Fibonacci n-step number sequences: Difference between revisions

← Older edit

Fibonacci n-step number sequences (view source)

Revision as of 21:16, 22 April 2024

164,877 bytes added , 1 month ago

Added various BASIC dialects (Chipmunk Basic, QBasic, and QB64)

Jjuanhdez

2,130

edits

Revision as of 08:30, 26 May 2012 (view source) rosettacode>Spoon! (→‎{{header\|Python}}: added generator solution) ← Older edit		Latest revision as of 21:16, 22 April 2024 (view source) Jjuanhdez (talk \| contribs) (Added various BASIC dialects (Chipmunk Basic, QBasic, and QB64))
(280 intermediate revisions by more than 100 users not shown)
Line 1: {{~~draft~~ task}} These number series are an expansion of the ordinary [[Fibonacci sequence]] where: # For <math>n = 2</math> we have the Fibonacci sequence; with initial values <math>[1, 1]</math> and <math>F_k^2 = F_{k-1}^2 + F_{k-2}^2</math> # For <math>n = 3</math> we have the tribonacci sequence; with initial values <math>[1, 1, 2]</math> and <math>F_k^3 = F_{k-1}^3 + F_{k-2}^3 + F_{k-3}^3</math> # For <math>n = 4</math> we have the tetranacci sequence; with initial values <math>[1, 1, 2, 4]</math> and <math>F_k^4 = F_{k-1}^4 + F_{k-2}^4 + F_{k-3}^4 + F_{k-4}^4</math><br>... # For general <math>n>2</math> we have the Fibonacci <math>n</math>-step sequence - <math>F_k^n</math>; with initial values of the first <math>n</math> values of the <math>(n-1)</math>'th Fibonacci <math>n</math>-step sequence <math>F_k^{n-1}</math>; and <math>k</math>'th value of this <math>n</math>'th sequence being <math>F_k^n = \sum_{i=1}^{(n)} {F_{k-i}^{(n)}}</math> For small values of <math>n</math>, [[wp:Number prefix#Greek_series\|Greek numeric prefixes]] are sometimes used to individually name each series. :::: {\| style="text-align: left;" border="4" cellpadding="2" cellspacing="2" \|+ Fibonacci <math>n</math>-step sequences \|- style="background-color: rgb(255, 204, 255);" ! <math>n</math> !! Series name !! Values \|- \| 2 \|\| fibonacci \|\| 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... Line 31: \| 10 \|\| decanacci \|\| 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ... \|} ~~<br>~~ Allied sequences can be generated where the initial values are changed: : '''The [[wp:Lucas number\|Lucas series]]''' sums the two ~~preceeding~~preceding values like the fibonacci series for <math>n=2</math> but uses <math>[2, 1]</math> as its initial values. <!-- Lucas numbers, Lucas number, Lucas series [added to make searches easier.] --> ~~;The task is to:~~ # Write a function to generate Fibonacci n-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. <br> ;Task: # Write a function to generate Fibonacci <math>n</math>-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.:~~ ;Related tasks: * [[Fibonacci sequence]] *   [[Fibonacci sequence]] * [http://mathworld.wolfram.com/Fibonaccin-StepNumber.html Wolfram Mathworld] *   [http://mathworld.wolfram.com/Fibonaccin-StepNumber.html Wolfram Mathworld] * [[Hofstadter Q sequence‎]] *   [[Hofstadter Q sequence‎]] *   [[Leonardo numbers]] ;Also see: *   [https://www.youtube.com/watch?v=PeUbRXnbmms Lucas Numbers - Numberphile] (Video) *   [https://www.youtube.com/watch?v=fMJflV_GUpU Tribonacci Numbers (and the Rauzy Fractal) - Numberphile] (Video) *   [[wp:Lucas number\|Wikipedia, Lucas number]] *   [http://mathworld.wolfram.com/FibonacciNumber.html MathWorld, Fibonacci Number] *   [http://www.math-cs.ucmo.edu/~curtisc/articles/howardcooper/genfib4.pdf Some identities for r-Fibonacci numbers] *   [[oeis:A000045\|OEIS Fibonacci numbers]] *   [[oeis:A000032\|OEIS Lucas numbers]] <br><br> =={{header\|11l}}== {{trans\|Python: Callable class}} <syntaxhighlight lang="11l">T Fiblike Int addnum [Int] memo F (start) .addnum = start.len .memo = copy(start) F ()(n) X.try R .memo[n] X.catch IndexError V ans = sum((n - .addnum .< n).map(i -> (.)(i))) .memo.append(ans) R ans V fibo = Fiblike([1, 1]) print((0.<10).map(i -> fibo(i))) V lucas = Fiblike([2, 1]) print((0.<10).map(i -> lucas(i))) L(n, name) zip(2..10, ‘fibo tribo tetra penta hexa hepta octo nona deca’.split(‘ ’)) V fibber = Fiblike([1] [+] (0 .< n - 1).map(i -> Int(2 ^ i))) print(‘n=#2, #5nacci -> #. ...’.format(n, name, (0.<15).map(i -> String(@fibber(i))).join(‘ ’)))</syntaxhighlight> {{out}} <pre> [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 ... </pre> =={{header\|360 Assembly}}== <syntaxhighlight lang="360asm">* Fibonacci n-step number sequences - 14/04/2020 FIBONS CSECT USING FIBONS,R13 base register B 72(R15) skip savearea DC 17F'0' savearea SAVE (14,12) save previous context ST R13,4(R15) link backward ST R15,8(R13) link forward LR R13,R15 set addressability LA R6,2 i=2 DO WHILE=(C,R6,LE,=F'7') do i=2 to 7 ST R6,IR ir=i IF C,R6,EQ,=F'7' THEN if i=7 then - Lucas LA R0,2 2 ST R0,IR ir=2 ENDIF , endif LA R0,1 1 ST R0,T t(1)=1 IF C,R6,EQ,=F'7' THEN if i=7 then - Lucas LA R0,2 2 ST R0,T t(1)=2 ENDIF , endif LA R0,1 1 ST R0,T+4 t(2)=1 LA R7,3 j=3 DO WHILE=(C,R7,LE,=A(NMAX)) do j=3 to nmax SR R0,R0 0 ST R0,SUM sum=0 LR R11,R7 j S R11,IR j-ir LR R8,R7 k=j BCTR R8,0 k=j-1 DO WHILE=(CR,R8,GE,R11) do k=j-1 to j-ir by -1 IF LTR,R8,P,R8 THEN if k>0 then LR R1,R8 k SLA R1,2 ~ L R2,T-4(R1) t(k) L R1,SUM sum AR R1,R2 + ST R1,SUM sum=sum+t(k) ENDIF , endif BCTR R8,0 k-- ENDDO , enddo k L R0,SUM sum LR R1,R7 j SLA R1,2 ~ ST R0,T-4(R1) t(j)=sum LA R7,1(R7) j++ ENDDO , enddo j MVC PG,=CL120' ' clear buffer LA R9,PG @buffer LR R1,R6 i BCTR R1,0 i-1 MH R1,=H'5' ~ LA R4,BONACCI-5(R1) @bonacci(i-1) MVC 0(5,R9),0(R4) output bonacci(i-1) LA R9,5(R9) @buffer IF C,R6,NE,=F'7' THEN if i<>7 then MVC 0(7,R9),=C'nacci: ' output 'nacci: ' ELSE , else MVC 0(7,R9),=C' : ' output ' : ' ENDIF , endif LA R9,7(R9) @buffer LA R7,1 j=1 DO WHILE=(C,R7,LE,=A(NMAX)) do j=1 to nmax LR R1,R7 j SLA R1,2 ~ L R2,T-4(R1) t(j) XDECO R2,XDEC edit t(j) MVC 0(6,R9),XDEC+6 output t(j) LA R9,6(R9) @buffer LA R7,1(R7) j++ ENDDO , enddo j XPRNT PG,L'PG print buffer LA R6,1(R6) i++ ENDDO , enddo i L R13,4(0,R13) restore previous savearea pointer RETURN (14,12),RC=0 restore registers from calling sav NMAX EQU 18 sequence length BONACCI DC CL5' fibo',CL5'tribo',CL5'tetra',CL5'penta',CL5' hexa' DC CL5'lucas' bonacci(6) IR DS F ir SUM DS F sum T DS (NMAX)F t(nmax) XDEC DS CL12 temp for xdeco PG DS CL120 buffer REGEQU END FIBONS</syntaxhighlight> {{out}} <pre> fibonacci: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 tribonacci: 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 tetranacci: 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 pentanacci: 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 hexanacci: 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 lucas : 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 </pre> =={{header\|ACL2}}== <syntaxhighlight 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))))))</syntaxhighlight> Output: <pre>> (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)</pre> =={{header\|Action!}}== <syntaxhighlight lang="action!">DEFINE MAX="15" PROC GenerateSeq(CARD ARRAY init BYTE nInit CARD ARRAY seq BYTE nSeq) CARD next BYTE i,j,n IF nInit<nSeq THEN n=nInit ELSE n=nSeq FI FOR i=0 TO n-1 DO seq(i)=init(i) OD FOR i=n TO nSeq-1 DO next=0 FOR j=i-nInit TO i-1 DO next==+seq(j) OD seq(i)=next OD RETURN PROC PrintSeq(CHAR ARRAY name CARD ARRAY seq BYTE n) BYTE i PrintF("%S=[",name) FOR i=0 TO n-1 DO PrintC(seq(i)) IF i<n-1 THEN Print(" ") ELSE PrintE("]") FI OD RETURN PROC SetInverseVideo(CHAR ARRAY text) BYTE i FOR i=1 TO text(0) DO text(i)=text(i) OR $80 OD RETURN PROC Test(CHAR ARRAY name CARD ARRAY init CARD ARRAY nInit BYTE nSeq) CARD ARRAY seq(MAX) SetInverseVideo(name) GenerateSeq(init,nInit,seq,nSeq) PrintSeq(name,seq,nSeq) RETURN PROC Main() CARD ARRAY fibInit=[1 1 2 4 8 16 32 64 128 256 512] CARD ARRAY lucInit=[2 1] Test("lucas",lucInit,2,MAX) Test("fibonacci",fibInit,2,MAX) Test("tribonacci",fibInit,3,MAX) Test("tetranacci",fibInit,4,MAX) Test("pentanacci",fibInit,5,MAX) Test("hexanacci",fibInit,6,MAX) Test("heptanacci",fibInit,7,MAX) Test("octanacci",fibInit,8,MAX) Test("nonanacci",fibInit,9,MAX) Test("decanacci",fibInit,10,MAX) RETURN</syntaxhighlight> {{out}} [https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Fibonacci_n-step_number_sequences.png Screenshot from Atari 8-bit computer] <pre> lucas=[2 1 3 4 7 11 18 29 47 76 123 19 9 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] octanacci=[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] </pre> =={{header\|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. <syntaxhighlight 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;</syntaxhighlight> The implementation is quite straightforward. <syntaxhighlight 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;</syntaxhighlight> Finally, we actually generate some sequences, as required by the task. For convenience, we define a procedure Print that outputs a sequence, <syntaxhighlight 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;</syntaxhighlight> The output: <pre>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 )</pre> =={{header\|ALGOL 68}}== <syntaxhighlight lang="algol68"># returns an array of the first required count elements of an a n-step fibonacci sequence # # the initial values are taken from the init array # PROC n step fibonacci sequence = ( []INT init, INT required count )[]INT: BEGIN [ 1 : required count ]INT result; []INT initial values = init[ AT 1 ]; INT step = UPB initial values; # install the initial values # FOR n TO step DO result[ n ] := initial values[ n ] OD; # calculate the rest of the sequence # FOR n FROM step + 1 TO required count DO result[ n ] := 0; FOR p FROM n - step TO n - 1 DO result[ n ] +:= result[ p ] OD OD; result END; # required count # # prints the elements of a sequence # PROC print sequence = ( STRING legend, []INT sequence )VOID: BEGIN print( ( legend, ":" ) ); FOR e FROM LWB sequence TO UPB sequence DO print( ( " ", whole( sequence[ e ], 0 ) ) ) OD; print( ( newline ) ) END; # print sequence # # print some sequences # print sequence( "fibonacci ", n step fibonacci sequence( ( 1, 1 ), 10 ) ); print sequence( "tribonacci ", n step fibonacci sequence( ( 1, 1, 2 ), 10 ) ); print sequence( "tetrabonacci", n step fibonacci sequence( ( 1, 1, 2, 4 ), 10 ) ); print sequence( "lucus ", n step fibonacci sequence( ( 2, 1 ), 10 ) ) </syntaxhighlight> {{out}} <pre> fibonacci : 1 1 2 3 5 8 13 21 34 55 tribonacci : 1 1 2 4 7 13 24 44 81 149 tetrabonacci: 1 1 2 4 8 15 29 56 108 208 lucus : 2 1 3 4 7 11 18 29 47 76 </pre> =={{header\|APL}}== {{works with\|Dyalog APL}} <syntaxhighlight lang="apl">nStep ← {⊃(1↓⊢,+/)⍣(⍺-1)⊢⍵} nacci ← 20⌈¯2+⍳ ↑((⍳10)nStep¨⊂)¨(nacci¨2 3 4),⊂2 1</syntaxhighlight> {{out}} <pre>1 1 2 3 5 8 13 21 34 55 1 1 2 4 7 13 24 44 81 149 1 1 2 4 8 15 29 56 108 208 2 1 3 4 7 11 18 29 47 76</pre> =={{header\|AppleScript}}== ===Functional=== <syntaxhighlight lang="applescript">use AppleScript version "2.4" use framework "Foundation" use scripting additions -- Start sequence -> Number of terms -> terms -- takeNFibs :: [Int] -> Int -> [Int] on takeNFibs(xs, n) script go on \|λ\|(xs, n) if 0 < n and 0 < length of xs then cons(head(xs), ¬ \|λ\|(append(tail(xs), {sum(xs)}), n - 1)) else {} end if end \|λ\| end script go's \|λ\|(xs, n) end takeNFibs -- fibInit :: Int -> [Int] on fibInit(n) script powerOfTwo on \|λ\|(x) 2 ^ x as integer end \|λ\| end script cons(1, map(powerOfTwo, enumFromToInt(0, n - 2))) end fibInit -- TEST --------------------------------------------------- on run set intTerms to 15 script series on \|λ\|(s, n) justifyLeft(12, space, s & "nacci") & " -> " & ¬ showJSON(takeNFibs(fibInit(n), intTerms)) end \|λ\| end script set strTable to unlines(zipWith(series, ¬ words of ("fibo tribo tetra penta hexa hepta octo nona deca"), ¬ enumFromToInt(2, 10))) justifyLeft(12, space, "Lucas ") & " -> " & ¬ showJSON(takeNFibs({2, 1}, intTerms)) & linefeed & strTable end run -- GENERIC FUNCTIONS -------------------------------------- -- Append two lists. -- append (++) :: [a] -> [a] -> [a] -- append (++) :: String -> String -> String on append(xs, ys) xs & ys end append -- cons :: a -> [a] -> [a] on cons(x, xs) if list is class of xs then {x} & xs else x & xs end if end cons -- enumFromToInt :: Int -> Int -> [Int] on enumFromToInt(m, n) if m ≤ n then set lst to {} repeat with i from m to n set end of lst to i end repeat return lst else return {} end if end enumFromToInt -- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs) tell mReturn(f) set v to startValue set lng to length of xs repeat with i from 1 to lng set v to \|λ\|(v, item i of xs, i, xs) end repeat return v end tell end foldl -- head :: [a] -> a on head(xs) if xs = {} then missing value else item 1 of xs end if end head -- justifyLeft :: Int -> Char -> String -> String on justifyLeft(n, cFiller, strText) if n > length of strText then text 1 thru n of (strText & replicate(n, cFiller)) else strText end if end justifyLeft -- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: First-class m => (a -> b) -> m (a -> b) on mReturn(f) if class of f is script then f else script property \|λ\| : f end script end if end mReturn -- map :: (a -> b) -> [a] -> [b] on map(f, xs) tell mReturn(f) set lng to length of xs set lst to {} repeat with i from 1 to lng set end of lst to \|λ\|(item i of xs, i, xs) end repeat return lst end tell end map -- min :: Ord a => a -> a -> a on min(x, y) if y < x then y else x end if end min -- Egyptian multiplication - progressively doubling a list, appending -- stages of doubling to an accumulator where needed for binary -- assembly of a target length -- replicate :: Int -> a -> [a] on replicate(n, a) set out to {} if n < 1 then return out set dbl to {a} repeat while (n > 1) if (n mod 2) > 0 then set out to out & dbl set n to (n div 2) set dbl to (dbl & dbl) end repeat return out & dbl end replicate -- showJSON :: a -> String on showJSON(x) set c to class of x if (c is list) or (c is record) then set ca to current application set {json, e} to ca's NSJSONSerialization's ¬ dataWithJSONObject:x options:0 \|error\|:(reference) if json is missing value then e's localizedDescription() as text else (ca's NSString's alloc()'s ¬ initWithData:json encoding:(ca's NSUTF8StringEncoding)) as text end if else if c is date then "\"" & ((x - (time to GMT)) as «class isot» as string) & ".000Z" & "\"" else if c is text then "\"" & x & "\"" else if (c is integer or c is real) then x as text else if c is class then "null" else try x as text on error ("«" & c as text) & "»" end try end if end showJSON -- sum :: [Num] -> Num on sum(xs) script add on \|λ\|(a, b) a + b end \|λ\| end script foldl(add, 0, xs) end sum -- tail :: [a] -> [a] on tail(xs) set blnText to text is class of xs if blnText then set unit to "" else set unit to {} end if set lng to length of xs if 1 > lng then missing value else if 2 > lng then unit else if blnText then text 2 thru -1 of xs else rest of xs end if end if end tail -- unlines :: [String] -> String on unlines(xs) set {dlm, my text item delimiters} to ¬ {my text item delimiters, linefeed} set str to xs as text set my text item delimiters to dlm str end unlines -- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] on zipWith(f, xs, ys) set lng to min(length of xs, length of ys) if 1 > lng then return {} set lst to {} tell mReturn(f) repeat with i from 1 to lng set end of lst to \|λ\|(item i of xs, item i of ys) end repeat return lst end tell end zipWith </syntaxhighlight> {{Out}} <pre>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]</pre> ===Simple=== <syntaxhighlight lang="applescript">-- Parameters: -- n: …nacci step size as integer. Alternatively "Lucas". -- F: Maximum …nacci index required. (0-based.) on fibonacciNStep(n, F) script o property sequence : {0} end script if (n is "Lucas") then set {n, item 1 of o's sequence} to {2, 2} -- F1 (if included) is always 1. if (F > 0) then set end of o's sequence to 1 -- F2 (ditto) is F0 + F1. if (F > 1) then set end of o's sequence to (beginning of o's sequence) + (end of o's sequence) -- Each further number up to and including Fn is twice the number preceding it. if (n > F) then set n to F repeat (n - 2) times set end of o's sequence to (end of o's sequence) 2 end repeat -- Beyond Fn, each number is twice the one preceding it, minus the number n places before that. set nBeforeEnd to -(n + 1) repeat (F - n) times set end of o's sequence to (end of o's sequence) * 2 - (item nBeforeEnd of o's sequence) end repeat return o's sequence end fibonacciNStep -- Test code: set maxF to 15 -- Length of sequence required after the initial 0 or 2. set seriesNames to {missing value, "fibonacci: ", "tribonacci: ", "tetranacci: ", "pentanacci: ", ¬ "hexanacci: ", "heptanacci: ", "octonacci: ", "nonanacci: ", "decanacci: "} set output to {} set astid to AppleScript's text item delimiters set AppleScript's text item delimiters to ", " repeat with nacciSize from 2 to 10 set end of output to (item nacciSize of seriesNames) & fibonacciNStep(nacciSize, maxF) & " …" end repeat set end of output to "Lucas: " & fibonacciNStep("lucas", maxF) & " …" set AppleScript's text item delimiters to linefeed set output to output as text set AppleScript's text item delimiters to astid return output</syntaxhighlight> {{output}} <syntaxhighlight lang="applescript">"fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 … tribonacci: 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136 … tetranacci: 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536 … pentanacci: 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930 … hexanacci: 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617 … heptanacci: 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936 … octonacci: 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080 … nonanacci: 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144 … decanacci: 0, 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, 1364 …"</syntaxhighlight> =={{header\|Arturo}}== <syntaxhighlight lang="arturo">naccis: #[ lucas: [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] ] anyNacci: function [start, count][ n: size start result: new start do.times: count-n -> result: result ++ sum last.n:n result return join.with:", " to [:string] result ] loop naccis [k,v][ print [pad (k ++ ":") 12 anyNacci v 15] ]</syntaxhighlight> {{out}} <pre> 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</pre> =={{header\|AutoHotkey}}== <syntaxhighlight 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 }</syntaxhighlight> '''Output:''' <pre>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</pre> =={{header\|AWK}}== <syntaxhighlight lang="awk"> function sequence(values, howmany) { init_length = length(values) for (i=init_length + 1; i<=howmany; i++) { values[i] = 0 for (j=1; j<=init_length; j++) { values[i] += values[i-j] } } result = "" for (i in values) { result = result values[i] " " } delete values return result } # print some sequences END { a[1] = 1; a[2] = 1 print("fibonacci :\t",sequence(a, 10)) a[1] = 1; a[2] = 1; a[3] = 2 print("tribonacci :\t",sequence(a, 10)) a[1] = 1 ; a[2] = 1 ; a[3] = 2 ; a[4] = 4 print("tetrabonacci :\t",sequence(a, 10)) a[1] = 2; a[2] = 1 print("lucas :\t\t",sequence(a, 10)) } </syntaxhighlight> '''Output:''' <pre> fibonacci : 1 1 2 3 5 8 13 21 34 55 tribonacci : 1 1 2 4 7 13 24 44 81 149 tetrabonacci : 1 1 2 4 8 15 29 56 108 208 lucas : 2 1 3 4 7 11 18 29 47 76 </pre> =={{header\|BASIC}}== ==={{header\|BASIC256}}=== <syntaxhighlight lang="basic256"># Rosetta Code problem: https://www.rosettacode.org/wiki/Fibonacci_n-step_number_sequences # by Jjuanhdez, 06/2022 arraybase 1 print " fibonacci =>"; dim a = {1,1} call fib (a) print " tribonacci =>"; dim a = {1,1,2} call fib (a) print " tetranacci =>"; dim a = {1,1,2,4} call fib (a) print " pentanacci =>"; dim a = {1,1,2,4,8} call fib (a) print " hexanacci =>"; dim a = {1,1,2,4,8,16} call fib (a) print " heptanacci =>"; dim a = {1,1,2,4,8,16,32} call fib (a) print " octonacci =>"; dim a = {1,1,2,4,8,16,32,64} call fib (a) print " nonanacci =>"; dim a = {1,1,2,4,8,16,32,64,128} call fib (a) print " decanacci =>"; dim a = {1,1,2,4,8,16,32,64,128,256} call fib (a) print " lucas =>"; dim a = {2,1} call fib (a) end subroutine fib (a) dim f(24) fill 0 b = 0 for x = 1 to a[?] b += 1 f[x] = a[x] next x for i = b to 13 + b print rjust(f[i-b+1], 5); if i <> 13 + b then print ","; else print ", ..." for j = (i-b+1) to i f[i+1] = f[i+1] + f[j] next j next i end subroutine</syntaxhighlight> {{out}} <pre> fibonacci => 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... tribonacci => 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, ... tetranacci => 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, ... pentanacci => 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ... hexanacci => 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, ... heptanacci => 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, ... octonacci => 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, ... nonanacci => 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, ... decanacci => 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, ... lucas => 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...</pre> ==={{header\|Chipmunk Basic}}=== {{trans\|BASIC256}} {{works with\|Chipmunk Basic\|3.6.4}} <syntaxhighlight lang="vbnet">100 sub fib(a()) 110 erase f 120 dim f(24) 130 b = 0 140 for x = 1 to ubound(a) 150 b = b+1 160 f(x) = a(x) 170 next x 180 for i = b to 12+b 190 print using "#### ";f(i-b+1); 200 for j = (i-b+1) to i 210 f(i+1) = f(i+1)+f(j) 220 next j 230 next i 240 print 250 end sub 260 cls 270 print " fibonacci =>"; 280 dim a(2) 290 a(1) = 1 : a(2) = 1 300 fib(a()) 310 print " tribonacci =>"; 320 dim a(3) 330 a(1) = 1 : a(2) = 1 : a(3) = 2 340 fib(a()) 350 print " tetranacci =>"; 360 dim c(4) 370 c(1) = 1 : c(2) = 1 : c(3) = 2 : c(4) = 4 380 fib(c()) 390 print " lucas =>"; 400 dim d(2) 410 d(1) = 2 : d(2) = 1 420 fib(d()) 430 end</syntaxhighlight> ==={{header\|QBasic}}=== {{trans\|BASIC256}} {{works with\|QBasic\|1.1}} {{works with\|QuickBasic\|4.5}} {{works with\|QB64}} <syntaxhighlight lang="qbasic">DECLARE SUB fib (a() AS INTEGER) CLS PRINT " fibonacci =>"; DIM a(1 TO 2) AS INTEGER a(1) = 1: a(2) = 1 CALL fib(a()) PRINT " tribonacci =>"; DIM b(1 TO 3) AS INTEGER b(1) = 1: b(2) = 1: b(3) = 2 CALL fib(b()) PRINT " tetranacci =>"; DIM c(1 TO 4) AS INTEGER c(1) = 1: c(2) = 1: c(3) = 2: c(4) = 4 CALL fib(c()) PRINT " lucas =>"; DIM d(1 TO 2) AS INTEGER d(1) = 2: d(2) = 1 CALL fib(d()) END SUB fib (a() AS INTEGER) DIM f(24) b = 0 FOR x = 1 TO UBOUND(a) b = b + 1 f(x) = a(x) NEXT x FOR i = b TO 12 + b PRINT USING "#### "; f(i - b + 1); FOR j = (i - b + 1) TO i f(i + 1) = f(i + 1) + f(j) NEXT j NEXT i END SUB</syntaxhighlight> ==={{header\|QB64}}=== {{trans\|BASIC256}} <syntaxhighlight lang="qbasic">Rem $Dynamic Cls Print " fibonacci =>"; Dim a(1 To 2) As Integer a(1) = 1 a(2) = 1 Call fib(a()) Print " tribonacci =>"; ReDim _Preserve a(1 To 3) a(3) = 2 Call fib(a()) Print " tetranacci =>"; ReDim _Preserve a(1 To 4) a(4) = 4 Call fib(a()) Print " lucas =>"; ReDim a(1 To 2) a(1) = 2 a(2) = 1 Call fib(a()) End Sub fib (a() As Integer) Dim f(24) b = 0 For x = 1 To UBound(a) b = b + 1 f(x) = a(x) Next x For i = b To 12 + b Print Using "#### "; f(i - b + 1); For j = (i - b + 1) To i f(i + 1) = f(i + 1) + f(j) Next j Next i End Sub</syntaxhighlight> =={{header\|Batch File}}== <syntaxhighlight lang="dos"> @echo off echo Fibonacci Sequence: call:nfib 1 1 echo. echo Tribonacci Sequence: call:nfib 1 1 2 echo. echo Tetranacci Sequence: call:nfib 1 1 2 4 echo. echo Lucas Numbers: call:nfib 2 1 echo. pause>nul exit /b :nfib setlocal enabledelayedexpansion for %%i in (%) do ( set /a count+=1 set seq=!seq! %%i ) set "seq=%seq% ^\| " set n=-%count% set /a n+=1 for %%i in (%) do ( set F!n!=%%i set /a n+=1 ) for /l %%i in (1,1,10) do ( set /a termstart=%%i-%count%% set /a termend=%%i-1 for /l %%j in (!termstart!,1,!termend!) do ( set /a F%%i+=!F%%j! ) set seq=!seq! !F%%i! ) echo %seq% endlocal exit /b </syntaxhighlight> {{out}} <pre> Fibonacci Sequence: 1 1 \| 2 3 5 8 13 21 34 55 89 144 Tribonacci Sequence: 1 1 2 \| 4 7 13 24 44 81 149 274 504 927 Tetranacci Sequence: 1 1 2 4 \| 8 15 29 56 108 208 401 773 1490 2872 Lucas Numbers: 2 1 \| 3 4 7 11 18 29 47 76 123 199 </pre> =={{header\|BBC BASIC}}== The BBC BASIC '''SUM''' function is useful here. <syntaxhighlight 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</syntaxhighlight> '''Output:''' <pre> 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 ... </pre> =={{header\|Befunge}}== <syntaxhighlight lang="befunge">110p>>55+109"iccanaceD"22099v v9013"Tetranacci"9014"Lucas"< >"iccanobirT"2109"iccanobiF"v >>:#,_0p20p0>:01-\2>#v0>#g<>> ^_@#:,+55$_^ JH v`1:v#\p03< _$.1+:77+`^vg03:_0g+>\:1+#^ 50p-\30v v\<>\30g1-\^$$_:1- 05g04\g< >`#^_:40p30g0>^!:g</syntaxhighlight> {{out}} <pre>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 Lucas 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 Decanacci 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172</pre> =={{header\|Bracmat}}== {{trans\|PicoLisp}} <syntaxhighlight lang="bracmat">( ( nacci = Init Cnt N made tail . ( plus = n . !arg:#%?n ?arg&!n+plus$!arg \| 0 ) & !arg:(?Init.?Cnt) & !Init:? [?N & !Init:?made & !Cnt+-1!N:?times & -1+-1!N:?M & whl ' ( !times+-1:~<0:?times & !made:? [!M ?tail & !made plus$!tail:?made ) & !made ) & ( pad = len w . @(!arg:? [?len) & @(" ":? [!len ?w) & !w !arg ) & (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) (lucas.2 1) : ?L & whl ' ( !L:(?name.?Init) ?L & out$(str$(pad$!name ": ") nacci$(!Init.12)) ) );</syntaxhighlight> Output: <pre> 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 pentanacci: 1 1 2 4 8 16 31 61 120 236 464 912 hexanacci: 1 1 2 4 8 16 32 63 125 248 492 976 heptanacci: 1 1 2 4 8 16 32 64 127 253 504 1004 octonacci: 1 1 2 4 8 16 32 64 128 255 509 1016 nonanacci: 1 1 2 4 8 16 32 64 128 256 511 1021 decanacci: 1 1 2 4 8 16 32 64 128 256 512 1023 lucas: 2 1 3 4 7 11 18 29 47 76 123 199</pre> =={{header\|BQN}}== <syntaxhighlight lang="bqn">NStep ← ⊑(1↓⊢∾+´)∘⊢⍟⊣ Nacci ← (2⋆0∾↕)∘(⊢-1˙) >((↕10) NStep¨ <)¨ (Nacci¨ 2‿3‿4) ∾ <2‿1</syntaxhighlight> {{out}} <pre>┌─ ╵ 1 1 2 3 5 8 13 21 34 55 1 1 2 4 7 13 24 44 81 149 1 1 2 4 8 15 29 56 108 208 2 1 3 4 7 11 18 29 47 76 ┘</pre> =={{header\|C}}== <syntaxhighlight lang="c">/* 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; }</syntaxhighlight> Output: <pre> 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 </pre> =={{header\|C sharp\|C#}}== <syntaxhighlight lang="csharp">using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Fibonacci { class Program { static void Main(string[] args) { PrintNumberSequence("Fibonacci", GetNnacciNumbers(2, 10)); PrintNumberSequence("Lucas", GetLucasNumbers(10)); PrintNumberSequence("Tribonacci", GetNnacciNumbers(3, 10)); PrintNumberSequence("Tetranacci", GetNnacciNumbers(4, 10)); Console.ReadKey(); } private static IList<ulong> GetLucasNumbers(int length) { IList<ulong> seedSequence = new List<ulong>() { 2, 1 }; return GetFibLikeSequence(seedSequence, length); } private static IList<ulong> GetNnacciNumbers(int seedLength, int length) { return GetFibLikeSequence(GetNacciSeed(seedLength), length); } private static IList<ulong> GetNacciSeed(int seedLength) { IList<ulong> seedSquence = new List<ulong>() { 1 }; for (uint i = 0; i < seedLength - 1; i++) { seedSquence.Add((ulong)Math.Pow(2, i)); } return seedSquence; } private static IList<ulong> GetFibLikeSequence(IList<ulong> seedSequence, int length) { IList<ulong> sequence = new List<ulong>(); int count = seedSequence.Count(); if (length <= count) { sequence = seedSequence.Take((int)length).ToList(); } else { sequence = seedSequence; for (int i = count; i < length; i++) { ulong num = 0; for (int j = 0; j < count; j++) { num += sequence[sequence.Count - 1 - j]; } sequence.Add(num); } } return sequence; } private static void PrintNumberSequence(string Title, IList<ulong> numbersequence) { StringBuilder output = new StringBuilder(Title).Append(" "); foreach (long item in numbersequence) { output.AppendFormat("{0}, ", item); } Console.WriteLine(output.ToString()); } } }</syntaxhighlight> <pre>Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, Lucas 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, Tribonacci 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, Tetranacci 1, 1, 2, 4, 8, 15, 29, 56, 108, 208,</pre> =={{header\|C++}}== <syntaxhighlight 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 ; }</syntaxhighlight> Output: <pre>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 ... </pre> ===Alternate Version=== This version focuses on a clean, simple class that adapts to any pair of starting numbers and any order. Rather than summing over all history every time, it uses an O(1) incremental update to a running total. Thus, performance remains essentially unchanged even for very large orders. <syntaxhighlight lang="cpp"> #include <iostream> #include <vector> // This class forms a simple 'generator', where operator() returns the next // element in the series. It uses a small sliding window buffer to minimize // storage overhead. class nacci_t { std::vector< int > history; unsigned windex; // sliding window index unsigned rindex; // result index int running_sum; // sum of values in sliding window public: nacci_t( unsigned int order, int a0 = 1, int a1 = 1 ) : history( order + 1 ), windex( 0 ), rindex( order - 1 ), running_sum( a0 + a1 ) { // intialize sliding window history[order - 1] = a0; history[order - 0] = a1; } int operator()() { int result = history[ rindex ]; // get 'nacci number to return running_sum -= history[ windex ]; // old 'nacci falls out of window history[ windex ] = running_sum; // new 'nacci enters the window running_sum += running_sum; // new 'nacci added to the sum if ( ++windex == history.size() ) windex = 0; if ( ++rindex == history.size() ) rindex = 0; return result; } }; int main() { for ( unsigned int i = 2; i <= 10; ++i ) { nacci_t nacci( i ); // fibonacci sequence std::cout << "nacci( " << i << " ): "; for ( int j = 0; j < 10; ++j ) std::cout << " " << nacci(); std::cout << std::endl; } for ( unsigned int i = 2; i <= 10; ++i ) { nacci_t lucas( i, 2, 1 ); // Lucas sequence std::cout << "lucas( " << i << " ): "; for ( int j = 0; j < 10; ++j ) std::cout << " " << lucas(); std::cout << std::endl; } } </syntaxhighlight> =={{header\|Clojure}}== <syntaxhighlight 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]))</syntaxhighlight> {{out}} <pre>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)</pre> =={{header\|CLU}}== <syntaxhighlight lang="clu">% Find the Nth element of a given n-step sequence n_step = proc (seq: sequence[int], n: int) returns (int) a: array[int] := sequence[int]$s2a(seq) for i: int in int$from_to(1,n) do sum: int := 0 for x: int in array[int]$elements(a) do sum := sum + x end array[int]$reml(a) array[int]$addh(a,sum) end return(array[int]$bottom(a)) end n_step % Generate the initial sequence for the Fibonacci n-step sequence of length N anynacci = proc (n: int) returns (sequence[int]) a: array[int] := array[int]$[1] for i: int in int$from_to(0,n-2) do array[int]$addh(a, 2*i) end return(sequence[int]$a2s(a)) end anynacci % Given an initial sequence, print the first N elements print_n = proc (seq: sequence[int], n: int) po: stream := stream$primary_output() for i: int in int$from_to(0, n-1) do stream$putright(po, int$unparse(n_step(seq, i)), 4) end stream$putl(po, "") end print_n start_up = proc () s = struct[name: string, seq: sequence[int]] po: stream := stream$primary_output() seqs: array[s] := array[s]$[ s${name: "Fibonacci", seq: anynacci(2)}, s${name: "Tribonacci", seq: anynacci(3)}, s${name: "Tetranacci", seq: anynacci(4)}, s${name: "Lucas", seq: sequence[int]$[2,1]} ] for seq: s in array[s]$elements(seqs) do stream$putleft(po, seq.name, 12) print_n(seq.seq, 10) end end start_up</syntaxhighlight> {{out}} <pre>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</pre> =={{header\|Common Lisp}}== <syntaxhighlight lang="lisp"> (defun gen-fib (lst m) "Return the first m members of a generalized Fibonacci sequence using lst as initial values and the length of lst as step." (let ((l (- (length lst) 1))) (do ((fib-list (reverse lst) (cons (loop for i from 0 to l sum (nth i fib-list)) fib-list)) (c (+ l 2) (+ c 1))) ((> c m) (reverse fib-list))))) (defun initial-values (n) "Return the initial values of the Fibonacci n-step sequence" (cons 1 (loop for i from 0 to (- n 2) collect (expt 2 i)))) (defun start () (format t "Lucas series: ~a~%" (gen-fib '(2 1) 10)) (loop for i from 2 to 4 do (format t "Fibonacci ~a-step sequence: ~a~%" i (gen-fib (initial-values i) 10))))</syntaxhighlight> {{out}} <pre>Lucas series: (2 1 3 4 7 11 18 29 47 76) Fibonacci 2-step sequence: (1 1 2 3 5 8 13 21 34 55) Fibonacci 3-step sequence: (1 1 2 4 7 13 24 44 81 149) Fibonacci 4-step sequence: (1 1 2 4 8 15 29 56 108 208)</pre> =={{header\|D}}== ===Basic Memoization=== ~~<lang d>import std.stdio, std.algorithm, std.range, std.conv;~~ <syntaxhighlight lang="d">void main() { import std.stdio, std.algorithm, std.range, std.conv; const(int)[] memo; ~~void main() {~~ ~~int[] memo;~~ size_t addNum; void setHead(int[] head) nothrow @safe { memo = head; addNum = head.length; } int fibber(in size_t n) /nothrow/ @safe { if (n >= memo.length) memo ~= iota(n - addNum, n).map!fibber().~~reduce!q{a + b}()~~sum; return memo[n]; } setHead([1, 1]); ~~iota(~~10).iota.map!fibber().writeln(); setHead([2, 1]); ~~iota(~~10).iota.map!fibber().writeln(); ~~auto~~const prefixes = "fibo tribo tetra penta hexa hepta octo nona deca"; foreach (immutable n, const name; ~~zip(iota(2, 11),~~ prefixes.split.enumerate()2)) { setHead(1 ~ iota(n - 1).map!q{2 ^^ a}().array()); ~~auto items~~ writefln("n=%2d, ~~iota(15).map!(i~~%5snacci =-> ~~text(fibber(i)))~~%(%d %) ...~~join(~~", ~~");~~n, name, ~~writefln("n=%2d,~~ ~~%5snacci~~ -> %s ~~...",~~ n, ~~name,~~ ~~items~~ 15.iota.map!fibber); } }</~~lang~~syntaxhighlight> {{out}} <pre>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55] Line 88 ⟶ 1,690: n=10, decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...</pre> ===~~Alternative~~Callable ~~Version~~Struct=== The output is similar. <~~lang~~syntaxhighlight 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/ @safe { this.memo = start.dup; this.addNum = start.length; } T opCall(in size_t n) /nothrow/ @safe { if (n >= memo.length) memo ~= iota(n - addNum, n) .map!(i => opCall(i))~~().reduce!q{a + b}();~~ .sum .to!int; return memo[n]; } Line 111 ⟶ 1,715: void main() { auto fibo = fiblike!int([1, 1]); ~~//writeln(~~iota(10).map!fibo~~())~~.writeln; ~~foreach (i; 0 .. 10)~~ ~~//write(fibo(i), " ");~~ ~~write(fibo.opCall(i), " ");~~ ~~writeln();~~ auto lucas = fiblike!int([2, 1]); ~~//writeln(~~iota(10).map!lucas~~())~~.writeln; ~~foreach (i; 0 .. 10)~~ const prefixes = "fibo tribo tetra penta hexa hepta octo nona deca"; ~~//write(lucas(i), " ");~~ foreach (immutable n, const name; prefixes.split.enumerate(2)) { ~~write(lucas.opCall(i), " ");~~ auto fib = fiblike!int(1 ~ iota(n - 1).map!q{2 ^^ a}.array); ~~writeln();~~ writefln("n=%2d, %5snacci -> %(%d %) ...", ~~auto prefixes = "fibo tribo tetra penta hexa hepta octo nona deca";~~ ~~foreach~~ ( n, name~~; zip(iota(2~~, ~~11), prefixes~~15.~~split()~~iota.map!fib)~~) {~~; ~~auto fib = fiblike!int(1 ~ iota(n-1).map!q{2 ^^ a}().array());~~ ~~//auto items = iota(15).map!(i => text(fib(i)))().join(" ");~~ ~~string[] items;~~ ~~foreach (i; 0 .. 15)~~ ~~//items ~= text(fib(i));~~ ~~items ~= text(fib.opCall(i));~~ ~~writefln("n=%2d, %5snacci -> %s ...", n,name, items.join(" "));~~ } }</~~lang~~syntaxhighlight> ===Struct With opApply=== The output is similar. <syntaxhighlight 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)) { auto fib = Fiblike!int(1 ~ iota(n - 1).map!q{2 ^^ a}.array); writefln("n=%2d, %5snacci -> %s", n, name, fib.takeApply(15)); } }</syntaxhighlight> ===Range Generator Version=== <syntaxhighlight lang="d">void main() { import std.stdio, std.algorithm, std.range, std.concurrency; immutable fibLike = (int[] tail) => new Generator!int({ foreach (x; tail) yield(x); foreach (immutable i; tail.length.iota.cycle) yield(tail[i] = tail.sum); }); foreach (seed; [[1, 1], [2, 1]]) fibLike(seed).take(10).writeln; immutable prefixes = "fibo tribo tetra penta hexa hepta octo nona deca"; foreach (immutable n, const name; prefixes.split.enumerate(2)) { auto fib = fibLike(1 ~ iota(n - 1).map!q{2 ^^ a}.array); writefln("n=%2d, %5snacci -> %(%s, %), ...", n, name, fib.take(15)); } }</syntaxhighlight> {{out}} <pre>[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, ...</pre> =={{header\|Delphi}}== See [[#Pascal]]. =={{header\|EasyLang}}== <syntaxhighlight> proc sequ n$ val[] n . . write n$ & ": " il = len val[] len val[] n for i = il + 1 to n for j = 1 to il val[i] += val[i - j] . . for v in val[] write v & " " . print "" . sequ "Fibonacci" [ 1 1 ] 10 sequ "Tribonacci" [ 1 1 2 ] 10 sequ "Tetrabonacci" [ 1 1 2 4 ] 10 sequ "Lucas" [ 2 1 ] 10 </syntaxhighlight> {{out}} <pre> Fibonacci: 1 1 2 3 5 8 13 21 34 55 Tribonacci: 1 1 2 4 7 13 24 44 81 149 Tetrabonacci: 1 1 2 4 8 15 29 56 108 208 Lucas: 2 1 3 4 7 11 18 29 47 76 </pre> =={{header\|EchoLisp}}== <syntaxhighlight lang="scheme"> ;; generate a recursive lambda() for a x-nacci ;; equip it with memoïzation ;; bind it to its name (define (make-nacci name seed) (define len (1+ (vector-length seed))) (define-global name `(lambda(n) (for/sum ((i (in-range (1- n) (- n ,len) -1))) (,name i)))) (remember name seed) name) (define nacci-family `( (Fibonacci #(1 1)) (Tribonacci #(1 1 2)) (Tetranacci #(1 1 2 4)) (Decanacci #(1 1 2 4 8 16 32 64 128 256)) (Random-😜-nacci ,(list->vector (take 6 (shuffle (iota 100))))) (Lucas #(2 1)))) (define (task naccis) (for ((nacci naccis)) (define-values (name seed) nacci) (make-nacci name seed) (printf "%s[%d] → %d" name (vector-length seed) (take name 16)))) </syntaxhighlight> {{out}} <pre> (task nacci-family ) Fibonacci[2] → (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987) Tribonacci[3] → (1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768) Tetranacci[4] → (1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671) Decanacci[10] → (1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336) Random-😜-nacci[6] → (95 52 16 48 59 56 326 557 1062 2108 4168 8277 16498 32670 64783 128504) Lucas[2] → (2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364) </pre> =={{header\|Elixir}}== {{trans\|Ruby}} <syntaxhighlight lang="elixir">defmodule RC do def anynacci(start_sequence, count) do n = length(start_sequence) anynacci(Enum.reverse(start_sequence), count-n, n) end def anynacci(seq, 0, _), do: Enum.reverse(seq) def anynacci(seq, count, n) do next = Enum.sum(Enum.take(seq, n)) anynacci([next\|seq], count-1, n) end end IO.inspect RC.anynacci([1,1], 15) 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] ] Enum.each(naccis, fn {name, list} -> :io.format("~11s: ", [name]) IO.inspect RC.anynacci(list, 15) end)</syntaxhighlight> {{out}} <pre> 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] </pre> =={{header\|Erlang}}== <syntaxhighlight lang="text"> -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]}. </syntaxhighlight> {{out}} <pre> 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] </pre> =={{header\|ERRE}}== <syntaxhighlight lang="erre"> PROGRAM FIBON ! ! for rosettacode.org ! DIM F[20] PROCEDURE FIB(TIPO$,F$) FOR I%=0 TO 20 DO F[I%]=0 END FOR B=0 LOOP Q=INSTR(F$,",") B=B+1 IF Q=0 THEN F[B]=VAL(F$) EXIT ELSE F[B]=VAL(MID$(F$,1,Q-1)) F$=MID$(F$,Q+1) END IF END LOOP PRINT(TIPO$;" =>";) FOR I=B TO 14+B DO IF I<>B THEN PRINT(",";) END IF PRINT(F[I-B+1];) FOR J=(I-B)+1 TO I DO F[I+1]=F[I+1]+F[J] END FOR END FOR PRINT END PROCEDURE BEGIN PRINT(CHR$(12);) ! CLS FIB("Fibonacci","1,1") FIB("Tribonacci","1,1,2") FIB("Tetranacci","1,1,2,4") FIB("Lucas","2,1") END PROGRAM </syntaxhighlight> =={{header\|F_Sharp\|F#}}== <syntaxhighlight lang="fsharp">let fibinit = Seq.append (Seq.singleton 1) (Seq.unfold (fun n -> Some(n, 2n)) 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</syntaxhighlight> Output <pre>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]</pre> =={{header\|Factor}}== <code>building</code> is a dynamic variable that refers to the sequence being built by <code>make</code>. This is useful when the next element of the sequence depends on previous elements. <syntaxhighlight lang="factor">USING: formatting fry kernel make math namespaces qw sequences ; : n-bonacci ( n initial -- seq ) [ [ [ , ] each ] [ length - ] [ length ] tri '[ building get _ tail sum , ] times ] { } make ; qw{ fibonacci tribonacci tetranacci lucas } { { 1 1 } { 1 1 2 } { 1 1 2 4 } { 2 1 } } [ 10 swap n-bonacci "%-10s %[%3d, %]\n" printf ] 2each</syntaxhighlight> {{out}} <pre> 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 } </pre> =={{header\|Forth}}== <syntaxhighlight lang="forth">: length @ ; \ length of an array is stored at its address : a{ here cell allot ; : } , here over - cell / over ! ; defer nacci : step ( a- i n -- a- i m ) >r 1- 2dup nacci r> + ; : steps ( a- i n -- m ) 0 tuck do step loop nip nip ; :noname ( a- i -- n ) over length over > \ if i is within the array if cells + @ \ fetch i...if not, else over length 1- steps \ get length of array for calling step and recurse then ; is nacci : show-nacci 11 1 do dup i nacci . loop cr drop ; ." fibonacci: " a{ 1 , 1 } show-nacci ." tribonacci: " a{ 1 , 1 , 2 } show-nacci ." tetranacci: " a{ 1 , 1 , 2 , 4 } show-nacci ." lucas: " a{ 2 , 1 } show-nacci </syntaxhighlight> {{out}} <pre>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 </pre> =={{header\|Fortran}}== <syntaxhighlight 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) = 2s(i-1) - s(i-(n+1)) end do end subroutine nacci end program f </syntaxhighlight> <pre> $ ./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 $ </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> =={{header\|FreeBASIC}}== <syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 ' Deduces the step, n, from the length of the dynamic array passed in ' and fills it out to 'size' elements Sub fibN (a() As Integer, size As Integer) Dim lb As Integer = LBound(a) Dim ub As Integer = UBound(a) Dim length As Integer = ub - lb + 1 If length < 2 OrElse length >= size Then Return ub = lb + size - 1 Redim Preserve a(lb To ub) Dim sum As Integer For i As Integer = lb + length to ub sum = 0 For j As Integer = 1 To Length sum += a(i - j) Next j a(i) = sum Next i End Sub Sub printSeries(a() As Integer, name_ As String) '' name is a keyword Print name_; " =>"; For i As Integer = LBound(a) To UBound(a) Print Using "####"; a(i); Print " "; Next Print End Sub Const size As Integer = 13 '' say Redim a(1 To 2) As Integer a(1) = 1 : a(2) = 1 fibN(a(), size) printSeries(a(), "fibonacci ") Redim Preserve a(1 To 3) a(3) = 2 fibN(a(), size) printSeries(a(), "tribonacci") Redim Preserve a(1 To 4) a(4) = 4 fibN(a(), size) printSeries(a(), "tetranacci") erase a Redim a(1 To 2) a(1) = 2 : a(2) = 1 fibN(a(), size) printSeries(a(), "lucas ") Print Print "Press any key to quit" Sleep</syntaxhighlight> {{out}} <pre> fibonacci => 1 1 2 3 5 8 13 21 34 55 89 144 233 tribonacci => 1 1 2 4 7 13 24 44 81 149 274 504 927 tetranacci => 1 1 2 4 8 15 29 56 108 208 401 773 1490 lucas => 2 1 3 4 7 11 18 29 47 76 123 199 322 </pre> =={{header\|FunL}}== <syntaxhighlight lang="funl">import util.TextTable native scala.collection.mutable.Queue def fibLike( init ) = q = Queue() for i <- init do q.enqueue( i ) def fib = q.enqueue( sum(q) ) q.dequeue() # fib() 0 # fib() def fibN( n ) = fibLike( [1] + [2^i \| i <- 0:n-1] ) val lucas = fibLike( [2, 1] ) t = TextTable() t.header( 'k', 'Fibonacci', 'Tribonacci', 'Tetranacci', 'Lucas' ) t.line() for i <- 1..5 t.rightAlignment( i ) seqs = (fibN(2), fibN(3), fibN(4), lucas) for k <- 1..10 t.row( ([k] + [seqs(i)(k) \| i <- 0:4]).toIndexedSeq() ) print( t )</syntaxhighlight> {{out}} <pre> +----+-----------+------------+------------+-------+ \| k \| Fibonacci \| Tribonacci \| Tetranacci \| Lucas \| +----+-----------+------------+------------+-------+ \| 1 \| 1 \| 1 \| 1 \| 2 \| \| 2 \| 1 \| 1 \| 1 \| 1 \| \| 3 \| 2 \| 2 \| 2 \| 3 \| \| 4 \| 3 \| 4 \| 4 \| 4 \| \| 5 \| 5 \| 7 \| 8 \| 7 \| \| 6 \| 8 \| 13 \| 15 \| 11 \| \| 7 \| 13 \| 24 \| 29 \| 18 \| \| 8 \| 21 \| 44 \| 56 \| 29 \| \| 9 \| 34 \| 81 \| 108 \| 47 \| \| 10 \| 55 \| 149 \| 208 \| 76 \| +----+-----------+------------+------------+-------+ </pre> =={{header\|Fōrmulæ}}== {{FormulaeEntry\|page=https://formulae.org/?script=examples/Fibonacci_n-step_number_sequences}} '''Solution''' According to the requirements, the program must generate a series, and the order (Fibonacci, Tribonacci, etc) should be determined according with the initial values. In this case, the number n indicates how many terms of the series will be generated. [[File:Fōrmulæ - Fibonacci n-step number sequences 01.png]] The following generates a Fibonacci series of 15 terms: [[File:Fōrmulæ - Fibonacci n-step number sequences 02.png]] [[File:Fōrmulæ - Fibonacci n-step number sequences 03.png]] The following generates a Lucas series of 15 terms: [[File:Fōrmulæ - Fibonacci n-step number sequences 04.png]] [[File:Fōrmulæ - Fibonacci n-step number sequences 05.png]] The following generates a Tribonacci series of 15 terms: [[File:Fōrmulæ - Fibonacci n-step number sequences 06.png]] [[File:Fōrmulæ - Fibonacci n-step number sequences 07.png]] '''Generating initial values.''' The initial values can be generated by the following function: [[File:Fōrmulæ - Fibonacci n-step number sequences 08.png]] Note that it is a recursive function, and it calls the previously defined function. It requires the initial values as a seed: (1, 1) for Fibonacci style (Fibonacci, Tribonacci, etc), and (2, 1) for Lucas style. The following generates the initial values for Fibonacci series. [[File:Fōrmulæ - Fibonacci n-step number sequences 09.png]] [[File:Fōrmulæ - Fibonacci n-step number sequences 10.png]] The following generates the initial values for Lucas series. [[File:Fōrmulæ - Fibonacci n-step number sequences 11.png]] [[File:Fōrmulæ - Fibonacci n-step number sequences 12.png]] '''Generating tables of series for Fibonacci and Lucas''' This generates a tables of series for Fibonacci (15 terms), for orders 2 to 10 (Fibonacci, Tribonacci, etc.) [[File:Fōrmulæ - Fibonacci n-step number sequences 13.png]] [[File:Fōrmulæ - Fibonacci n-step number sequences 14.png]] This generates a tables of series for Lucas (15 terms), for orders 2 to 15: [[File:Fōrmulæ - Fibonacci n-step number sequences 15.png]] [[File:Fōrmulæ - Fibonacci n-step number sequences 16.png]] =={{header\|Go}}== Solution using separate goroutines. <syntaxhighlight lang="go">package main import "fmt" func g(i []int, c chan<- int) { var sum int b := append([]int(nil), i...) // make a copy 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) // Note/warning: these goroutines are leaked. go g(s.i, c) for j := 0; j < 10; j++ { fmt.Print(" ", <-c) } fmt.Println() } }</syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|Groovy}}== =====Solution===== <syntaxhighlight lang="groovy">def fib = { List seed, int k=10 -> assert seed : "The seed list must be non-null and non-empty" assert seed.every { it instanceof Number } : "Every member of the seed must be a number" def n = seed.size() assert n > 1 : "The seed must contain at least two elements" List result = [] + seed if (k < n) { result[0..k] } else { (n..k).inject(result) { res, kk -> res << res[-n..-1].sum() } } }</syntaxhighlight> =====Test===== <syntaxhighlight lang="groovy">[ ' 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], ' lucas':[2,1], ].each { name, seed -> println "${name}: ${fib(seed,10)}" } println " lucas[0]: ${fib([2,1],0)}" println " tetra[3]: ${fib([1,1,2,4],3)}"</syntaxhighlight> {{out}} <pre> 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] lucas[0]: [2] tetra[3]: [1, 1, 2, 4]</pre> =={{header\|Haskell}}== <~~lang~~syntaxhighlight lang="haskell">import ~~Data~~Control.~~List~~Monad (~~tails~~zipWithM_) import ~~Control~~Data.~~Monad~~List (~~zipWithM_~~tails) fiblike :: ~~Int ->~~ [Integer] -> [Integer] fiblike n st = xs ~~where~~ where ~~xs = st ++ map (sum . take n) (tails xs)~~ xs = st <> map (sum . take n) (tails xs) n = length st nstep :: Int -> [Integer] nstep n = fiblike n $ take n $ 1 : iterate (2 ) 1 main :: IO () main = do mapM_ (print $. take 10 $. fiblike 2) [[1, 1], [2, 1]] zipWithM_ ~~print $ take 10 $ fiblike 2 [2,1]~~ ~~zipWithM_~~ ( \n name -> do ~~putStr (name ++ "nacci -> ")~~ putStr (name <> "nacci -> ") ~~print $ take 15 $ nstep n)~~ print $ take 15 $ nstep n ~~[2..] (words "fibo tribo tetra penta hexa hepta octo nona deca")</lang>~~ ) [2 ..] (words "fibo tribo tetra penta hexa hepta octo nona deca")</syntaxhighlight> {{out}} <pre> Line 165 ⟶ 2,508: 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] </pre> Or alternatively, without imports – using only the default Prelude: <syntaxhighlight lang="haskell">------------ FIBONACCI N-STEP NUMBER SEQUENCES ----------- nStepFibonacci :: Int -> [Int] nStepFibonacci = nFibs . (1 :) . fmap (2 ^) . enumFromTo 0 . subtract 2 nFibs :: [Int] -> [Int] nFibs ys@(z : zs) = z : nFibs (zs <> [sum ys]) --------------------------- TEST ------------------------- main :: IO () main = do putStrLn $ justifyLeft 12 ' ' "Lucas" <> "-> " <> show (take 15 (nFibs [2, 1])) (putStrLn . unlines) ( zipWith ( \s n -> justifyLeft 12 ' ' (s <> "naccci") <> ("-> " <> show (take 15 (nStepFibonacci n))) ) ( words "fibo tribo tetra penta hexa hepta octo nona deca" ) [2 ..] ) justifyLeft :: Int -> Char -> String -> String justifyLeft n c s = take n (s <> replicate n c)</syntaxhighlight> <pre>Lucas -> [2,1,3,4,7,11,18,29,47,76,123,199,322,521,843] fibonaccci -> [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610] tribonaccci -> [1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136] tetranaccci -> [1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536] pentanaccci -> [1,1,2,4,8,16,31,61,120,236,464,912,1793,3525,6930] hexanaccci -> [1,1,2,4,8,16,32,63,125,248,492,976,1936,3840,7617] heptanaccci -> [1,1,2,4,8,16,32,64,127,253,504,1004,2000,3984,7936] octonaccci -> [1,1,2,4,8,16,32,64,128,255,509,1016,2028,4048,8080] nonanaccci -> [1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144] decanaccci -> [1,1,2,4,8,16,32,64,128,256,512,1023,2045,4088,8172]</pre> or in terms of '''unfoldr''': {{Trans\|Python}} <syntaxhighlight lang="haskell">import Data.Bifunctor (second) import Data.List (transpose, uncons, unfoldr) ------------ FIBONACCI N-STEP NUMBER SEQUENCES ----------- a000032 :: [Int] a000032 = unfoldr (recurrence 2) [2, 1] nStepFibonacci :: Int -> [Int] nStepFibonacci = unfoldr <$> recurrence <> (($ 1 : fmap (2 ^) [0 ..]) . take) recurrence :: Int -> [Int] -> Maybe (Int, [Int]) recurrence n = ( fmap . second . flip (<>) . pure . sum . take n ) <> uncons --------------------------- TEST ------------------------- main :: IO () main = putStrLn $ "Recurrence relation sequences:\n\n" <> spacedTable justifyRight ( ("lucas:" : fmap show (take 15 a000032)) : zipWith ( \k n -> (k <> "nacci:") : fmap show (take 15 $ nStepFibonacci n) ) (words "fibo tribo tetra penta hexa hepta octo nona deca") [2 ..] ) ------------------------ FORMATTING ---------------------- spacedTable :: (Int -> Char -> String -> String) -> [[String]] -> String spacedTable aligned rows = let columnWidths = fmap (maximum . fmap length) (transpose rows) in unlines $ fmap (unwords . zipWith (`aligned` ' ') columnWidths) rows justifyRight :: Int -> Char -> String -> String justifyRight n c = (drop . length) <> (replicate n c <>)</syntaxhighlight> {{Out}} <pre>Recurrence relation sequences: 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</pre> =={{header\|Icon}} and {{header\|Unicon}}== Works in both languages: <syntaxhighlight lang="unicon">procedure main(A) every writes("F2:\t"\|right((fnsGen(1,1))\14,5) \| "\n") every writes("F3:\t"\|right((fnsGen(1,1,2))\14,5) \| "\n") every writes("F4:\t"\|right((fnsGen(1,1,2,4))\14,5) \| "\n") every writes("Lucas:\t"\|right((fnsGen(2,1))\14,5) \| "\n") every writes("F?:\t"\|right((fnsGen!A)\14,5) \| "\n") end procedure fnsGen(cache[]) n := cache every i := seq() do { if i > cache then every (put(cache,0),cache[i] +:= cache[i-n to i-1]) suspend cache[i] } end</syntaxhighlight> Output: <pre> ->fns 3 1 4 1 5 F2: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 F3: 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 F4: 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 Lucas: 2 1 3 4 7 11 18 29 47 76 123 199 322 521 F?: 3 1 4 1 5 14 25 49 94 187 369 724 1423 2797 -> </pre> A slightly longer version of <tt>fnsGen</tt> that reduces the memory footprint is: <syntaxhighlight lang="unicon">procedure fnsGen(cache[]) every i := seq() do { if i := (i > cache, cache) then { every (sum := 0) +:= !cache put(cache, sum) # cache only 'just enough' pop(cache) } suspend cache[i] } end</syntaxhighlight> The output is identical. =={{header\|J}}== '''Solution''':<syntaxhighlight lang="j"> nacci =: (] , +/@{.)^:(-@#@]`(-#)`])</syntaxhighlight> '''Example''' ''(Lucas)'':<syntaxhighlight lang="j"> 10 nacci 2 1 NB. Lucas series, first 10 terms 2 1 3 4 7 11 18 29 47 76</syntaxhighlight> '''Example''' ''(extended 'nacci series)'':<syntaxhighlight 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 ✓</syntaxhighlight> =={{header\|Java}}== '''Code:''' <syntaxhighlight 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(); } } }</syntaxhighlight> Output: <pre>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</pre> =={{header\|JavaScript}}== ===ES5=== <syntaxhighlight 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();</syntaxhighlight> {{out}} <pre>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</pre> ===ES6=== <syntaxhighlight lang="javascript">(() => { 'use strict'; // Start sequence -> Number of terms -> terms // takeNFibs :: [Int] -> Int -> [Int] const takeNFibs = (xs, n) => { const go = (xs, n) => 0 < n && 0 < xs.length ? ( cons( head(xs), go( append(tail(xs), [sum(xs)]), n - 1 ) ) ) : []; return go(xs, n); }; // fibInit :: Int -> [Int] const fibInit = n => cons( 1, map(x => Math.pow(2, x), enumFromToInt(0, n - 2) ) ); // TEST ----------------------------------------------------------------- const main = () => { const intTerms = 15, strTable = unlines( zipWith( (s, n) => justifyLeft(12, ' ', s + 'nacci') + ' -> ' + showJSON( takeNFibs(fibInit(n), intTerms) ), words('fibo tribo tetra penta hexa hepta octo nona deca'), enumFromToInt(2, 10) ) ); return justifyLeft(12, ' ', 'Lucas ') + ' -> ' + showJSON(takeNFibs([2, 1], intTerms)) + '\n' + strTable; }; // GENERIC FUNCTIONS ---------------------------- // append (++) :: [a] -> [a] -> [a] // append (++) :: String -> String -> String const append = (xs, ys) => xs.concat(ys); // cons :: a -> [a] -> [a] const cons = (x, xs) => Array.isArray(xs) ? ( [x].concat(xs) ) : (x + xs); // enumFromToInt :: Int -> Int -> [Int] const enumFromToInt = (m, n) => m <= n ? iterateUntil( x => n <= x, x => 1 + x, m ) : []; // head :: [a] -> a const head = xs => xs.length ? xs[0] : undefined; // iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a] const iterateUntil = (p, f, x) => { const vs = [x]; let h = x; while (!p(h))(h = f(h), vs.push(h)); return vs; }; // justifyLeft :: Int -> Char -> String -> String const justifyLeft = (n, cFiller, s) => n > s.length ? ( s.padEnd(n, cFiller) ) : s; // map :: (a -> b) -> [a] -> [b] const map = (f, xs) => xs.map(f); // showJSON :: a -> String const showJSON = x => JSON.stringify(x); // sum :: [Num] -> Num const sum = xs => xs.reduce((a, x) => a + x, 0); // tail :: [a] -> [a] const tail = xs => 0 < xs.length ? xs.slice(1) : []; // unlines :: [String] -> String const unlines = xs => xs.join('\n'); // words :: String -> [String] const words = s => s.split(/\s+/); // zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] const zipWith = (f, xs, ys) => Array.from({ length: Math.min(xs.length, ys.length) }, (_, i) => f(xs[i], ys[i], i)); // MAIN --- return main(); })();</syntaxhighlight> <pre>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]</pre> =={{header\|jq}}== {{Works with\|jq\|1.4}} <syntaxhighlight lang="jq"># Input: the initial array def nacci(arity; len): arity as $arity \| len as $len \| reduce range(length; $len) as $i (.; ([0, (length - $arity)] \| max ) as $lower \| . + [ .[ ($lower) : length] \| add] ) ; def fib(arity; len): arity as $arity \| len as $len \| [1,1] \| nacci($arity; $arity) \| nacci($arity; $len) ; def lucas(arity; len): arity as $arity \| len as $len \| [2,1] \| nacci($arity; $arity) \| nacci($arity; $len) ;</syntaxhighlight> '''Example''': <syntaxhighlight lang="jq">def main: (range(2; 11) \| "fib(\(.)): \(fib(.; 15))"), (range(2; 11) \| "lucas(\(.)): \(lucas(.; 15))") ; main</syntaxhighlight> {{Out}} $ jq -M -r -n -f fibonacci_n-step.jq ... [as for JavaScript] ... =={{header\|Julia}}== This solution provides a generalized Fibonacci iterator that is then made specific to particular sorts of series by setting its parameters. <tt>NFib</tt> is the type that holds the series parameters. <tt>FState</tt> contains the iteration state. The methods <tt>start</tt>, <tt>end</tt> and <tt>next</tt>, provided for these new types, enable Julia's iteration mechanics upon them. This iterator is implemented using an n-element circular list that contains the previous values of the sequence that are needed to calculate the current value. To do this without clumsy initialization logic, the "seed" sequence consists of the <math>n</math> values prior to <math>k=1</math> rather than the first <math>n</math> values. For example the (2 step) Fibonacci sequence is <math>F_{k+1}=F_{k}+F_{k-1}</math> with <math>F_{-1}=1</math> and <math>F_{0}=0</math> rather than <math>F_{1}=1</math> and <math>F_{2}=1</math>. See [https://cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html Primes in Fibonacci n-step and Lucas n-step Sequences] for further details. '''Generalized Fibonacci Iterator Definition''' <syntaxhighlight lang="julia"> type NFib{T<:Integer} n::T klim::T seeder::Function end type FState a::Array{BigInt,1} adex::Integer k::Integer end function Base.start{T<:Integer}(nf::NFib{T}) a = nf.seeder(nf.n) adex = 1 k = 1 return FState(a, adex, k) end function Base.done{T<:Integer}(nf::NFib{T}, fs::FState) fs.k > nf.klim end function Base.next{T<:Integer}(nf::NFib{T}, fs::FState) f = sum(fs.a) fs.a[fs.adex] = f fs.adex = rem1(fs.adex+1, nf.n) fs.k += 1 return (f, fs) end </syntaxhighlight> '''Specification of the n-step Fibonacci Iterator''' The seeding for this series of sequences is <math>F_{1-n} = 1</math> and <math>F_{2-n} \ldots F_{0}=0</math>. <syntaxhighlight lang="julia"> function fib_seeder{T<:Integer}(n::T) a = zeros(BigInt, n) a[1] = one(BigInt) return a end function fib{T<:Integer}(n::T, k::T) NFib(n, k, fib_seeder) end </syntaxhighlight> '''Specification of the Rosetta Code n-step Lucas Iterator''' This iterator produces the task description's version of the Lucas Sequence ([https://oeis.org/A000032 OEIS A000032]) and its generalization to n-steps as was done by some of the other solutions to this task. The seeding for this series of sequences is <math>F_{1-n} = 3</math>, <math>F_{2-n} = -1</math> and, for <math>n > 2</math>, <math>F_{3-n} \ldots F_{0}=0</math>. <syntaxhighlight lang="julia"> function luc_rc_seeder{T<:Integer}(n::T) a = zeros(BigInt, n) a[1] = 3 a[2] = -1 return a end function luc_rc{T<:Integer}(n::T, k::T) NFib(n, k, luc_rc_seeder) end </syntaxhighlight> '''Specification of the MathWorld n-step Lucas Iterator''' This iterator produces the Mathworld version of the Lucas Sequence ([http://mathworld.wolfram.com/LucasNumber.html Lucas Number] and [https://oeis.org/A000204 OEIS A000204]) and its generalization to n-steps according to Mathworld ([http://mathworld.wolfram.com/Lucasn-StepNumber.html Lucas n-Step Number] and [https://cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html Primes in Fibonacci n-step and Lucas n-step Sequences]). The seeding for this series of sequences is <math>F_{0} = n</math> and <math>F_{1-n} \ldots F_{-1}=-1</math>. <syntaxhighlight lang="julia"> function luc_seeder{T<:Integer}(n::T) a = -ones(BigInt, n) a[end] = big(n) return a end function luc{T<:Integer}(n::T, k::T) NFib(n, k, luc_seeder) end </syntaxhighlight> '''Main''' <syntaxhighlight lang="julia"> lo = 2 hi = 10 klim = 16 print("n-step Fibonacci for n = (", lo, ",", hi) println(") up to k = ", klim, ":") for i in 2:10 print(@sprintf("%5d => ", i)) for j in fib(i, klim) print(j, " ") end println() end println() print("n-step Rosetta Code Lucas for n = (", lo, ",", hi) println(") up to k = ", klim, ":") for i in 2:10 print(@sprintf("%5d => ", i)) for j in luc_rc(i, klim) print(j, " ") end println() end println() print("n-step MathWorld Lucas for n = (", lo, ",", hi) println(") up to k = ", klim, ":") for i in 2:10 print(@sprintf("%5d => ", i)) for j in luc(i, klim) print(j, " ") end println() end </syntaxhighlight> {{out}} <pre> n-step Fibonacci for n = (2,10) up to k = 16: 2 => 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 3 => 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 4 => 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 5 => 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 6 => 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 7 => 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 8 => 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 9 => 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 10 => 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 n-step Rosetta Code Lucas for n = (2,10) up to k = 16: 2 => 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 3 => 2 1 3 6 10 19 35 64 118 217 399 734 1350 2483 4567 8400 4 => 2 1 3 6 12 22 43 83 160 308 594 1145 2207 4254 8200 15806 5 => 2 1 3 6 12 24 46 91 179 352 692 1360 2674 5257 10335 20318 6 => 2 1 3 6 12 24 48 94 187 371 736 1460 2896 5744 11394 22601 7 => 2 1 3 6 12 24 48 96 190 379 755 1504 2996 5968 11888 23680 8 => 2 1 3 6 12 24 48 96 192 382 763 1523 3040 6068 12112 24176 9 => 2 1 3 6 12 24 48 96 192 384 766 1531 3059 6112 12212 24400 10 => 2 1 3 6 12 24 48 96 192 384 768 1534 3067 6131 12256 24500 n-step MathWorld Lucas for n = (2,10) up to k = 16: 2 => 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3 => 1 3 7 11 21 39 71 131 241 443 815 1499 2757 5071 9327 17155 4 => 1 3 7 15 26 51 99 191 367 708 1365 2631 5071 9775 18842 36319 5 => 1 3 7 15 31 57 113 223 439 863 1695 3333 6553 12883 25327 49791 6 => 1 3 7 15 31 63 120 239 475 943 1871 3711 7359 14598 28957 57439 7 => 1 3 7 15 31 63 127 247 493 983 1959 3903 7775 15487 30847 61447 8 => 1 3 7 15 31 63 127 255 502 1003 2003 3999 7983 15935 31807 63487 9 => 1 3 7 15 31 63 127 255 511 1013 2025 4047 8087 16159 32287 64511 10 => 1 3 7 15 31 63 127 255 511 1023 2036 4071 8139 16271 32527 65023 </pre> =={{header\|Kotlin}}== <syntaxhighlight lang="scala">// version 1.1.2 fun fibN(initial: IntArray, numTerms: Int) : IntArray { val n = initial.size require(n >= 2 && numTerms >= 0) val fibs = initial.copyOf(numTerms) if (numTerms <= n) return fibs for (i in n until numTerms) { var sum = 0 for (j in i - n until i) sum += fibs[j] fibs[i] = sum } return fibs } fun main(args: Array<String>) { val names = arrayOf("fibonacci", "tribonacci", "tetranacci", "pentanacci", "hexanacci", "heptanacci", "octonacci", "nonanacci", "decanacci") val initial = intArrayOf(1, 1, 2, 4, 8, 16, 32, 64, 128, 256) println(" n name values") var values = fibN(intArrayOf(2, 1), 15).joinToString(", ") println("%2d %-10s %s".format(2, "lucas", values)) for (i in 0..8) { values = fibN(initial.sliceArray(0 until i + 2), 15).joinToString(", ") println("%2d %-10s %s".format(i + 2, names[i], values)) } }</syntaxhighlight> {{out}} <pre> n name values 2 lucas 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843 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 </pre> =={{header\|Lua}}== <syntaxhighlight lang="lua">function nStepFibs (seq, limit) local iMax, sum = #seq - 1 while #seq < limit do sum = 0 for i = 0, iMax do sum = sum + seq[#seq - i] end table.insert(seq, sum) end return seq end local fibSeqs = { {name = "Fibonacci", values = {1, 1} }, {name = "Tribonacci", values = {1, 1, 2} }, {name = "Tetranacci", values = {1, 1, 2, 4}}, {name = "Lucas", values = {2, 1} } } for _, sequence in pairs(fibSeqs) do io.write(sequence.name .. ": ") print(table.concat(nStepFibs(sequence.values, 10), " ")) end</syntaxhighlight> {{out}} <pre>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</pre> =={{header\|Maple}}== <syntaxhighlight lang="maple">numSequence := proc(initValues :: Array) local n, i, values; n := numelems(initValues); values := copy(initValues); for i from (n+1) to 15 do values(i) := add(values[i-n..i-1]); end do; return values; end proc: initValues := Array([1]): for i from 2 to 10 do initValues(i) := add(initValues): printf ("nacci(%d): %a\n", i, convert(numSequence(initValues), list)); end do: printf ("lucas: %a\n", convert(numSequence(Array([2, 1])), list));</syntaxhighlight> {{out}} <pre> 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, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843] </pre> =={{header\|Mathematica}} / {{header\|Wolfram Language}}== <syntaxhighlight 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 </syntaxhighlight> Output: <pre> 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 </pre> =={{header\|Nim}}== {{trans\|Python}} <syntaxhighlight lang="nim">import sequtils, strutils proc fiblike(start: seq[int]): auto = var memo = start proc fibber(n: int): int = if n < memo.len: return memo[n] else: var ans = 0 for i in n-start.len ..< n: ans += fibber(i) memo.add ans return ans return fibber let fibo = fiblike(@[1,1]) echo toSeq(0..9).map(fibo) let lucas = fiblike(@[2,1]) echo toSeq(0..9).map(lucas) for n, name in items({2: "fibo", 3: "tribo", 4: "tetra", 5: "penta", 6: "hexa", 7: "hepta", 8: "octo", 9: "nona", 10: "deca"}): var se = @[1] for i in 0..n-2: se.add(1 shl i) let fibber = fiblike(se) echo "n = ", align($n, 2), ", ", align(name, 5), "nacci -> ", toSeq(0..14).mapIt($fibber(it)).join(" "), " ..."</syntaxhighlight> Output: <pre>@[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 ...</pre> =={{header\|Ol}}== We will use lazy lists, so can get any amount of n-nacci numbers. <syntaxhighlight lang="scheme"> (define (n-fib-iterator ll) (cons (car ll) (lambda () (n-fib-iterator (append (cdr ll) (list (fold + 0 ll))))))) </syntaxhighlight> Testing: <syntaxhighlight lang="scheme"> (print "2, fibonacci : " (ltake (n-fib-iterator '(1 1)) 15)) (print "3, tribonacci: " (ltake (n-fib-iterator '(1 1 2)) 15)) (print "4, tetranacci: " (ltake (n-fib-iterator '(1 1 2 4)) 15)) (print "5, pentanacci: " (ltake (n-fib-iterator '(1 1 2 4 8)) 15)) (print "2, lucas : " (ltake (n-fib-iterator '(2 1)) 15)) ; ==> 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) 2, lucas : (2 1 3 4 7 11 18 29 47 76 123 199 322 521 843) </syntaxhighlight> =={{header\|PARI/GP}}== The function <code>gen</code> 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. <syntaxhighlight 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)))</syntaxhighlight> {{out}} <pre>2 [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] 3 [1, 1, 2, 4, 7, 13, 24, 44, 81, 149] 4 [1, 1, 2, 4, 8, 15, 29, 56, 108, 208] 5 [1, 1, 2, 4, 8, 16, 31, 61, 120, 236] 6 [1, 1, 2, 4, 8, 16, 32, 63, 125, 248] 7 [1, 1, 2, 4, 8, 16, 32, 64, 127, 253] 8 [1, 1, 2, 4, 8, 16, 32, 64, 128, 255] 9 [1, 1, 2, 4, 8, 16, 32, 64, 128, 256] 10 [1, 1, 2, 4, 8, 16, 32, 64, 128, 256]</pre> =={{header\|Pascal}}== {{works with\|Free_Pascal}} <syntaxhighlight 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.</syntaxhighlight> Output: <pre>% ./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</pre> ===Alternative=== With the same output like above. A little bit like C++ alternative, but using only one idx and the observation, that Sum[n] = 2Sum[n-1]- Sum[n-stepSize]. There is no need to do so in Terms of speed, since fib(100) is out of reach using Uint64. Fib(n)/Fib(n-1) tends to the golden ratio = 1.618... 1.618^100 > 2^64 {{works with\|Free_Pascal}} <syntaxhighlight lang="pascal"> program FibbonacciN (output); {$IFNDEF FPC} {$APPTYPE CONSOLE} {$ENDIF} const MAX_Nacci = 10; No_of_examples = 11;// max 90; (golden ratio)^No < 2^64 Name: array[2..11] of string = ('Fibonacci: ', 'Tribonacci: ', 'Tetranacci: ', 'Pentanacci: ', 'Hexanacci: ', 'Heptanacci: ', 'Octonacci: ', 'Nonanacci: ', 'Decanacci: ', 'Lucas: ' ); type tfibIdx = 0..MAX_Nacci; tNacVal = Uint64;// longWord tNacci = record ncSum : tNacVal; ncLastFib : array[tFibIdx] of tNacVal; ncNextIdx : array[tFibIdx] of tFibIdx; ncIdx : tFibIdx; ncValue : tFibIdx; end; function CreateNacci(n: tFibIdx): TNacci; var i : tFibIdx; sum :tNacVal; begin //With result do with CreateNacci do begin ncLastFib[0] := 1; ncLastFib[1] := 1; For i := 2 to n-1 do ncLastFib[i] := ncLastFib[i-1] 2; Sum := 0; For i := 0 to n-1 do sum := sum +ncLastFib[i]; ncSum := Sum; //No need to do a compare //inc(idx); //if idx>= n then // idx := 0; //idx := nextIdx[idx] For i := 0 to n-2 do ncNextIdx[i] := i+1; ncNextIdx[n-1] := 0; ncIdx := 0; end; end; function LehmerCreate:TNacci; begin with LehmerCreate do begin ncLastFib[0] := 2; ncLastFib[1] := 1; ncSum := 3; ncNextIdx[0] := 1; ncNextIdx[1] := 0; ncIdx := 0; end; end; function NextNacci(var Nacci:tNacci):tNacVal; var NewSum :tNacVal; begin with Nacci do begin NewSum := 2ncSum- ncLastFib[ncIdx]; ncLastFib[ncIdx] := ncSum; ncIdx := ncNextIdx[ncIdx]; NextNacci := ncSum; ncSum := NewSum; end; end; var Nacci : tNacci; j, k: integer; BEGIN for j := 2 to 10 do begin Nacci := CreateNacci(j); write (Name[j]); For k := 0 to j-1 do write(Nacci.ncLastFib[k],' '); For k := j to No_of_examples-1 do write(NextNacci(Nacci),' '); writeln; end; write (Name[11]); j := 2; Nacci := LehmerCreate; For k := 0 to j-1 do write(Nacci.ncLastFib[k],' '); For k := j to No_of_examples-1 do write(NextNacci(Nacci),' '); writeln; END.</syntaxhighlight> =={{header\|PascalABC.NET}}== ===Unfold=== I first define a high order function to generate infinite sequences given a lambda and a seed. <syntaxhighlight lang="pascal"> // unfold infinite sequences. Nigel Galloway: September 8th., 2022 function unfold<gN,gG>(n:Func<gG,(gN,gG)>; g:gG): sequence of gN; begin var (x,r):=n(g); yield x; yield sequence unfold(n,r); end; function unfold<gN,gG>(n:Func<array of gG,(gN,array of gG)>;params g:array of gG): sequence of gN := unfold(n,g); </syntaxhighlight> ===The Task=== Like the Pascal above but not iffy, not loopy, and not as long! <syntaxhighlight lang="pascal"> // Fibonacci n-step number sequences. Nigel Galloway: September 8th., 2022 var nFib:=function(n:array of biginteger): (biginteger,array of biginteger)->(n.First,n[1:].Append(n.Sum).ToArray); begin var fib:=unfold(nFib,1bi,1bi); fib.Take(20).Println; var tri:=unfold(nFib,fib.Take(3)); tri.Take(20).Println; var tet:=unfold(nFib,tri.Take(4)); tet.Take(20).Println; var pen:=unfold(nFib,tet.Take(5)); pen.Take(20).Println; var hex:=unfold(nFib,pen.Take(6)); hex.Take(20).Println; var hep:=unfold(nFib,hex.Take(7)); hep.Take(20).Println; var oct:=unfold(nFib,hep.Take(8)); oct.Take(20).Println; var non:=unfold(nFib,oct.Take(9)); non.Take(20).Println; var dec:=unfold(nFib,non.Take(10)); dec.Take(20).Println; var luc:=unfold(nFib,2bi,1bi); luc.Take(20).Println; end. </syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|Perl}}== <syntaxhighlight lang="perl">use strict; use warnings; use feature <say signatures>; no warnings 'experimental'; use List::Util <max sum>; sub fib_n ($n = 2, $xs = [1], $max = 100) { my @xs = @$xs; while ( $max > (my $len = @xs) ) { push @xs, sum @xs[ max($len - $n, 0) .. $len-1 ]; } @xs } say $_-1 . ': ' . join ' ', (fib_n $_)[0..19] for 2..10; say "\nLucas: " . join ' ', fib_n(2, [2,1], 20);</syntaxhighlight> {{out}} <pre>1: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 2: 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 3: 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 4: 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513 5: 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904 6: 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888 7: 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005 8: 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328 9: 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864 Lucas: 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349</pre> =={{header\|Phix}}== <!--<syntaxhighlight lang="phix">(phixonline)--> <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> <span style="color: #008080;">function</span> <span style="color: #000000;">nacci_noo</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;"></span><span style="color: #000000;">l</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nacci_noo</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">nacci_noo</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">return</span> <span style="color: #000000;">res</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">constant</span> <span style="color: #000000;">names</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"lucas fibo tribo tetra penta hexa hepta octo nona deca"</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span> <span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nacci_noo</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%snacci: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">f</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <!--</syntaxhighlight>--> {{out}} <pre> lucasnacci: {2,1,3,4,7,11,18,29,47,76} 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} </pre> =={{header\|PHP}}== <syntaxhighlight 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"; } </syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|PicoLisp}}== <syntaxhighlight lang="picolisp">(de nacci (Init Cnt) (let N (length Init) (make (made Init) (do (- Cnt N) (link (apply + (tail N (made)))) ) ) ) )</syntaxhighlight> Test: <syntaxhighlight 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)</syntaxhighlight> =={{header\|PL/I}}== <syntaxhighlight 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 Lusas 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;</syntaxhighlight> Output: <pre> We have a Lucas 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 </pre> =={{header\|Powershell}}== <syntaxhighlight lang="powershell">#Create generator of extended fibonaci Function Get-ExtendedFibonaciGenerator($InitialValues ){ $Values = $InitialValues { #exhaust initial values first before calculating next values by summation if ($InitialValues.Length -gt 0) { $NextValue = $InitialValues[0] $Script:InitialValues = $InitialValues \| Select -Skip 1 return $NextValue } $NextValue = $Values \| Measure-Object -Sum \| Select -ExpandProperty Sum $Script:Values = @($Values \| Select-Object -Skip 1) + @($NextValue) $NextValue }.GetNewClosure() } </syntaxhighlight> Example of invocation to generate up to decanaci <syntaxhighlight lang="powershell">$Name = 'fibo tribo tetra penta hexa hepta octo nona deca'.Split() 0..($Name.Length-1) \| foreach { $Index = $_ $InitialValues = @(1) + @(foreach ($I In 0..$Index) { [Math]::Pow(2,$I) }) $Generator = Get-ExtendedFibonaciGenerator $InitialValues [PSCustomObject] @{ n = $InitialValues.Length; Name = "$($Name[$Index])naci"; Sequence = 1..15 \| foreach { & $Generator } \| Join-String -Separator ',' } } \| Format-Table -AutoSize </syntaxhighlight> Sample output <pre> n Name Sequence - ---- -------- 2 fibonaci 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610 3 tribonaci 1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136 4 tetranaci 1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536 5 pentanaci 1,1,2,4,8,16,31,61,120,236,464,912,1793,3525,6930 6 hexanaci 1,1,2,4,8,16,32,63,125,248,492,976,1936,3840,7617 7 heptanaci 1,1,2,4,8,16,32,64,127,253,504,1004,2000,3984,7936 8 octonaci 1,1,2,4,8,16,32,64,128,255,509,1016,2028,4048,8080 9 nonanaci 1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144 10 decanaci 1,1,2,4,8,16,32,64,128,256,512,1023,2045,4088,8172 </pre> =={{header\|PureBasic}}== <syntaxhighlight 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 "" </syntaxhighlight> '''Sample Output''' <pre> 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 </pre> =={{header\|Python}}== ===Python: function returning a function=== <~~lang~~syntaxhighlight lang="python">>>> def fiblike(start): addnum = len(start) memo = start[:] Line 201 ⟶ 4,011: 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~~syntaxhighlight> ===Python: Callable class=== <~~lang~~syntaxhighlight lang="python">>>> class Fiblike(): def __init__(self, start): self.addnum = len(start) Line 237 ⟶ 4,047: 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~~syntaxhighlight> ===Python: Generator=== <syntaxhighlight lang="python">~~>>>~~ from ~~collections~~itertools import ~~deque~~islice, cycle ~~>>> def fiblike(start):~~ def fiblike(tail): ~~... q = deque()~~ ~~...~~ for x in ~~start~~tail: ~~...~~ yield x for i in cycle(xrange(len(tail))): ~~... q.append(x)~~ tail[i] = x = sum(tail) ~~... while True:~~ ~~...~~ yield x ~~= sum(q)~~ ~~... yield x~~ fibo = fiblike([1, 1]) ~~... q.popleft()~~ print list(islice(fibo, 10)) ~~... q.append(x)~~ lucas = fiblike([2, 1]) ~~...~~ print list(islice(lucas, 10)) ~~>>> from itertools import islice~~ ~~>>> fibo = fiblike([1,1])~~ suffixes = "fibo tribo tetra penta hexa hepta octo nona deca" ~~>>> list(islice(fibo, 10))~~ for n, name in zip(xrange(2, 11), suffixes.split()): ~~[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]~~ ~~>>>~~ ~~lucas~~ fib = fiblike([1] + [2, * i for i in xrange(n - 1)]) ~~>>>~~ items = list(islice(~~lucas~~fib, 1015)) print "n=%2i, %5snacci -> %s ..." % (n, name, items)</syntaxhighlight> {{out}} <pre>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55] [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, list(islice(fibber, 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] ... Line 271 ⟶ 4,080: 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] ...</pre> ~~>>> </lang>~~ ===Python: Defined in terms of a generic anamorphism=== ~~=={{header\|REXX}}==~~ Defining the Lucas series and the N-Step Fibonacci series in terms of unfoldr (dual to functools.reduce). ~~<lang rexx>/REXX program to calculate and display N-step Fibonacci sequences. /~~ {{Works with\|Python\|3.7}} <syntaxhighlight lang="python">'''Fibonacci n-step number sequences''' from itertools import chain, count, islice ~~parse arg FibName values /allow user to specify which Fib/~~ ~~if FibName\=='' then do /if specified, show that Fib. /~~ ~~call nStepFib FibName,values~~ # A000032 :: () -> [Int] ~~exit~~ def A000032(): '''Non finite sequence of Lucas numbers. ''' return unfoldr(recurrence(2))([2, 1]) # nStepFibonacci :: Int -> [Int] def nStepFibonacci(n): '''Non-finite series of N-step Fibonacci numbers, defined by a recurrence relation. ''' return unfoldr(recurrence(n))( take(n)( chain( [1], (2 * i for i in count(0)) ) ) ) # recurrence :: Int -> [Int] -> Int def recurrence(n): '''Recurrence relation in Fibonacci and related series. ''' def go(xs): h, t = xs return h, t + [sum(take(n)(xs))] return go # ------------------------- TEST ------------------------- # main :: IO () def main(): '''First 15 terms each n-step Fibonacci(n) series where n is drawn from [2..8] ''' labels = "fibo tribo tetra penta hexa hepta octo nona deca" table = list( chain( [['lucas:'] + [ str(x) for x in take(15)(A000032())] ], map( lambda k, n: list( chain( [k + 'nacci:'], ( str(x) for x in take(15)(nStepFibonacci(n)) ) ) ), labels.split(), count(2) ) ) ) print('Recurrence relation series:\n') print( spacedTable(table) ) # ----------------------- GENERIC ------------------------ # take :: Int -> [a] -> [a] # take :: Int -> String -> String def take(n): '''The prefix of xs of length n, or xs itself if n > length xs. ''' def go(xs): return ( xs[0:n] if isinstance(xs, (list, tuple)) else list(islice(xs, n)) ) return go # unfoldr :: (b -> Maybe (a, b)) -> b -> [a] def unfoldr(f): '''Generic anamorphism. A lazy (generator) list unfolded from a seed value by repeated application of f until no residue remains. Dual to fold/reduce. f returns either None, or just (value, residue). For a strict output value, wrap in list(). ''' def go(x): valueResidue = f(x) while None is not valueResidue: yield valueResidue[0] valueResidue = f(valueResidue[1]) return go # ---------------------- FORMATTING ---------------------- # spacedTable :: [[String]] -> String def spacedTable(rows): columnWidths = [ max([len(x) for x in col]) for col in zip(rows) ] return '\n'.join([ ' '.join( map( lambda x, w: x.rjust(w, ' '), row, columnWidths ) ) for row in rows ]) # MAIN --- if __name__ == '__main__': main()</syntaxhighlight> {{Out}} <pre>Recurrence relation series: 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</pre> =={{header\|Quackery}}== <syntaxhighlight lang="quackery"> [ 0 swap witheach + ] is sum ( [ --> n ) [ tuck size - dup 0 < iff [ split drop ] else [ dip [ dup size negate swap ] times [ over split dup sum join join ] nip ] ] is n-step ( n [ --> [ ) [ ' [ 1 1 ] n-step ] is fibonacci ( n --> [ ) [ ' [ 1 1 2 ] n-step ] is tribonacci ( n --> [ ) [ ' [ 1 1 2 4 ] n-step ] is tetranacci ( n --> [ ) [ ' [ 2 1 ] n-step ] is lucas ( n --> [ ) ' [ fibonacci tribonacci tetranacci lucas ] witheach [ dup echo say ": " 10 swap do echo cr ]</syntaxhighlight> {{out}} <pre>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 ] </pre> =={{header\|Racket}}== <syntaxhighlight lang="racket">#lang racket ;; fib-list : [Listof Nat] x Nat -> [Listof Nat] ;; Given a non-empty list of natural numbers, the length of the list ;; becomes the size of the step; return the first n numbers of the ;; sequence; assume n >= (length lon) (define (fib-list lon n) (define len (length lon)) (reverse (for/fold ([lon (reverse lon)]) ([_ (in-range (- n len))]) (cons (apply + (take lon len)) lon)))) ;; Show the series ... (define (show-fibs name l) (printf "~a: " name) (for ([n (in-list (fib-list l 20))]) (printf "~a, " n)) (printf "...\n")) ;; ... with initial 2-powers lists (for ([n (in-range 2 11)]) (show-fibs (format "~anacci" (case n [(2) 'fibo] [(3) 'tribo] [(4) 'tetra] [(5) 'penta] [(6) 'hexa] [(7) 'hepta] [(8) 'octo] [(9) 'nona] [(10) 'deca])) (cons 1 (build-list (sub1 n) (curry expt 2))))) ;; and with an initial (2 1) (show-fibs "lucas" '(2 1))</syntaxhighlight> {{out}} <pre>fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ... tribonacci: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, ... tetranacci: 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, ... pentanacci: 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513, ... hexanacci: 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, ... heptanacci: 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, 31489, 62725, 124946, 248888, ... octonacci: 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, 32192, 64256, 128257, 256005, ... nonanacci: 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, 32512, 64960, 129792, 259328, ... decanacci: 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172, 16336, 32656, 65280, 130496, 260864, ... lucas: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, ...</pre> =={{header\|Raku}}== (formerly Perl 6) ===Lazy List with Closure=== <syntaxhighlight lang="raku" line>sub nacci ( $s = 2, :@start = (1,) ) { my @seq = \|@start, { state $n = +@start; @seq[ ($n - $s .. $n++ - 1).grep: * >= 0 ].sum } … ; } put "{.fmt: '%2d'}-nacci: ", nacci($_)[^20] for 2..12 ; put "Lucas: ", nacci(:start(2,1))[^20];</syntaxhighlight> {{out}} <pre> 2-nacci: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 3-nacci: 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 4-nacci: 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 5-nacci: 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513 6-nacci: 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904 7-nacci: 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888 8-nacci: 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005 9-nacci: 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328 10-nacci: 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864 11-nacci: 1 1 2 4 8 16 32 64 128 256 512 1024 2047 4093 8184 16364 32720 65424 130816 261568 12-nacci: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4095 8189 16376 32748 65488 130960 261888 Lucas: 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349</pre> ===Generative=== A slightly more straight forward way of constructing a lazy list. {{works with\|Rakudo\|2015.12}} <syntaxhighlight lang="raku" line>sub fib ($n, @xs is copy = [1]) { flat 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];</syntaxhighlight> =={{header\|REXX}}== <syntaxhighlight lang="rexx">/REXX program calculates and displays a N-step Fibonacci sequence(s). / parse arg FibName values /allows a Fibonacci name, starter vals/ if FibName\='' then do; call nStepFib FibName,values; signal done; end /* [↓] no args specified, 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 done: exit /stick a fork in it, we're all done. / /────────────────────────────────────────────────────────────────────────────/ nStepFib: procedure; parse arg Fname,vals,m; if m=='' then m=30; L= N=words(vals) do pop=1 for N /use N initial values. / @.pop=word(vals,pop) /populate initial numbers/ end /pop/ do j=1 for m /calculate M Fib numbers./ if j>N then do; @.j=0 /initialize the sum to 0./ do k=j-N for N /sum the last N numbers./ @.j=@.j+@.k /add the [N-j]th number./ end /k/ end L=L @.j ~~/nothing~~ ~~given,~~ so ~~show~~ a ~~bunch.~~ /append Fib number──►list/ end /j/ ~~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~~ ~~/─────────────────────────────────────nStepFib subroutine──────────────/~~ ~~nStepFib: procedure; parse arg Fname,vals,m; if m=='' then m=30; L=~~ ~~N=words(vals); do pop=1 for N; @.pop=word(vals,pop); end /populate/~~ say right(Fname,11)'[sum'right(N,3) "terms]:" strip(L) '···' ~~do j=1 for m /calculate M Fibonacci numbers/~~ return</syntaxhighlight> ~~if j>N then do; s=0; do k=j-N for N; s=s+@.k; end /k/~~ '''output'''   when using the default input: ~~@.j=s /assign this sum to the series. /~~ <pre> ~~end~~ Lucas[sum ~~L=L~~2 ~~@.j~~terms]: 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127 24476 39603 ~~/append~~64079 ~~this~~103682 ~~Fib~~167761 ~~num~~271443 to439204 ~~the~~710647 ~~list/~~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 ··· ~~end /j/~~ 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 ··· </pre> =={{header\|Ring}}== ~~say right(Fname,11)'[sum' N "terms]:" strip(L) '...' /show&tell time/~~ <syntaxhighlight lang="ring"> ~~return</lang>~~ # Project : Fibonacci n-step number sequences ~~'''output''' when using the default input~~ ~~<pre style="height:45ex;overflow:scroll">~~ f = list(12) ~~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 ...~~ see "Fibonacci:" + nl ~~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 ...~~ f2 = [1,1] ~~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 ...~~ for nr2 = 1 to 10 ~~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 ...~~ see "" + f2[1] + " " ~~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 ...~~ fibn(f2) ~~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 ...~~ next ~~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 ...~~ showarray(f2) ~~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 ...~~ see " ..." + nl + nl ~~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 ...~~ see "Tribonacci:" + nl ~~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 ...~~ f3 = [1,1,2] ~~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 ...~~ for nr3 = 1 to 9 see "" + f3[1] + " " fibn(f3) next showarray(f3) see " ..." + nl + nl see "Tetranacci:" + nl f4 = [1,1,2,4] for nr4 = 1 to 8 see "" + f4[1] + " " fibn(f4) next showarray(f4) see " ..." + nl + nl see "Lucas:" + nl f5 = [2,1] for nr5 = 1 to 10 see "" + f5[1] + " " fibn(f5) next showarray(f5) see " ..." + nl + nl func fibn(fs) s = sum(fs) for i = 2 to len(fs) fs[i-1] = fs[i] next fs[i-1] = s return fs func sum(arr) sm = 0 for sn = 1 to len(arr) sm = sm + arr[sn] next return sm func showarray(fn) svect = "" for p = 1 to len(fn) svect = svect + fn[p] + " " next see svect </syntaxhighlight> Output: <pre> 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 ... </pre> =={{header\|RPL}}== ≪ OVER SIZE → len n ≪ LIST→ <span style="color:red">1</span> + len '''FOR''' j n DUPN <span style="color:red">2</span> n '''START''' + '''NEXT''' '''NEXT''' len →LIST ≫ ≫ ‘<span style="color:blue">NFIB</span>’ STO <span style="color:red">{1 1} 15</span> <span style="color:blue">NFIB</span> DUP <span style="color:red">1 3</span> SUB <span style="color:red">15</span> <span style="color:blue">NFIB</span> DUP <span style="color:red">1 4</span> SUB <span style="color:red">15</span> <span style="color:blue">NFIB</span> <span style="color:red">{2 1} 15</span> <span style="color:blue">NFIB</span> {{out}} <pre> 4: { 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 } 3: { 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 } 2: { 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 } 1: { 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 } </pre> =={{header\|Ruby}}== <syntaxhighlight 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 (count-n).times do # Loop for the remaining results up to count result << result.last(n).sum # Get the last n element from result and append its total to Array end result end naccis = { lucas: [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] } naccis.each {\|name, seq\| puts "%12s : %p" % [name, anynacci(seq, 15)]}</syntaxhighlight> {{out}} <syntaxhighlight lang="ruby"> 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] </syntaxhighlight> =={{header\|Run BASIC}}== <syntaxhighlight lang="runbasic">a = fib(" fibonacci ", "1,1") a = fib("tribonacci ", "1,1,2") a = fib("tetranacci ", "1,1,2,4") a = fib(" pentanacc ", "1,1,2,4,8") a = fib(" hexanacci ", "1,1,2,4,8,16") a = fib(" lucas ", "2,1") function fib(f$, s$) dim f(20) while word$(s$,b+1,",") <> "" b = b + 1 f(b) = val(word$(s$,b,",")) wend PRINT f$; "=>"; 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</syntaxhighlight> {{out}} <pre> fibonacci => 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, tribonacci => 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, tetranacci => 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, pentanacc => 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, hexanacci => 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, lucas => 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521,</pre> =={{header\|Rust}}== <syntaxhighlight lang="rust"> struct GenFibonacci { buf: Vec<u64>, sum: u64, idx: usize, } impl Iterator for GenFibonacci { type Item = u64; fn next(&mut self) -> Option<u64> { let result = Some(self.sum); self.sum -= self.buf[self.idx]; self.buf[self.idx] += self.sum; self.sum += self.buf[self.idx]; self.idx = (self.idx + 1) % self.buf.len(); result } } fn print(buf: Vec<u64>, len: usize) { let mut sum = 0; for &elt in buf.iter() { sum += elt; print!("\t{}", elt); } let iter = GenFibonacci { buf: buf, sum: sum, idx: 0 }; for x in iter.take(len) { print!("\t{}", x); } } fn main() { print!("Fib2:"); print(vec![1,1], 10 - 2); print!("\nFib3:"); print(vec![1,1,2], 10 - 3); print!("\nFib4:"); print(vec![1,1,2,4], 10 - 4); print!("\nLucas:"); print(vec![2,1], 10 - 2); } </syntaxhighlight> <syntaxhighlight lang="text"> Fib2: 1 1 2 3 5 8 13 21 34 55 Fib3: 1 1 2 4 7 13 24 44 81 149 Fib4: 1 1 2 4 8 15 29 56 108 208 Lucas: 2 1 3 4 7 11 18 29 47 76 </syntaxhighlight> =={{header\|Scala}}== ===Simple Solution=== <syntaxhighlight lang="scala"> //we rely on implicit conversion from Int to BigInt. //BigInt is preferable since the numbers get very big, very fast. //(though for a small example of the first few numbers it's not needed) def fibStream(init: BigInt): LazyList[BigInt] = { def inner(prev: Vector[BigInt]): LazyList[BigInt] = prev.head #:: inner(prev.tail :+ prev.sum) inner(init.toVector) } </syntaxhighlight> ===Optimizing=== <syntaxhighlight lang="scala"> //in the optimized version we don't compute values until it's needed. //the unoptimized version, computed k elements ahead, where k being //the number of elements to sum (fibonacci: k=2, tribonacci: k=3, ...). def fib2Stream(init: BigInt): LazyList[BigInt] = { def inner(prev: Vector[BigInt]): LazyList[BigInt] = { val sum = prev.sum sum #:: inner(prev.tail :+ sum) } init.to(LazyList) #::: inner(init.toVector) } </syntaxhighlight> ===Optimizing Further=== <syntaxhighlight lang="scala"> //instead of summing k elements each phase, we exploit the fact //that the last element is already the sum of all k preceding elements def fib3Stream(init: BigInt): LazyList[BigInt] = { def inner(prev: Vector[BigInt]): LazyList[BigInt] = { val n = prev.last 2 - prev.head n #:: inner(prev.tail :+ n) } //last element must be the sum of k preceding elements, vector size should be k+1 val v = init.toVector :+ init.sum v.to(LazyList) #::: inner(v) } </syntaxhighlight> ===Printing=== <syntaxhighlight lang="scala"> println(s"Fibonacci: ${fibStream(1,1).take(10).mkString(",")}") println(s"Tribonacci: ${fibStream(1,1,2).take(10).mkString(",")}") println(s"Tetranacci: ${fibStream(1,1,2,4).take(10).mkString(",")}") println(s"Lucas: ${fibStream(2,1).take(10).mkString(",")}") </syntaxhighlight> {{out}} <pre> 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 </pre> '''Note:''' In Scala, ''Stream'' is a lazy list. if you don't need the sequence saved in memory, just to iterate over members, you may convert the logic to use ''Iterator'' instead of ''Stream''. =={{header\|Scheme}}== <syntaxhighlight lang="scheme"> (import (scheme base) (scheme write) (srfi 1)) ;; uses n-step sequence formula to ;; continue lst until of length num (define (n-fib lst num) (let ((n (length lst))) (do ((result (reverse lst) (cons (fold + 0 (take result n)) result))) ((= num (length result)) (reverse result))))) ;; display examples (do ((i 2 (+ 1 i))) ((> i 4) ) (display (string-append "n = " (number->string i) ": ")) (display (n-fib (cons 1 (list-tabulate (- i 1) (lambda (n) (expt 2 n)))) 15)) (newline)) (display "Lucas: ") (display (n-fib '(2 1) 15)) (newline) </syntaxhighlight> {{out}} <pre> n = 2: (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610) n = 3: (1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136) n = 4: (1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536) Lucas: (2 1 3 4 7 11 18 29 47 76 123 199 322 521 843) </pre> =={{header\|Seed7}}== <syntaxhighlight 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;</syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|Sidef}}== {{trans\|Perl}} <syntaxhighlight lang="ruby">func fib(n, xs=[1], k=20) { loop { var len = xs.len len >= k && break xs << xs.slice(max(0, len - n)).sum } return xs } for i in (2..10) { say fib(i).join(' ') } say fib(2, [2, 1]).join(' ')</syntaxhighlight> {{out}} <pre> 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 </pre> Using matrix exponentiation: <syntaxhighlight lang="ruby">func fibonacci_matrix(k) is cached { Matrix.build(k,k, {\|i,j\| ((i == k-1) \|\| (i == j-1)) ? 1 : 0 }) } func fibonacci_kth_order(n, k=2) { var A = fibonacci_matrix(k) (An)[0][-1] } for k in (2..9) { say ("Fibonacci of k=#{k} order: ", (15+k).of { fibonacci_kth_order(_, k) }) }</syntaxhighlight> {{out}} <pre> Fibonacci of k=2 order: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987] Fibonacci of k=3 order: [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768] Fibonacci of k=4 order: [0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671] Fibonacci of k=5 order: [0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624] Fibonacci of k=6 order: [0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109] Fibonacci of k=7 order: [0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808] Fibonacci of k=8 order: [0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128] Fibonacci of k=9 order: [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272] </pre> Faster algorithm: <syntaxhighlight lang="ruby">func fibonacci_kth_order (n, k = 2) { return 0 if (n < k-1) var f = (1..(k+1) -> map {\|j\| j < k ? 2j : 1 }) k += 1 for i in (2(k-1) .. n) { f[i%k] = (2f[(i-1)%k] - f[i%k]) } return f[n%k] } for k in (2..9) { say ("Fibonacci of k=#{k} order: ", (15+k).of { fibonacci_kth_order(_, k) }) }</syntaxhighlight> (same output as above) =={{header\|Tailspin}}== <syntaxhighlight lang="tailspin"> templates fibonacciNstep&{N:} templates next @: $(1); $(2..last)... -> @: $ + $@; [ $(2..last)..., $@ ] ! end next @: $; 1..$N -> # <> $@(1) ! @: $@ -> next; end fibonacciNstep [1,1] -> fibonacciNstep&{N:10} -> '$; ' -> !OUT::write ' ' -> !OUT::write [1,1,2] -> fibonacciNstep&{N:10} -> '$; ' -> !OUT::write ' ' -> !OUT::write [1,1,2,4] -> fibonacciNstep&{N:10} -> '$; ' -> !OUT::write ' ' -> !OUT::write [2,1] -> fibonacciNstep&{N:10} -> '$; ' -> !OUT::write ' ' -> !OUT::write </syntaxhighlight> {{out}} <pre> 1 1 2 3 5 8 13 21 34 55 1 1 2 4 7 13 24 44 81 149 1 1 2 4 8 15 29 56 108 208 2 1 3 4 7 11 18 29 47 76 </pre> =={{header\|Tcl}}== {{works with\|Tcl\|8.6}} <~~lang~~syntaxhighlight lang="tcl">package require Tcl 8.6 proc fibber {args} { Line 359 ⟶ 4,907: print10 [fibber 1 1 2 4] puts "LUCAS" print10 [fibber 2 1]</~~lang~~syntaxhighlight> {{out}} <pre> Line 370 ⟶ 4,918: LUCAS [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, ...] </pre> =={{header\|VBA}}== <syntaxhighlight lang="vb">Option Explicit Sub Main() Dim temp$, T() As Long, i& 'Fibonacci: T = Fibonacci_Step(1, 15, 1) For i = LBound(T) To UBound(T) temp = temp & ", " & T(i) Next Debug.Print "Fibonacci: " & Mid(temp, 3) temp = "" 'Tribonacci: T = Fibonacci_Step(1, 15, 2) For i = LBound(T) To UBound(T) temp = temp & ", " & T(i) Next Debug.Print "Tribonacci: " & Mid(temp, 3) temp = "" 'Tetranacci: T = Fibonacci_Step(1, 15, 3) For i = LBound(T) To UBound(T) temp = temp & ", " & T(i) Next Debug.Print "Tetranacci: " & Mid(temp, 3) temp = "" 'Lucas: T = Fibonacci_Step(1, 15, 1, 2) For i = LBound(T) To UBound(T) temp = temp & ", " & T(i) Next Debug.Print "Lucas: " & Mid(temp, 3) temp = "" End Sub Private Function Fibonacci_Step(First As Long, Count As Long, S As Long, Optional Second As Long) As Long() Dim T() As Long, R() As Long, i As Long, Su As Long, C As Long If Second <> 0 Then S = 1 ReDim T(1 - S To Count) For i = LBound(T) To 0 T(i) = 0 Next i T(1) = IIf(Second <> 0, Second, 1) T(2) = 1 For i = 3 To Count Su = 0 C = S + 1 Do While C >= 0 Su = Su + T(i - C) C = C - 1 Loop T(i) = Su Next ReDim R(1 To Count) For i = 1 To Count R(i) = T(i) Next Fibonacci_Step = R End Function</syntaxhighlight> {{Out}} <pre>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 Lucas: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843</pre> =={{header\|VBScript}}== <syntaxhighlight lang="vb"> 'function arguments: 'init - initial series of the sequence(e.g. "1,1") 'rep - how many times the sequence repeats - init Function generate_seq(init,rep) token = Split(init,",") step_count = UBound(token) rep = rep - (UBound(token) + 1) out = init For i = 1 To rep sum = 0 n = step_count Do While n >= 0 sum = sum + token(UBound(token)-n) n = n - 1 Loop 'add the next number to the sequence ReDim Preserve token(UBound(token) + 1) token(UBound(token)) = sum out = out & "," & sum Next generate_seq = out End Function WScript.StdOut.Write "fibonacci: " & generate_seq("1,1",15) WScript.StdOut.WriteLine WScript.StdOut.Write "tribonacci: " & generate_seq("1,1,2",15) WScript.StdOut.WriteLine WScript.StdOut.Write "tetranacci: " & generate_seq("1,1,2,4",15) WScript.StdOut.WriteLine WScript.StdOut.Write "lucas: " & generate_seq("2,1",15) WScript.StdOut.WriteLine </syntaxhighlight> {{Out}} <pre> 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 lucas: 2,1,3,4,7,11,18,29,47,76,123,199,322,521,843 </pre> =={{header\|Visual Basic .NET}}== {{trans\|Visual Basic}} {{works with\|Visual Basic .NET\|2011}} <syntaxhighlight lang="vbnet">' Fibonacci n-step number sequences - VB.Net Public Class FibonacciNstep Const nmax = 20 Sub Main() Dim bonacci As String() = {"", "", "Fibo", "tribo", "tetra", "penta", "hexa"} Dim i As Integer 'Fibonacci: For i = 2 To 6 Debug.Print(bonacci(i) & "nacci: " & FibonacciN(i, nmax)) Next i 'Lucas: Debug.Print("Lucas: " & FibonacciN(2, nmax, 2)) End Sub 'Main Private Function FibonacciN(iStep As Long, Count As Long, Optional First As Long = 0) As String Dim i, j As Integer, Sigma As Long, c As String Dim T(nmax) As Long T(1) = IIf(First = 0, 1, First) T(2) = 1 For i = 3 To Count Sigma = 0 For j = i - 1 To i - iStep Step -1 If j > 0 Then Sigma += T(j) End If Next j T(i) = Sigma Next i c = "" For i = 1 To nmax c &= ", " & T(i) Next i Return Mid(c, 3) End Function 'FibonacciN End Class 'FibonacciNstep</syntaxhighlight> {{out}} <pre> Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 tribonacci: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012 tetranacci: 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312 pentanacci: 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513 hexanacci: 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904 Lucas: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349 </pre> =={{header\|V (Vlang)}}== {{trans\|Wren}} <syntaxhighlight lang="v (vlang)">fn fib_n(initial []int, num_terms int) []int { n := initial.len if n < 2 \|\| num_terms < 0 {panic("Invalid argument(s).")} if num_terms <= n {return initial} mut fibs := []int{len:num_terms} for i in 0..n { fibs[i] = initial[i] } for i in n..num_terms { mut sum := 0 for j in i-n..i { sum = sum + fibs[j] } fibs[i] = sum } return fibs } fn main(){ names := [ "fibonacci", "tribonacci", "tetranacci", "pentanacci", "hexanacci", "heptanacci", "octonacci", "nonanacci", "decanacci" ] initial := [1, 1, 2, 4, 8, 16, 32, 64, 128, 256] println(" n name values") mut values := fib_n([2, 1], 15) print(" 2 ${'lucas':-10}") println(values.map('${it:4}').join(' ')) for i in 0..names.len { values = fib_n(initial[0..i + 2], 15) print("${i+2:2} ${names[i]:-10}") println(values.map('${it:4}').join(' ')) } }</syntaxhighlight> {{out}} <pre> n name values 2 lucas 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 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 </pre> =={{header\|Wren}}== {{trans\|Kotlin}} {{libheader\|Wren-fmt}} <syntaxhighlight lang="wren">import "./fmt" for Fmt var fibN = Fn.new { \|initial, numTerms\| var n = initial.count if (n < 2 \|\| numTerms < 0) Fiber.abort("Invalid argument(s).") if (numTerms <= n) return initial.toList var fibs = List.filled(numTerms, 0) for (i in 0...n) fibs[i] = initial[i] for (i in n...numTerms) { var sum = 0 for (j in i-n...i) sum = sum + fibs[j] fibs[i] = sum } return fibs } var names = [ "fibonacci", "tribonacci", "tetranacci", "pentanacci", "hexanacci", "heptanacci", "octonacci", "nonanacci", "decanacci" ] var initial = [1, 1, 2, 4, 8, 16, 32, 64, 128, 256] System.print(" n name values") var values = fibN.call([2, 1], 15) Fmt.write("$2d $-10s", 2, "lucas") Fmt.aprint(values, 4, 0, "") for (i in 0..8) { values = fibN.call(initial[0...i + 2], 15) Fmt.write("$2d $-10s", i + 2, names[i]) Fmt.aprint(values, 4, 0, "") }</syntaxhighlight> {{out}} <pre> n name values 2 lucas 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 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 </pre> =={{header\|XPL0}}== <syntaxhighlight 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]); ]</syntaxhighlight> Output: <pre> 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 </pre> =={{header\|Yabasic}}== {{trans\|Lua}} <syntaxhighlight lang="yabasic">sub nStepFibs$(seq$, limit) local iMax, sum, numb$(1), lim, i lim = token(seq$, numb$(), ",") redim numb$(limit) seq$ = "" iMax = lim - 1 while(lim < limit) sum = 0 for i = 0 to iMax : sum = sum + val(numb$(lim - i)) : next lim = lim + 1 numb$(lim) = str$(sum) wend for i = 0 to lim : seq$ = seq$ + " " + numb$(i) : next return seq$ end sub print "Fibonacci:", nStepFibs$("1,1", 10) print "Tribonacci:", nStepFibs$("1,1,2", 10) print "Tetranacci:", nStepFibs$("1,1,2,4", 10) print "Lucas:", nStepFibs$("2,1", 10)</syntaxhighlight> =={{header\|zkl}}== <syntaxhighlight lang="zkl">fcn fibN(ns){ fcn(ns){ ns.append(ns.sum()).pop(0) }.fp(vm.arglist.copy()); }</syntaxhighlight> This stores the initial n terms of the sequence and returns a function that, at each call, appends the sum of the terms to the sequence then pops the leading value and returns it. <syntaxhighlight lang="zkl">N:=15; lucas:=fibN(2,1); do(N){ lucas().print(","); } println(); // Lucas ns:=L(1); foreach _ in ([ns.len()+1..10]){ // Fibonacci n-step for 2 .. 10 ns.append(ns.sum()); // the inital values for the series "%2d: ".fmt(ns.len()).print(); (N).pump(List,fibN(ns.xplode())).println(); }</syntaxhighlight> {{out}} <pre> 2,1,3,4,7,11,18,29,47,76,123,199,322,521,843, 2: L(1,1,2,3,5,8,13,21,34,55,89,144,233,377,610) 3: L(1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136) 4: L(1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536) 5: L(1,1,2,4,8,16,31,61,120,236,464,912,1793,3525,6930) 6: L(1,1,2,4,8,16,32,63,125,248,492,976,1936,3840,7617) 7: L(1,1,2,4,8,16,32,64,127,253,504,1004,2000,3984,7936) 8: L(1,1,2,4,8,16,32,64,128,255,509,1016,2028,4048,8080) 9: L(1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144) 10: L(1,1,2,4,8,16,32,64,128,256,512,1023,2045,4088,8172) </pre>