Fibonacci n-step number sequences: Difference between revisions
Line 666: | Line 666: | ||
1 1 2 4 8 16 32 63 125 248 |
1 1 2 4 8 16 32 63 125 248 |
||
$ |
$ |
||
</pre> |
|||
<pre> |
|||
$ for n in 2 3 4;do echo -e $n\\n10\\ny|./f;done |
|||
Enter the number of terms to sum: Show the the first how many terms of the sequence? Accept this initial sequence (y/n)? |
|||
1 1 |
|||
1 1 2 3 5 8 13 21 34 55 |
|||
Enter the number of terms to sum: Show the the first how many terms of the sequence? Accept this initial sequence (y/n)? |
|||
1 1 2 |
|||
1 1 2 4 7 13 24 44 81 149 |
|||
Enter the number of terms to sum: Show the the first how many terms of the sequence? Accept this initial sequence (y/n)? |
|||
1 1 2 4 |
|||
1 1 2 4 8 15 29 56 108 208 |
|||
</pre> |
</pre> |
||
Revision as of 03:45, 5 April 2014
{f{task}} These number series are an expansion of the ordinary Fibonacci sequence where:
- For we have the Fibonacci sequence; with initial values and
- For we have the tribonacci sequence; with initial values and
- For we have the tetranacci sequence; with initial values and
... - For general we have the Fibonacci -step sequence - ; with initial values of the first values of the 'th Fibonacci -step sequence ; and 'th value of this 'th sequence being
For small values of , Greek numeric prefixes are sometimes used to individually name each series.
Fibonacci -step sequences Series name Values 2 fibonacci 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... 3 tribonacci 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ... 4 tetranacci 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ... 5 pentanacci 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ... 6 hexanacci 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ... 7 heptanacci 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ... 8 octonacci 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ... 9 nonanacci 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ... 10 decanacci 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
Allied sequences can be generated where the initial values are changed:
- The Lucas series sums the two preceeding values like the fibonacci series for but uses as its initial values.
- The task is to
- Write a function to generate Fibonacci -step number sequences given its initial values and assuming the number of initial values determines how many previous values are summed to make the next number of the series.
- Use this to print and show here at least the first ten members of the Fibo/tribo/tetra-nacci and Lucas sequences.
- Cf.
Ada
First, we specify a package Bonacci, that defines the type Sequence (of Positive numbers), a function Generate that takes a given Start sequence and outputs a generalized N-Bonacci Sequence of a spefified Length, and some constant start sequences.
<lang Ada>package Bonacci is
type Sequence is array(Positive range <>) of Positive;
function Generate(Start: Sequence; Length: Positive := 10) return Sequence;
Start_Fibonacci: constant Sequence := (1, 1); Start_Tribonacci: constant Sequence := (1, 1, 2); Start_Tetranacci: constant Sequence := (1, 1, 2, 4); Start_Lucas: constant Sequence := (2, 1);
end Bonacci;</lang>
The implementation is quite straightforward.
<lang Ada>package body Bonacci is
function Generate(Start: Sequence; Length: Positive := 10) return Sequence is begin if Length <= Start'Length then return Start(Start'First .. Start'First+Length-1); else declare Sum: Natural := 0; begin for I in Start'Range loop Sum := Sum + Start(I); end loop; return Start(Start'First) & Generate(Start(Start'First+1 .. Start'Last) & Sum, Length-1); end; end if; end Generate;
end Bonacci;</lang>
Finally, we actually generate some sequences, as required by the task. For convenience, we define a procedure Print that outputs a sequence,
<lang Ada>with Ada.Text_IO, Bonacci;
procedure Test_Bonacci is
procedure Print(Name: String; S: Bonacci.Sequence) is begin Ada.Text_IO.Put(Name & "("); for I in S'First .. S'Last-1 loop Ada.Text_IO.Put(Integer'Image(S(I)) & ","); end loop; Ada.Text_IO.Put_Line(Integer'Image(S(S'Last)) & " )"); end Print;
begin
Print("Fibonacci: ", Bonacci.Generate(Bonacci.Start_Fibonacci)); Print("Tribonacci: ", Bonacci.Generate(Bonacci.Start_Tribonacci)); Print("Tetranacci: ", Bonacci.Generate(Bonacci.Start_Tetranacci)); Print("Lucas: ", Bonacci.Generate(Bonacci.Start_Lucas)); Print("Decanacci: ", Bonacci.Generate((1, 1, 2, 4, 8, 16, 32, 64, 128, 256), 15));
end Test_Bonacci;</lang>
The output:
Fibonacci: ( 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ) Tribonacci: ( 1, 1, 2, 4, 7, 13, 24, 44, 81, 149 ) Tetranacci: ( 1, 1, 2, 4, 8, 15, 29, 56, 108, 208 ) Lucas: ( 2, 1, 3, 4, 7, 11, 18, 29, 47, 76 ) Decanacci: ( 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172 )
ACL2
<lang lisp>(defun sum (xs)
(if (endp xs) 0 (+ (first xs) (sum (rest xs)))))
(defun n-bonacci (prevs limit)
(if (zp limit) nil (let ((next (append (rest prevs) (list (sum prevs))))) (cons (first next) (n-bonacci next (1- limit))))))</lang>
Output:
> (n-bonacci '(1 1) 10) (1 2 3 5 8 13 21 34 55 89) > (n-bonacci '(1 1 2) 10) (1 2 4 7 13 24 44 81 149 274) > (n-bonacci '(1 1 2 4) 10) (1 2 4 8 15 29 56 108 208 401) > (n-bonacci '(2 1) 10) (1 3 4 7 11 18 29 47 76 123)
AutoHotkey
<lang AutoHotkey>for i, seq in ["nacci", "lucas"]
Loop, 9 { Out .= seq "(" A_Index + 1 "): " for key, val in NStepSequence(i, 1, A_Index + 1, 15) Out .= val (A_Index = 15 ? "`n" : "`, ") }
MsgBox, % Out
NStepSequence(v1, v2, n, k) {
a := [v1, v2] Loop, % k - 2 { a[j := A_Index + 2] := 0 Loop, % j < n + 2 ? j - 1 : n a[j] += a[j - A_Index] } return, a
}</lang> Output:
nacci(2): 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 nacci(3): 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136 nacci(4): 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536 nacci(5): 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930 nacci(6): 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617 nacci(7): 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936 nacci(8): 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080 nacci(9): 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144 nacci(10): 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172 lucas(2): 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843 lucas(3): 2, 1, 3, 6, 10, 19, 35, 64, 118, 217, 399, 734, 1350, 2483, 4567 lucas(4): 2, 1, 3, 6, 12, 22, 43, 83, 160, 308, 594, 1145, 2207, 4254, 8200 lucas(5): 2, 1, 3, 6, 12, 24, 46, 91, 179, 352, 692, 1360, 2674, 5257, 10335 lucas(6): 2, 1, 3, 6, 12, 24, 48, 94, 187, 371, 736, 1460, 2896, 5744, 11394 lucas(7): 2, 1, 3, 6, 12, 24, 48, 96, 190, 379, 755, 1504, 2996, 5968, 11888 lucas(8): 2, 1, 3, 6, 12, 24, 48, 96, 192, 382, 763, 1523, 3040, 6068, 12112 lucas(9): 2, 1, 3, 6, 12, 24, 48, 96, 192, 384, 766, 1531, 3059, 6112, 12212 lucas(10): 2, 1, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1534, 3067, 6131, 12256
BBC BASIC
The BBC BASIC SUM function is useful here. <lang bbcbasic> @% = 5 : REM Column width
PRINT "Fibonacci:" DIM f2%(1) : f2%() = 1,1 FOR i% = 1 TO 12 : PRINT f2%(0); : PROCfibn(f2%()) : NEXT : PRINT " ..." PRINT "Tribonacci:" DIM f3%(2) : f3%() = 1,1,2 FOR i% = 1 TO 12 : PRINT f3%(0); : PROCfibn(f3%()) : NEXT : PRINT " ..." PRINT "Tetranacci:" DIM f4%(3) : f4%() = 1,1,2,4 FOR i% = 1 TO 12 : PRINT f4%(0); : PROCfibn(f4%()) : NEXT : PRINT " ..." PRINT "Lucas:" DIM fl%(1) : fl%() = 2,1 FOR i% = 1 TO 12 : PRINT fl%(0); : PROCfibn(fl%()) : NEXT : PRINT " ..." END DEF PROCfibn(f%()) LOCAL i%, s% s% = SUM(f%()) FOR i% = 1 TO DIM(f%(),1) f%(i%-1) = f%(i%) NEXT f%(i%-1) = s% ENDPROC</lang>
Output:
Fibonacci: 1 1 2 3 5 8 13 21 34 55 89 144 ... Tribonacci: 1 1 2 4 7 13 24 44 81 149 274 504 ... Tetranacci: 1 1 2 4 8 15 29 56 108 208 401 773 ... Lucas: 2 1 3 4 7 11 18 29 47 76 123 199 ...
C
<lang c>/*29th August, 2012 Abhishek Ghosh
The function anynacci determines the n-arity of the sequence from the number of seed elements. 0 ended arrays are used since C does not have a way of determining the length of dynamic and function-passed integer arrays.*/
- include<stdlib.h>
- include<stdio.h>
int * anynacci (int *seedArray, int howMany) {
int *result = malloc (howMany * sizeof (int)); int i, j, initialCardinality;
for (i = 0; seedArray[i] != 0; i++); initialCardinality = i;
for (i = 0; i < initialCardinality; i++) result[i] = seedArray[i];
for (i = initialCardinality; i < howMany; i++) { result[i] = 0; for (j = i - initialCardinality; j < i; j++) result[i] += result[j]; } return result;
}
int main () {
int fibo[] = { 1, 1, 0 }, tribo[] = { 1, 1, 2, 0 }, tetra[] = { 1, 1, 2, 4, 0 }, luca[] = { 2, 1, 0 }; int *fibonacci = anynacci (fibo, 10), *tribonacci = anynacci (tribo, 10), *tetranacci = anynacci (tetra, 10), *lucas = anynacci(luca, 10); int i;
printf ("\nFibonacci\tTribonacci\tTetranacci\tLucas\n");
for (i = 0; i < 10; i++) printf ("\n%d\t\t%d\t\t%d\t\t%d", fibonacci[i], tribonacci[i], tetranacci[i], lucas[i]);
return 0;
}</lang>
Output:
Fibonacci Tribonacci Tetranacci Lucas 1 1 1 2 1 1 1 1 2 2 2 3 3 4 4 4 5 7 8 7 8 13 15 11 13 24 29 18 21 44 56 29 34 81 108 47 55 149 208 76
C++
<lang cpp>#include <vector>
- include <iostream>
- include <numeric>
- include <iterator>
- include <memory>
- include <string>
- include <algorithm>
- include <iomanip>
std::vector<int> nacci ( const std::vector<int> & start , int arity ) {
std::vector<int> result ( start ) ; int sumstart = 1 ;//summing starts at vector's begin + sumstart as //soon as the vector is longer than arity while ( result.size( ) < 15 ) { //we print out the first 15 numbers if ( result.size( ) <= arity )
result.push_back( std::accumulate( result.begin( ) , result.begin( ) + result.size( ) , 0 ) ) ;
else {
result.push_back( std::accumulate ( result.begin( ) + sumstart , result.begin( ) + sumstart + arity , 0 )) ; sumstart++ ;
} } return std::move ( result ) ;
}
int main( ) {
std::vector<std::string> naccinames {"fibo" , "tribo" , "tetra" , "penta" , "hexa" , "hepta" , "octo" , "nona" , "deca" } ; const std::vector<int> fibo { 1 , 1 } , lucas { 2 , 1 } ; for ( int i = 2 ; i < 11 ; i++ ) { std::vector<int> numberrow = nacci ( fibo , i ) ; std::cout << std::left << std::setw( 10 ) <<
naccinames[ i - 2 ].append( "nacci" ) << std::setw( 2 ) << " : " ;
std::copy ( numberrow.begin( ) , numberrow.end( ) ,
std::ostream_iterator<int>( std::cout , " " ) ) ;
std::cout << "...\n" ; numberrow = nacci ( lucas , i ) ; std::cout << "Lucas-" << i ; if ( i < 10 ) //for formatting purposes
std::cout << " : " ;
else
std::cout << " : " ;
std::copy ( numberrow.begin( ) , numberrow.end( ) ,
std::ostream_iterator<int>( std::cout , " " ) ) ;
std::cout << "...\n" ; } return 0 ;
}</lang> Output:
fibonacci : 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... Lucas-2 : 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 ... tribonacci : 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ... Lucas-3 : 2 1 3 6 10 19 35 64 118 217 399 734 1350 2483 4567 ... tetranacci : 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ... Lucas-4 : 2 1 3 6 12 22 43 83 160 308 594 1145 2207 4254 8200 ... pentanacci : 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ... Lucas-5 : 2 1 3 6 12 24 46 91 179 352 692 1360 2674 5257 10335 ... hexanacci : 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ... Lucas-6 : 2 1 3 6 12 24 48 94 187 371 736 1460 2896 5744 11394 ... heptanacci : 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ... Lucas-7 : 2 1 3 6 12 24 48 96 190 379 755 1504 2996 5968 11888 ... octonacci : 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ... Lucas-8 : 2 1 3 6 12 24 48 96 192 382 763 1523 3040 6068 12112 ... nonanacci : 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ... Lucas-9 : 2 1 3 6 12 24 48 96 192 384 766 1531 3059 6112 12212 ... decanacci : 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ... Lucas-10 : 2 1 3 6 12 24 48 96 192 384 768 1534 3067 6131 12256 ...
Clojure
<lang clojure>(defn nacci [init]
(letfn [(s [] (lazy-cat init (apply map + (map #(drop % (s)) (range (count init))))))] (s)))
(let [show (fn [name init] (println "first 20" name (take 20 (nacci init))))]
(show "Fibonacci" [1 1]) (show "Tribonacci" [1 1 2]) (show "Tetranacci" [1 1 2 4]) (show "Lucas" [2 1]))</lang>
- Output:
first 20 Fibonacci (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765) first 20 Tribonacci (1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012) first 20 Tetranacci (1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312) first 20 Lucas (2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349)
D
Basic Memoization
<lang d>void main() {
import std.stdio, std.algorithm, std.range, std.conv;
const(int)[] memo; size_t addNum;
void setHead(int[] head) nothrow { memo = head; addNum = head.length; }
int fibber(in size_t n) nothrow { if (n >= memo.length) memo ~= iota(n - addNum, n).map!fibber.sum; return memo[n]; }
setHead([1, 1]); 10.iota.map!fibber.writeln; setHead([2, 1]); 10.iota.map!fibber.writeln;
const prefixes = "fibo tribo tetra penta hexa hepta octo nona deca"; //foreach (immutable n, const name; prefixes.split.enumerate(2)) { foreach (immutable n, name; iota(2, 11).zip(prefixes.split)) { setHead(1 ~ iota(n - 1).map!q{2 ^^ a}.array); writefln("n=%2d, %5snacci -> %(%d %) ...", n, name, 15.iota.map!fibber); }
}</lang>
- Output:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] n= 2, fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ... n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ... n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ... n= 6, hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ... n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ... n= 8, octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ... n= 9, nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ... n=10, decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
Callable Struct
The output is similar. <lang d>import std.stdio, std.algorithm, std.range, std.conv;
struct fiblike(T) {
const(T)[] memo; immutable size_t addNum;
this(in T[] start) /*nothrow*/ { this.memo = start.dup; this.addNum = start.length; }
T opCall(in size_t n) /*nothrow*/ { if (n >= memo.length) memo ~= iota(n - addNum, n) .map!(i => opCall(i)) .sum .to!int; return memo[n]; }
}
void main() {
auto fibo = fiblike!int([1, 1]); iota(10).map!fibo.writeln;
auto lucas = fiblike!int([2, 1]); iota(10).map!lucas.writeln;
const prefixes = "fibo tribo tetra penta hexa hepta octo nona deca"; //foreach (immutable n, const name; prefixes.split.enumerate(2)) { foreach (immutable n, name; iota(2, 11).zip(prefixes.split)) { auto fib = fiblike!int(1 ~ iota(n - 1).map!q{2 ^^ a}.array); writefln("n=%2d, %5snacci -> %(%d %) ...", n, name, 15.iota.map!fib); }
}</lang>
Struct With opApply
The output is similar. <lang d>import std.stdio, std.algorithm, std.range, std.traits;
struct Fiblike(T) {
T[] tail;
int opApply(int delegate(immutable ref T) dg) { int result, pos; foreach (immutable x; tail) { result = dg(x); if (result) return result; } foreach (immutable i; tail.length.iota.cycle) { immutable x = tail.sum; result = dg(x); if (result) break; tail[i] = x; } return result; }
}
// std.range.take doesn't work with opApply. ForeachType!It[] takeApply(It)(It iterable, in size_t n) {
typeof(return) result; foreach (immutable x; iterable) { result ~= x; if (result.length == n) break; } return result;
}
void main() {
Fiblike!int([1, 1]).takeApply(10).writeln; Fiblike!int([2, 1]).takeApply(10).writeln;
const prefixes = "fibo tribo tetra penta hexa hepta octo nona deca"; //foreach (immutable n, const name; prefixes.split.enumerate(2)) { foreach (const n, name; iota(2, 11).zip(prefixes.split)) { auto fib = Fiblike!int(1 ~ iota(n - 1).map!q{2 ^^ a}.array); writefln("n=%2d, %5snacci -> %s", n, name, fib.takeApply(15)); }
}</lang>
Erlang
<lang> -module( fibonacci_nstep ).
-export( [nacci/2, task/0] ).
nacci( N, Ns ) when N =< erlang:length(Ns) -> {Sequence, _Not_sequence} = lists:split( N, Ns ), Sequence; nacci( N, Ns ) -> Nth = erlang:length( Ns ), {_Nth, Sequence_reversed} = lists:foldl( fun nacci_foldl/2, {Nth, lists:reverse(Ns)}, lists:seq(Nth+1, N) ), lists:reverse( Sequence_reversed ).
task() -> Names_and_funs = [{X, fun (N) -> nacci( N, Y ) end} || {X, Y} <- [{fibonacci, [1, 1]}, {tribonacci, [1, 1, 2]}, {tetranacci, [1, 1, 2, 4]}, {lukas, [2, 1]}]], [io:fwrite( "~p: ~p~n", [X, Y(10)] ) || {X, Y} <- Names_and_funs].
nacci_foldl( _N, {Nth, Ns} ) -> {Sum_ns, _Not_sum_ns} = lists:split( Nth, Ns ), {Nth, [lists:sum(Sum_ns) | Ns]}. </lang>
- Output:
59> fibonacci_nstep:task(). fibonacci: [1,1,2,3,5,8,13,21,34,55] tribonacci: [1,1,2,4,7,13,24,44,81,149] tetranacci: [1,1,2,4,8,15,29,56,108,208] lukas: [2,1,3,4,7,11,18,29,47,76]
F#
<lang fsharp>let fibinit = Seq.append (Seq.singleton 1) (Seq.unfold (fun n -> Some(n, 2*n)) 1)
let fiblike init =
Seq.append (Seq.ofList init) (Seq.unfold (function | least :: rest -> let this = least + Seq.reduce (+) rest Some(this, rest @ [this]) | _ -> None) init)
let lucas = fiblike [2; 1]
let nacci n = Seq.take n fibinit |> Seq.toList |> fiblike
[<EntryPoint>] let main argv =
let start s = Seq.take 15 s |> Seq.toList let prefix = "fibo tribo tetra penta hexa hepta octo nona deca".Split() Seq.iter (fun (p, n) -> printfn "n=%2i, %5snacci -> %A" n p (start (nacci n))) (Seq.init prefix.Length (fun i -> (prefix.[i], i+2))) printfn " lucas -> %A" (start (fiblike [2; 1])) 0</lang>
Output
n= 2, fibonacci -> [1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; 610] n= 3, tribonacci -> [1; 1; 2; 4; 7; 13; 24; 44; 81; 149; 274; 504; 927; 1705; 3136] n= 4, tetranacci -> [1; 1; 2; 4; 8; 15; 29; 56; 108; 208; 401; 773; 1490; 2872; 5536] n= 5, pentanacci -> [1; 1; 2; 4; 8; 16; 31; 61; 120; 236; 464; 912; 1793; 3525; 6930] n= 6, hexanacci -> [1; 1; 2; 4; 8; 16; 32; 63; 125; 248; 492; 976; 1936; 3840; 7617] n= 7, heptanacci -> [1; 1; 2; 4; 8; 16; 32; 64; 127; 253; 504; 1004; 2000; 3984; 7936] n= 8, octonacci -> [1; 1; 2; 4; 8; 16; 32; 64; 128; 255; 509; 1016; 2028; 4048; 8080] n= 9, nonanacci -> [1; 1; 2; 4; 8; 16; 32; 64; 128; 256; 511; 1021; 2040; 4076; 8144] n=10, decanacci -> [1; 1; 2; 4; 8; 16; 32; 64; 128; 256; 512; 1023; 2045; 4088; 8172] lucas -> [2; 1; 3; 4; 7; 11; 18; 29; 47; 76; 123; 199; 322; 521; 843]
FORTRAN
<lang FORTRAN> ! save this program as file f.f08 ! gnu-linux command to build and test ! $ a=./f && gfortran -Wall -std=f2008 $a.f08 -o $a && echo -e 2\\n5\\n\\n | $a
! -*- mode: compilation; default-directory: "/tmp/" -*- ! Compilation started at Fri Apr 4 23:20:27 ! ! a=./f && gfortran -Wall -std=f2008 $a.f08 -o $a && echo -e 2\\n8\\ny\\n | $a ! Enter the number of terms to sum: Show the the first how many terms of the sequence? Accept this initial sequence (y/n)? ! 1 1 ! 1 1 2 3 5 8 13 21 ! ! Compilation finished at Fri Apr 4 23:20:27
program f
implicit none integer :: n, terms integer, allocatable, dimension(:) :: sequence integer :: i character :: answer write(6,'(a)',advance='no')'Enter the number of terms to sum: ' read(5,*) n if ((n < 2) .or. (29 < n)) stop'Unreasonable! Exit.' write(6,'(a)',advance='no')'Show the the first how many terms of the sequence? ' read(5,*) terms if (terms < 1) stop'Lazy programmer has not implemented backward sequences.' n = min(n, terms) allocate(sequence(1:terms)) sequence(1) = 1 do i = 0, n - 2 sequence(i+2) = 2**i end do write(6,*)'Accept this initial sequence (y/n)?' write(6,*) sequence(:n) read(5,*) answer if (answer .eq. 'n') then write(6,*) 'Fine. Enter the initial terms.' do i=1, n write(6, '(i2,a2)', advance = 'no') i, ': ' read(5, *) sequence(i) end do end if call nacci(n, sequence) write(6,*) sequence(:terms) deallocate(sequence)
contains
subroutine nacci(n, s) ! nacci =: (] , +/@{.)^:(-@#@]`(-#)`]) integer, intent(in) :: n integer, intent(inout), dimension(:) :: s integer :: i, terms terms = size(s)
! do i = n+1, terms
! s(i) = sum(s(i-n:i-1)) ! end do i = n+1 if (n+1 .le. terms) s(i) = sum(s(i-n:i-1)) do i = n + 2, terms s(i) = 2*s(i-1) - s(i-(n+1)) end do end subroutine nacci
end program f </lang>
$ ./f # Lucas series Enter the number of terms to sum: 2 Show the the first how many terms of the sequence? 10 Accept this initial sequence (y/n)? 1 1 n Fine. Enter the initial terms. 1: 2 2: 1 2 1 3 4 7 11 18 29 47 76 $ $ $ $ $ $ $ ./f # Waltzing the 6-step Enter the number of terms to sum: 6 Show the the first how many terms of the sequence? 10 Accept this initial sequence (y/n)? 1 1 2 4 8 16 y 1 1 2 4 8 16 32 63 125 248 $
$ for n in 2 3 4;do echo -e $n\\n10\\ny|./f;done Enter the number of terms to sum: Show the the first how many terms of the sequence? Accept this initial sequence (y/n)? 1 1 1 1 2 3 5 8 13 21 34 55 Enter the number of terms to sum: Show the the first how many terms of the sequence? Accept this initial sequence (y/n)? 1 1 2 1 1 2 4 7 13 24 44 81 149 Enter the number of terms to sum: Show the the first how many terms of the sequence? Accept this initial sequence (y/n)? 1 1 2 4 1 1 2 4 8 15 29 56 108 208
Go
Solution using a separate goroutine. <lang go>package main
import "fmt"
func g(i []int, c chan int) {
var sum int b := append([]int{}, i...) for _, t := range b { c <- t sum += t } for { for j, t := range b { c <- sum b[j], sum = sum, sum+sum-t } }
}
func main() {
for _, s := range []struct { seq string i []int } { {"Fibonacci", []int{1, 1}}, {"Tribonacci", []int{1, 1, 2}}, {"Tetranacci", []int{1, 1, 2, 4}}, {"Lucas", []int{2, 1}}, } { fmt.Printf("%10s:", s.seq) c := make(chan int) go g(s.i, c) for j := 0; j < 10; j++ { fmt.Print(" ", <-c) } fmt.Println() }
}</lang>
- Output:
Fibonacci: 1 1 2 3 5 8 13 21 34 55 Tribonacci: 1 1 2 4 7 13 24 44 81 149 Tetranacci: 1 1 2 4 8 15 29 56 108 208 Lucas: 2 1 3 4 7 11 18 29 47 76
Haskell
<lang haskell>import Data.List (tails) import Control.Monad (zipWithM_)
fiblike :: [Integer] -> [Integer] fiblike st = xs where
xs = st ++ map (sum . take n) (tails xs) n = length st
nstep :: Int -> [Integer] nstep n = fiblike $ take n $ 1 : iterate (2*) 1
main :: IO () main = do
print $ take 10 $ fiblike [1,1] print $ take 10 $ fiblike [2,1] zipWithM_ (\n name -> do putStr (name ++ "nacci -> ") print $ take 15 $ nstep n) [2..] (words "fibo tribo tetra penta hexa hepta octo nona deca")</lang>
- Output:
[1,1,2,3,5,8,13,21,34,55] [2,1,3,4,7,11,18,29,47,76] fibonacci -> [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610] tribonacci -> [1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136] tetranacci -> [1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536] pentanacci -> [1,1,2,4,8,16,31,61,120,236,464,912,1793,3525,6930] hexanacci -> [1,1,2,4,8,16,32,63,125,248,492,976,1936,3840,7617] heptanacci -> [1,1,2,4,8,16,32,64,127,253,504,1004,2000,3984,7936] octonacci -> [1,1,2,4,8,16,32,64,128,255,509,1016,2028,4048,8080] nonanacci -> [1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144] decanacci -> [1,1,2,4,8,16,32,64,128,256,512,1023,2045,4088,8172]
J
Solution:<lang j> nacci =: (] , +/@{.)^:(-@#@]`(-#)`])</lang> Example (Lucas):<lang j> 10 nacci 2 1 NB. Lucas series, first 10 terms 2 1 3 4 7 11 18 29 47 76</lang> Example (extended 'nacci series):<lang j> TESTS =: }."1 fixdsv noun define [ require 'tables/dsv' NB. Tests from task description 2 fibonacci 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... 3 tribonacci 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ... 4 tetranacci 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ... 5 pentanacci 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ... 6 hexanacci 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ... 7 heptanacci 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ... 8 octonacci 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ... 9 nonanacci 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ... 10 decanacci 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ... )
testNacci =: ] -: #@] nacci {. NB. Given an order & test sequence, compare nacci to sequence OT =: __ ".&.> (<<<1) { |: TESTS NB. 'nacci order and test sequence (> 1 {"1 TESTS) ,. ' ' ,. (u: 16b274c 16b2713) {~ (testNacci }:)&>/ OT NB. ✓ or ❌ for success or failure
fibonacci ✓ tribonacci ✓ tetranacci ✓ pentanacci ✓ hexanacci ✓ heptanacci ✓ octonacci ✓ nonanacci ✓ decanacci ✓</lang>
Java
Code:
<lang java>class Fibonacci {
public static int[] lucas(int n, int numRequested) { if (n < 2) throw new IllegalArgumentException("Fibonacci value must be at least 2"); return fibonacci((n == 2) ? new int[] { 2, 1 } : lucas(n - 1, n), numRequested); } public static int[] fibonacci(int n, int numRequested) { if (n < 2) throw new IllegalArgumentException("Fibonacci value must be at least 2"); return fibonacci((n == 2) ? new int[] { 1, 1 } : fibonacci(n - 1, n), numRequested); } public static int[] fibonacci(int[] startingValues, int numRequested) { int[] output = new int[numRequested]; int n = startingValues.length; System.arraycopy(startingValues, 0, output, 0, n); for (int i = n; i < numRequested; i++) for (int j = 1; j <= n; j++) output[i] += output[i - j]; return output; } public static void main(String[] args) { for (int n = 2; n <= 10; n++) { System.out.print("nacci(" + n + "):"); for (int value : fibonacci(n, 15)) System.out.print(" " + value); System.out.println(); } for (int n = 2; n <= 10; n++) { System.out.print("lucas(" + n + "):"); for (int value : lucas(n, 15)) System.out.print(" " + value); System.out.println(); } }
}</lang>
Output:
nacci(2): 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 nacci(3): 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 nacci(4): 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 nacci(5): 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 nacci(6): 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 nacci(7): 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 nacci(8): 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 nacci(9): 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 nacci(10): 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 lucas(2): 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 lucas(3): 2 1 3 6 10 19 35 64 118 217 399 734 1350 2483 4567 lucas(4): 2 1 3 6 12 22 43 83 160 308 594 1145 2207 4254 8200 lucas(5): 2 1 3 6 12 24 46 91 179 352 692 1360 2674 5257 10335 lucas(6): 2 1 3 6 12 24 48 94 187 371 736 1460 2896 5744 11394 lucas(7): 2 1 3 6 12 24 48 96 190 379 755 1504 2996 5968 11888 lucas(8): 2 1 3 6 12 24 48 96 192 382 763 1523 3040 6068 12112 lucas(9): 2 1 3 6 12 24 48 96 192 384 766 1531 3059 6112 12212 lucas(10): 2 1 3 6 12 24 48 96 192 384 768 1534 3067 6131 12256
JavaScript
<lang JavaScript>function fib(arity, len) {
return nacci(nacci([1,1], arity, arity), arity, len);
}
function lucas(arity, len) {
return nacci(nacci([2,1], arity, arity), arity, len);
}
function nacci(a, arity, len) {
while (a.length < len) { var sum = 0; for (var i = Math.max(0, a.length - arity); i < a.length; i++) sum += a[i]; a.push(sum); } return a;
}
function main() {
for (var arity = 2; arity <= 10; arity++) console.log("fib(" + arity + "): " + fib(arity, 15)); for (var arity = 2; arity <= 10; arity++) console.log("lucas(" + arity + "): " + lucas(arity, 15));
}
main();</lang>
- Output:
fib(2): 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610 fib(3): 1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136 fib(4): 1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536 fib(5): 1,1,2,4,8,16,31,61,120,236,464,912,1793,3525,6930 fib(6): 1,1,2,4,8,16,32,63,125,248,492,976,1936,3840,7617 fib(7): 1,1,2,4,8,16,32,64,127,253,504,1004,2000,3984,7936 fib(8): 1,1,2,4,8,16,32,64,128,255,509,1016,2028,4048,8080 fib(9): 1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144 fib(10): 1,1,2,4,8,16,32,64,128,256,512,1023,2045,4088,8172 lucas(2): 2,1,3,4,7,11,18,29,47,76,123,199,322,521,843 lucas(3): 2,1,3,6,10,19,35,64,118,217,399,734,1350,2483,4567 lucas(4): 2,1,3,6,12,22,43,83,160,308,594,1145,2207,4254,8200 lucas(5): 2,1,3,6,12,24,46,91,179,352,692,1360,2674,5257,10335 lucas(6): 2,1,3,6,12,24,48,94,187,371,736,1460,2896,5744,11394 lucas(7): 2,1,3,6,12,24,48,96,190,379,755,1504,2996,5968,11888 lucas(8): 2,1,3,6,12,24,48,96,192,382,763,1523,3040,6068,12112 lucas(9): 2,1,3,6,12,24,48,96,192,384,766,1531,3059,6112,12212 lucas(10): 2,1,3,6,12,24,48,96,192,384,768,1534,3067,6131,12256
Mathematica
<lang Mathematica> f2=Function[{l,k},
Module[{n=Length@l,m}, m=SparseArray[{{i_,j_}/;i==1||i==j+1->1},{n,n}]; NestList[m.#&,l,k]]];
Table[Last/@f2[{1,1}~Join~Table[0,{n-2}],15+n]-18;;,{n,2,10}]//TableForm Table[Last/@f2[{1,2}~Join~Table[0,{n-2}],15+n]-18;;,{n,2,10}]//TableForm </lang> Output:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 2 1 3 6 10 19 35 64 118 217 399 734 1350 2483 4567 8400 15450 28417 2 1 3 6 12 22 43 83 160 308 594 1145 2207 4254 8200 15806 30467 58727 2 1 3 6 12 24 46 91 179 352 692 1360 2674 5257 10335 20318 39944 78528 2 1 3 6 12 24 48 94 187 371 736 1460 2896 5744 11394 22601 44831 88926 2 1 3 6 12 24 48 96 190 379 755 1504 2996 5968 11888 23680 47170 93961 2 1 3 6 12 24 48 96 192 382 763 1523 3040 6068 12112 24176 48256 96320 2 1 3 6 12 24 48 96 192 384 766 1531 3059 6112 12212 24400 48752 97408 2 1 3 6 12 24 48 96 192 384 768 1534 3067 6131 12256 24500 48976 97904
PARI/GP
The function gen
generates code to generate a given number of terms of the k-th sequence. Of course there are other approaches.
Use genV if you prefer to supply a different starting vector. <lang parigp>gen(n)=k->my(v=vector(k,i,1));for(i=3,min(k,n),v[i]=2^(i-2));for(i=n+1,k,v[i]=sum(j=i-n,i-1,v[j]));v genV(n)=v->for(i=3,min(#v,n),v[i]=2^(i-2));for(i=n+1,#v,v[i]=sum(j=i-n,i-1,v[j]));v for(n=2,10,print(n"\t"gen(n)(10)))</lang>
Pascal
<lang pascal>program FibbonacciN (output);
type
TintArray = array of integer;
const
Name: array[2..11] of string = ('Fibonacci: ', 'Tribonacci: ', 'Tetranacci: ', 'Pentanacci: ', 'Hexanacci: ', 'Heptanacci: ', 'Octonacci: ', 'Nonanacci: ', 'Decanacci: ', 'Lucas: ' );
var
sequence: TintArray; j, k: integer;
function CreateFibbo(n: integer): TintArray;
var i: integer; begin setlength(CreateFibbo, n); CreateFibbo[0] := 1; CreateFibbo[1] := 1; i := 2; while i < n do begin CreateFibbo[i] := CreateFibbo[i-1] * 2; inc(i); end; end;
procedure Fibbonacci(var start: TintArray);
const No_of_examples = 11; var n, i, j: integer; begin n := length(start); setlength(start, No_of_examples); for i := n to high(start) do begin start[i] := 0; for j := 1 to n do start[i] := start[i] + start[i-j] end; end;
begin
for j := 2 to 10 do begin sequence := CreateFibbo(j); Fibbonacci(sequence); write (Name[j]); for k := low(sequence) to high(sequence) do write(sequence[k], ' '); writeln; end; setlength(sequence, 2); sequence[0] := 2; sequence[1] := 1; Fibbonacci(sequence); write (Name[11]); for k := low(sequence) to high(sequence) do write(sequence[k], ' '); writeln;
end.</lang> Output:
% ./Fibbonacci Fibonacci: 1 1 2 3 5 8 13 21 34 55 89 Tribonacci: 1 1 2 4 7 13 24 44 81 149 274 Tetranacci: 1 1 2 4 8 15 29 56 108 208 401 Pentanacci: 1 1 2 4 8 16 31 61 120 236 464 Hexanacci: 1 1 2 4 8 16 32 63 125 248 492 Heptanacci: 1 1 2 4 8 16 32 64 127 253 504 Octonacci: 1 1 2 4 8 16 32 64 128 255 509 Nonanacci: 1 1 2 4 8 16 32 64 128 256 511 Decanacci: 1 1 2 4 8 16 32 64 128 256 512 Lucas: 2 1 3 4 7 11 18 29 47 76 123
Perl
<lang perl>use 5.010;
use List::Util qw/max sum/;
sub fib {
my $n = shift; my $xs = shift // [1]; my @xs = @{$xs};
while (my $len = scalar @xs) { last if $len >= 20; push( @xs, sum(@xs[max($len - $n, 0)..$len-1]) ); } return @xs;
}
for (2..10) {
say join(' ', fib($_));
} say join(' ', fib(2, [2,1]));</lang>
- Output:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349
Perl 6
Lazy List with Closure
<lang perl6>sub fibo ($n) {
constant @starters = 1,1,2,4 ... *; nacci @starters[^$n];
}
sub nacci (*@starter) {
my &fun = eval join '+', '*' xx @starter; @starter, &fun ... *;
}
for 2..10 -> $n { say fibo($n)[^20] } say nacci(2,1)[^20];</lang>
- Output:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349
Generative
A slightly more straight forward way of constructing a lazy list.
<lang perl6>sub fib ($n, @xs is copy = [1]) {
gather { take @xs[*]; loop { take my $x = [+] @xs; @xs.push: $x; @xs.shift if @xs > $n; } }
}
for 2..10 -> $n {
say fib($n, [1])[^20];
} say fib(2, [2,1])[^20];</lang>
PicoLisp
<lang PicoLisp>(de nacci (Init Cnt)
(let N (length Init) (make (made Init) (do (- Cnt N) (link (apply + (tail N (made)))) ) ) ) )</lang>
Test: <lang PicoLisp># Fibonacci
- (nacci (1 1) 10)
-> (1 1 2 3 5 8 13 21 34 55)
- Tribonacci
- (nacci (1 1 2) 10)
-> (1 1 2 4 7 13 24 44 81 149)
- Tetranacci
- (nacci (1 1 2 4) 10)
-> (1 1 2 4 8 15 29 56 108 208)
- Lucas
- (nacci (2 1) 10)
-> (2 1 3 4 7 11 18 29 47 76)
- Decanacci
- (nacci (1 1 2 4 8 16 32 64 128 256) 15)
-> (1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172)</lang>
PHP
<lang php><?php /**
* @author Elad Yosifon */
/**
* @param int $x * @param array $series * @param int $n * @return array */
function fib_n_step($x, &$series = array(1, 1), $n = 15) { $count = count($series);
if($count > $x && $count == $n) // exit point { return $series; }
if($count < $n) { if($count >= $x) // 4 or less { fib($series, $x, $count); return fib_n_step($x, $series, $n); } else // 5 or more { while(count($series) < $x ) { $count = count($series); fib($series, $count, $count); } return fib_n_step($x, $series, $n); } }
return $series; }
/**
* @param array $series * @param int $n * @param int $i */
function fib(&$series, $n, $i) { $end = 0; for($j = $n; $j > 0; $j--) { $end += $series[$i-$j]; } $series[$i] = $end; }
/*=================== OUTPUT ============================*/
header('Content-Type: text/plain'); $steps = array( 'LUCAS' => array(2, array(2, 1)), 'FIBONACCI' => array(2, array(1, 1)), 'TRIBONACCI' => array(3, array(1, 1, 2)), 'TETRANACCI' => array(4, array(1, 1, 2, 4)), 'PENTANACCI' => array(5, array(1, 1, 2, 4)), 'HEXANACCI' => array(6, array(1, 1, 2, 4)), 'HEPTANACCI' => array(7, array(1, 1, 2, 4)), 'OCTONACCI' => array(8, array(1, 1, 2, 4)), 'NONANACCI' => array(9, array(1, 1, 2, 4)), 'DECANACCI' => array(10, array(1, 1, 2, 4)), );
foreach($steps as $name=>$pair) { $ser = fib_n_step($pair[0],$pair[1]); $n = count($ser)-1;
echo $name." => ".implode(',', $ser) . "\n"; }
</lang>
- Output:
LUCAS => 2,1,3,4,7,11,18,29,47,76,123,199,322,521,843 FIBONACCI => 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610 TRIBONACCI => 1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136 TETRANACCI => 1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536 PENTANACCI => 1,1,2,4,8,16,31,61,120,236,464,912,1793,3525,6930 HEXANACCI => 1,1,2,4,8,16,32,63,125,248,492,976,1936,3840,7617 HEPTANACCI => 1,1,2,4,8,16,32,64,127,253,504,1004,2000,3984,7936 OCTONACCI => 1,1,2,4,8,16,32,64,128,255,509,1016,2028,4048,8080 NONANACCI => 1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144 DECANACCI => 1,1,2,4,8,16,32,64,128,256,512,1023,2045,4088,8172
PL/I
<lang PL/I>(subscriptrange, fixedoverflow, size): n_step_Fibonacci: procedure options (main);
declare line character (100) varying; declare (i, j, k) fixed binary;
put ('n-step Fibonacci series: Please type the initial values on one line:'); get edit (line) (L); line = trim(line); k = tally(line, ' ') - tally(line, ' ') + 1; /* count values */
begin; declare (n(k), s) fixed decimal (15); get string (line || ' ') list ( n );
if n(1) = 2 then put ('We have a Lucan series'); else put ('We have a ' || trim(k) || '-step Fibonacci series.');
put skip edit ( (trim(n(i)) do i = 1 to k) ) (a, x(1)); do j = k+1 to 20; /* In toto, generate 20 values in the series. */ s = sum(n); /* the next value in the series */ put edit (trim(s)) (x(1), a); do i = lbound(n,1)+1 to k; /* Discard the oldest value */ n(i-1) = n(i); end; n(k) = s; /* and insert the new value */ end; end;
end n_step_Fibonacci;</lang> Output:
We have a Lucan series. 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 We have a 2-step Fibonacci series. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 We have a 3-step Fibonacci series. 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 We have a 4-step Fibonacci series. 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 We have a 5-step Fibonacci series. 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513
PureBasic
<lang PureBasic>
Procedure.i FibonacciLike(k,n=2,p.s="",d.s=".") Protected i,r if k<0:ProcedureReturn 0:endif if p.s n=CountString(p.s,d.s)+1 for i=0 to n-1 if k=i:ProcedureReturn val(StringField(p.s,i+1,d.s)):endif next else if k=0:ProcedureReturn 1:endif if k=1:ProcedureReturn 1:endif endif for i=1 to n r+FibonacciLike(k-i,n,p.s,d.s) next ProcedureReturn r EndProcedure
- The fact that PureBasic supports default values for procedure parameters
- is very useful in a case such as this.
- Since
- k=4
- Debug FibonacciLike(k) ;good old Fibonacci
- Debug FibonacciLike(k,3) ;here we specified n=3 [Tribonacci]
- Debug FibonacciLike(k,3,"1.1.2") ;using the default delimiter "."
- Debug FibonacciLike(k,3,"1,1,2",",") ;using a different delimiter ","
- the last three all produce the same result.
- as do the following two for the Lucas series
- Debug FibonacciLike(k,2,"2.1") ;using the default delimiter "."
- Debug FibonacciLike(k,2,"2,1",",") ;using a different delimiter ","
m=10 t.s=lset("n",5) for k=0 to m
t.s+lset(str(k),5) next
Debug t.s for n=2 to 10
t.s=lset(str(n),5) for k=0 to m t.s+lset(str(FibonacciLike(k,n)),5) next
Debug t.s next Debug "" p.s="2.1" t.s=lset(p.s,5) for k=0 to m
t.s+lset(str(FibonacciLike(k,n,p.s)),5) next
Debug t.s Debug ""
</lang>
Sample Output
n 0 1 2 3 4 5 6 7 8 9 10 2 1 1 2 3 5 8 13 21 34 55 89 3 1 1 2 4 7 13 24 44 81 149 274 4 1 1 2 4 8 15 29 56 108 208 401 5 1 1 2 4 8 16 31 61 120 236 464 6 1 1 2 4 8 16 32 63 125 248 492 7 1 1 2 4 8 16 32 64 127 253 504 8 1 1 2 4 8 16 32 64 128 255 509 9 1 1 2 4 8 16 32 64 128 256 511 10 1 1 2 4 8 16 32 64 128 256 512 2.1 2 1 3 4 7 11 18 29 47 76 123
Python
Python: function returning a function
<lang python>>>> def fiblike(start): addnum = len(start) memo = start[:] def fibber(n): try: return memo[n] except IndexError: ans = sum(fibber(i) for i in range(n-addnum, n)) memo.append(ans) return ans return fibber
>>> fibo = fiblike([1,1]) >>> [fibo(i) for i in range(10)] [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> lucas = fiblike([2,1]) >>> [lucas(i) for i in range(10)] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] >>> for n, name in zip(range(2,11), 'fibo tribo tetra penta hexa hepta octo nona deca'.split()) : fibber = fiblike([1] + [2**i for i in range(n-1)]) print('n=%2i, %5snacci -> %s ...' % (n, name, ' '.join(str(fibber(i)) for i in range(15))))
n= 2, fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ...
n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ...
n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ...
n= 6, hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ...
n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ...
n= 8, octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ...
n= 9, nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ...
n=10, decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
>>> </lang>
Python: Callable class
<lang python>>>> class Fiblike(): def __init__(self, start): self.addnum = len(start) self.memo = start[:] def __call__(self, n): try: return self.memo[n] except IndexError: ans = sum(self(i) for i in range(n-self.addnum, n)) self.memo.append(ans) return ans
>>> fibo = Fiblike([1,1])
>>> [fibo(i) for i in range(10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> lucas = Fiblike([2,1])
>>> [lucas(i) for i in range(10)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
>>> for n, name in zip(range(2,11), 'fibo tribo tetra penta hexa hepta octo nona deca'.split()) :
fibber = Fiblike([1] + [2**i for i in range(n-1)])
print('n=%2i, %5snacci -> %s ...' % (n, name, ' '.join(str(fibber(i)) for i in range(15))))
n= 2, fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ...
n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ...
n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ...
n= 6, hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ...
n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ...
n= 8, octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ...
n= 9, nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ...
n=10, decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
>>> </lang>
Python: Generator
<lang python>from itertools import islice, cycle
def fiblike(tail):
for x in tail: yield x for i in cycle(xrange(len(tail))): tail[i] = x = sum(tail) yield x
fibo = fiblike([1, 1]) print list(islice(fibo, 10)) lucas = fiblike([2, 1]) print list(islice(lucas, 10))
suffixes = "fibo tribo tetra penta hexa hepta octo nona deca" for n, name in zip(xrange(2, 11), suffixes.split()):
fib = fiblike([1] + [2 ** i for i in xrange(n - 1)]) items = list(islice(fib, 15)) print "n=%2i, %5snacci -> %s ..." % (n, name, items)</lang>
- Output:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] n= 2, fibonacci -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] ... n= 3, tribonacci -> [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136] ... n= 4, tetranacci -> [1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536] ... n= 5, pentanacci -> [1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930] ... n= 6, hexanacci -> [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617] ... n= 7, heptanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936] ... n= 8, octonacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080] ... n= 9, nonanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144] ... n=10, decanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172] ...
Racket
<lang Racket>#lang racket
- fib-n
- Nat x Nat -> [List Nat]
- Outputs the first x numbers in the
- n-step fibonacci sequence
- n > 1
(define (fib-n n x)
(cond [(= x 0) empty] [(= x 1) '(1)] [(= x 2) '(1 1)] [(<= x (add1 n)) (append '(1 1) (build-list (- x 2) (λ (y) (expt 2 (add1 y)))))] [else (local ((define first-values (append '(1 1) (build-list (- n 1) (λ (x) (expt 2 (add1 x)))))) (define (add-values lon y acc) (cond [(= y 0) acc] [else (add-values (rest lon) (sub1 y) (+ (first lon) acc))])) (define (acc lon y) (cond [(= y x) lon] [else (acc (cons (add-values lon n 0) lon) (add1 y))]))) (reverse (acc (reverse first-values) (add1 n))))]))
- fib-list
- [List Nat] x Nat -> [List Nat]
- Given a list of natural numbers,
- the length of the list becomes the
- size of the step, and outputs
- the first x numbers of the sequence
- (len lon) > 1
(define (fib-list lon x)
(local ((define step (length lon))) (cond [(= x step) lon] [(< x step) (local ((define (extract-values lon y) (cond [(= y 0) empty] [else (cons (first lon) (extract-values (rest lon) (sub1 y)))]))) (extract-values lon x))] [else (local ((define (add-values lon y acc) (cond [(= y 0) acc] [else (add-values (rest lon) (sub1 y) (+ (first lon) acc))])) (define (acc lon y) (cond [(= y x) lon] [else (acc (cons (add-values lon step 0) lon) (add1 y))]))) (reverse (acc (reverse lon) step)))])))
- Now compute the series
(for/list ([n (in-range 2 11)])
(fib-list (fib-n n n) 20))
</lang>
Output:
'((1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765) (1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012) (1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312) (1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513) (1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904) (1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888) (1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005) (1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328) (1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864))
REXX
<lang rexx>/*REXX program calculates and displays N-step Fibonacci sequences. */ parse arg FibName values /*allow user to specify which Fib*/
if FibName\= then do /*if specified, show that Fib. */
call nStepFib FibName, values exit /*stick a fork in it, we're done.*/ end /*nothing given, so show a bunch.*/
call nStepFib 'Lucas' , 2 1 call nStepFib 'fibonacci' , 1 1 call nStepFib 'tribonacci' , 1 1 2 call nStepFib 'tetranacci' , 1 1 2 4 call nStepFib 'pentanacci' , 1 1 2 4 8 call nStepFib 'hexanacci' , 1 1 2 4 8 16 call nStepFib 'heptanacci' , 1 1 2 4 8 16 32 call nStepFib 'octonacci' , 1 1 2 4 8 16 32 64 call nStepFib 'nonanacci' , 1 1 2 4 8 16 32 64 128 call nStepFib 'decanacci' , 1 1 2 4 8 16 32 64 128 256 call nStepFib 'undecanacci' , 1 1 2 4 8 16 32 64 128 256 512 call nStepFib 'dodecanacci' , 1 1 2 4 8 16 32 64 128 256 512 1024 call nStepFib '13th-order' , 1 1 2 4 8 16 32 64 128 256 512 1024 2048 exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────NSTEPFIB subroutine─────────────────*/ nStepFib: procedure; parse arg Fname,vals,m; if m== then m=30; L= N=words(vals)
do pop=1 for N /*use N initial vals*/ @.pop=word(vals,pop) /*populate initial #s.*/ end /*pop*/ do j=1 for m /*calculate M Fibonacci numbers*/ if j>N then do; @.j=0 /*inialize the sum. */ do k=j-N for N /*sum the last N #.s*/ @.j=@.j+@.k /*add the [N-j]th #.*/ end /*k*/ end L=L @.j /*append this Fib num to the list*/ end /*j*/
say right(Fname,11)'[sum'right(N,3) "terms]:" strip(L) '...' /*show #s*/ return</lang> output when using the default input
Lucas[sum 2 terms]: 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127 24476 39603 64079 103682 167761 271443 439204 710647 1149851 ... fibonacci[sum 2 terms]: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 ... tribonacci[sum 3 terms]: 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 121415 223317 410744 755476 1389537 2555757 4700770 8646064 15902591 29249425 ... tetranacci[sum 4 terms]: 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 283953 547337 1055026 2033628 3919944 7555935 14564533 28074040 54114452 104308960 ... pentanacci[sum 5 terms]: 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513 400096 786568 1546352 3040048 5976577 11749641 23099186 45411804 89277256 175514464 ... hexanacci[sum 6 terms]: 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904 463968 920319 1825529 3621088 7182728 14247536 28261168 56058368 111196417 220567305 ... heptanacci[sum 7 terms]: 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888 495776 987568 1967200 3918592 7805695 15548665 30972384 61695880 122895984 244804400 ... octonacci[sum 8 terms]: 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005 510994 1019960 2035872 4063664 8111200 16190208 32316160 64504063 128752121 256993248 ... nonanacci[sum 9 terms]: 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328 518145 1035269 2068498 4132920 8257696 16499120 32965728 65866496 131603200 262947072 ... decanacci[sum 10 terms]: 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864 521472 1042432 2083841 4165637 8327186 16646200 33276064 66519472 132973664 265816832 ... undecanacci[sum 11 terms]: 1 1 2 4 8 16 32 64 128 256 512 1024 2047 4093 8184 16364 32720 65424 130816 261568 523008 1045760 2091008 4180992 8359937 16715781 33423378 66830392 133628064 267190704 ... dodecanacci[sum 12 terms]: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4095 8189 16376 32748 65488 130960 261888 523712 1047296 2094336 4188160 8375296 16748544 33492993 66977797 133939218 267845688 ... 13th-order[sum 13 terms]: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8191 16381 32760 65516 131024 262032 524032 1048000 2095872 4191488 8382464 16763904 33525760 67047424 134086657 268156933 ...
Ruby
<lang ruby>def anynacci(start_sequence, count)
n = start_sequence.length # Get the n-step for the type of fibonacci sequence result = start_sequence.dup # Create a new result array with the values copied from the array that was passed by reference (n+1..count).each do # Loop for the remaining results up to count result << result.last(n).reduce(:+) # Get the last n element from result and append its total to Array end result # Return result
end
naccis = { lucus: [2,1],
fibonacci: [1,1], tribonacci: [1,1,2], tetranacci: [1,1,2,4], pentanacci: [1,1,2,4,8], hexanacci: [1,1,2,4,8,16], heptanacci: [1,1,2,4,8,16,32], octonacci: [1,1,2,4,8,16,32,64], nonanacci: [1,1,2,4,8,16,32,64,128], decanacci: [1,1,2,4,8,16,32,64,128,256] }
def print_nacci(naccis, count=15)
puts naccis.map {|name, seq| "%12s : %p" % [name, anynacci(seq, count)]}
end
print_nacci(naccis)</lang>
- Output:
<lang ruby> lucus : [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843]
fibonacci : [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] tribonacci : [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136] tetranacci : [1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536] pentanacci : [1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930] hexanacci : [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617] heptanacci : [1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936] octonacci : [1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080] nonanacci : [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144] decanacci : [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172]
</lang>
Run BASIC
<lang runbasic>a = fib("1,1") a = fib("1,1,2") a = fib("1,1,2,4") a = fib("1,1,2,4,8") a = fib("1,1,2,4,8,16")
function fib(f$) dim f(20) while word$(f$,b+1,",") <> ""
b = b + 1 f(b) = val(word$(f$,b,","))
wend PRINT "Fibonacci:";b;"=>"; for i = b to 13 + b
print f(i-b+1);","; for j = (i - b) + 1 to i f(i+1) = f(i+1) + f(j) next j
next i print end function</lang>
Fibonacci:2=>1,1,2,3,5,8,13,21,34,55,89,144,233,377, Fibonacci:3=>1,1,2,4,7,13,24,44,81,149,274,504,927,1705, Fibonacci:4=>1,1,2,4,8,15,29,56,108,208,401,773,1490,2872, Fibonacci:5=>1,1,2,4,8,16,31,61,120,236,464,912,1793,3525, Fibonacci:6=>1,1,2,4,8,16,32,63,125,248,492,976,1936,3840,
Rust
<lang Rust> // Works with 0.9 fn fibonacci(max: uint, mut list: ~[int]) -> ~[int] { if list.len() == 0 { list = ~[0,1]; // If the list is empty, give it 0 and 1 as first to items } else if list.len() == max { return list; }
// Get the last two items on the list let n1 = list.len() - 1; // Last item let n2 = list.len() - 2; // Second-to-last item
let f1 = *list.iter().nth(n1).unwrap(); // Get the (n-1)th item let f2 = *list.iter().nth(n2).unwrap(); // get the (n-2)th item
// Add them together and push the sum onto the list! list.push(f1 + f2);
// Get the next number with the new list return fibonacci(max, list) } </lang>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func array integer: bonacci (in array integer: start, in integer: arity, in integer: length) is func
result var array integer: bonacciSequence is 0 times 0; local var integer: sum is 0; var integer: index is 0; begin bonacciSequence := start[.. length]; while length(bonacciSequence) < length do sum := 0; for index range max(1, length(bonacciSequence) - arity + 1) to length(bonacciSequence) do sum +:= bonacciSequence[index]; end for; bonacciSequence &:= [] (sum); end while; end func;
const proc: print (in string: name, in array integer: sequence) is func
local var integer: index is 0; begin write((name <& ":") rpad 12); for index range 1 to pred(length(sequence)) do write(sequence[index] <& ", "); end for; writeln(sequence[length(sequence)]); end func;
const proc: main is func
begin print("Fibonacci", bonacci([] (1, 1), 2, 10)); print("Tribonacci", bonacci([] (1, 1), 3, 10)); print("Tetranacci", bonacci([] (1, 1), 4, 10)); print("Lucas", bonacci([] (2, 1), 2, 10)); end func;</lang>
- Output:
Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 Tribonacci: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149 Tetranacci: 1, 1, 2, 4, 8, 15, 29, 56, 108, 208 Lucas: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76
Tcl
<lang tcl>package require Tcl 8.6
proc fibber {args} {
coroutine fib[incr ::fibs]=[join $args ","] apply {fn {
set n [info coroutine] foreach f $fn { if {![yield $n]} return set n $f } while {[yield $n]} { set fn [linsert [lreplace $fn 0 0] end [set n [+ {*}$fn]]] }
} ::tcl::mathop} $args
}
proc print10 cr {
for {set i 1} {$i <= 10} {incr i} {
lappend out [$cr true]
} puts \[[join [lappend out ...] ", "]\] $cr false
} puts "FIBONACCI" print10 [fibber 1 1] puts "TRIBONACCI" print10 [fibber 1 1 2] puts "TETRANACCI" print10 [fibber 1 1 2 4] puts "LUCAS" print10 [fibber 2 1]</lang>
- Output:
FIBONACCI [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...] TRIBONACCI [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ...] TETRANACCI [1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...] LUCAS [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, ...]
XPL0
<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations
proc Nacci(N, F0); \Generate Fibonacci N-step sequence int N, \step size
F0; \array of first N values
int I, J; def M = 10; \number of members in the sequence int F(M); \Fibonacci sequence [for I:= 0 to M-1 do \for all the members of the sequence...
[if I < N then F(I):= F0(I) \initialize sequence else [F(I):= 0; \sum previous members to get member I for J:= 1 to N do F(I):= F(I) + F(I-J); ]; IntOut(0, F(I)); ChOut(0, ^ ); ];
CrLf(0); ];
[Text(0, " Fibonacci: "); Nacci(2, [1, 1]);
Text(0, "Tribonacci: "); Nacci(3, [1, 1, 2]); Text(0, "Tetranacci: "); Nacci(4, [1, 1, 2, 4]); Text(0, " Lucas: "); Nacci(2, [2, 1]);
]</lang>
Output:
Fibonacci: 1 1 2 3 5 8 13 21 34 55 Tribonacci: 1 1 2 4 7 13 24 44 81 149 Tetranacci: 1 1 2 4 8 15 29 56 108 208 Lucas: 2 1 3 4 7 11 18 29 47 76