Fibonacci n-step number sequences
These number series are an expansion of the ordinary Fibonacci sequence where:
- For we have the Fibonacci sequence; with initial values and
- For we have the tribonacci sequence; with initial values and
- For we have the tetranacci sequence; with initial values and
... - For general we have the Fibonacci -step sequence - ; with initial values of the first values of the 'th Fibonacci -step sequence ; and 'th value of this 'th sequence being
You are encouraged to solve this task according to the task description, using any language you may know.
For small values of , Greek numeric prefixes are sometimes used to individually name each series.
Fibonacci -step sequences Series name Values 2 fibonacci 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... 3 tribonacci 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ... 4 tetranacci 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ... 5 pentanacci 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ... 6 hexanacci 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ... 7 heptanacci 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ... 8 octonacci 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ... 9 nonanacci 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ... 10 decanacci 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
Allied sequences can be generated where the initial values are changed:
- The Lucas series sums the two preceeding values like the fibonacci series for but uses as its initial values.
- The task is to
- Write a function to generate Fibonacci -step number sequences given its initial values and assuming the number of initial values determines how many previous values are summed to make the next number of the series.
- Use this to print and show here at least the first ten members of the Fibo/tribo/tetra-nacci and Lucas sequences.
- Cf.
Ada
First, we specify a package Bonacci, that defines the type Sequence (of Positive numbers), a function Generate that takes a given Start sequence and outputs a generalized N-Bonacci Sequence of a spefified Length, and some constant start sequences.
<lang Ada>package Bonacci is
type Sequence is array(Positive range <>) of Positive;
function Generate(Start: Sequence; Length: Positive := 10) return Sequence;
Start_Fibonacci: constant Sequence := (1, 1); Start_Tribonacci: constant Sequence := (1, 1, 2); Start_Tetranacci: constant Sequence := (1, 1, 2, 4); Start_Lucas: constant Sequence := (2, 1);
end Bonacci;</lang>
The implementation is quite straightforward.
<lang Ada>package body Bonacci is
function Generate(Start: Sequence; Length: Positive := 10) return Sequence is begin if Length <= Start'Length then return Start(Start'First .. Start'First+Length-1); else declare Sum: Natural := 0; begin for I in Start'Range loop Sum := Sum + Start(I); end loop; return Start(Start'First) & Generate(Start(Start'First+1 .. Start'Last) & Sum, Length-1); end; end if; end Generate;
end Bonacci;</lang>
Finally, we actually generate some sequences, as required by the task. For convenience, we define a procedure Print that outputs a sequence,
<lang Ada>with Ada.Text_IO, Bonacci;
procedure Test_Bonacci is
procedure Print(Name: String; S: Bonacci.Sequence) is begin Ada.Text_IO.Put(Name & "("); for I in S'First .. S'Last-1 loop Ada.Text_IO.Put(Integer'Image(S(I)) & ","); end loop; Ada.Text_IO.Put_Line(Integer'Image(S(S'Last)) & " )"); end Print;
begin
Print("Fibonacci: ", Bonacci.Generate(Bonacci.Start_Fibonacci)); Print("Tribonacci: ", Bonacci.Generate(Bonacci.Start_Tribonacci)); Print("Tetranacci: ", Bonacci.Generate(Bonacci.Start_Tetranacci)); Print("Lucas: ", Bonacci.Generate(Bonacci.Start_Lucas)); Print("Decanacci: ", Bonacci.Generate((1, 1, 2, 4, 8, 16, 32, 64, 128, 256), 15));
end Test_Bonacci;</lang>
The output:
Fibonacci: ( 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ) Tribonacci: ( 1, 1, 2, 4, 7, 13, 24, 44, 81, 149 ) Tetranacci: ( 1, 1, 2, 4, 8, 15, 29, 56, 108, 208 ) Lucas: ( 2, 1, 3, 4, 7, 11, 18, 29, 47, 76 ) Decanacci: ( 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172 )
ACL2
<lang lisp>(defun sum (xs)
(if (endp xs) 0 (+ (first xs) (sum (rest xs)))))
(defun n-bonacci (prevs limit)
(if (zp limit) nil (let ((next (append (rest prevs) (list (sum prevs))))) (cons (first next) (n-bonacci next (1- limit))))))</lang>
Output:
> (n-bonacci '(1 1) 10) (1 2 3 5 8 13 21 34 55 89) > (n-bonacci '(1 1 2) 10) (1 2 4 7 13 24 44 81 149 274) > (n-bonacci '(1 1 2 4) 10) (1 2 4 8 15 29 56 108 208 401) > (n-bonacci '(2 1) 10) (1 3 4 7 11 18 29 47 76 123)
C
<lang c> /*29th August, 2012 Abhishek Ghosh
The function anynacci determines the n-arity of the sequence from the number of seed elements. 0 ended arrays are used since C does not have a way of determining the length of dynamic and function-passed integer arrays.*/
- include<stdlib.h>
- include<stdio.h>
int * anynacci (int *seedArray, int howMany) {
int *result = (int *) malloc (howMany * sizeof (int)); int i, j, initialCardinality;
for (i = 0; seedArray[i] != 0; i++); initialCardinality = i;
for (i = 0; i < initialCardinality; i++) result[i] = seedArray[i];
for (i = initialCardinality; i < howMany; i++) { result[i] = 0; for (j = i - initialCardinality; j < i; j++) result[i] += result[j]; } return result;
}
int main () {
int fibo[] = { 1, 1, 0 }, tribo[] = { 1, 1, 2, 0 }, tetra[] = { 1, 1, 2, 4, 0 }, luca[] = { 2, 1, 0 }; int *fibonacci = anynacci (fibo, 10), *tribonacci = anynacci (tribo, 10), *tetranacci = anynacci (tetra, 10), *lucas = anynacci(luca, 10); int i;
printf ("\nFibonacci\tTribonacci\tTetranacci\tLucas\n");
for (i = 0; i < 10; i++) printf ("\n%d\t\t%d\t\t%d\t\t%d", fibonacci[i], tribonacci[i], tetranacci[i], lucas[i]);
return 0;
}
</lang>
Output:
Fibonacci Tribonacci Tetranacci Lucas 1 1 1 2 1 1 1 1 2 2 2 3 3 4 4 4 5 7 8 7 8 13 15 11 13 24 29 18 21 44 56 29 34 81 108 47 55 149 208 76
C++
<lang C++>#include <vector>
- include <iostream>
- include <numeric>
- include <iterator>
- include <memory>
- include <string>
- include <algorithm>
- include <iomanip>
std::vector<int> nacci ( const std::vector<int> & start , int arity ) {
std::vector<int> result ( start ) ; int sumstart = 1 ;//summing starts at vector's begin + sumstart as //soon as the vector is longer than arity while ( result.size( ) < 15 ) { //we print out the first 15 numbers if ( result.size( ) <= arity )
result.push_back( std::accumulate( result.begin( ) , result.begin( ) + result.size( ) , 0 ) ) ;
else {
result.push_back( std::accumulate ( result.begin( ) + sumstart , result.begin( ) + sumstart + arity , 0 )) ; sumstart++ ;
} } return std::move ( result ) ;
}
int main( ) {
std::vector<std::string> naccinames {"fibo" , "tribo" , "tetra" , "penta" , "hexa" , "hepta" , "octo" , "nona" , "deca" } ; const std::vector<int> fibo { 1 , 1 } , lucas { 2 , 1 } ; for ( int i = 2 ; i < 11 ; i++ ) { std::vector<int> numberrow = nacci ( fibo , i ) ; std::cout << std::left << std::setw( 10 ) <<
naccinames[ i - 2 ].append( "nacci" ) << std::setw( 2 ) << " : " ;
std::copy ( numberrow.begin( ) , numberrow.end( ) ,
std::ostream_iterator<int>( std::cout , " " ) ) ;
std::cout << "...\n" ; numberrow = nacci ( lucas , i ) ; std::cout << "Lucas-" << i ; if ( i < 10 ) //for formatting purposes
std::cout << " : " ;
else
std::cout << " : " ;
std::copy ( numberrow.begin( ) , numberrow.end( ) ,
std::ostream_iterator<int>( std::cout , " " ) ) ;
std::cout << "...\n" ; } return 0 ;
}</lang> Output:
fibonacci : 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... Lucas-2 : 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 ... tribonacci : 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ... Lucas-3 : 2 1 3 6 10 19 35 64 118 217 399 734 1350 2483 4567 ... tetranacci : 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ... Lucas-4 : 2 1 3 6 12 22 43 83 160 308 594 1145 2207 4254 8200 ... pentanacci : 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ... Lucas-5 : 2 1 3 6 12 24 46 91 179 352 692 1360 2674 5257 10335 ... hexanacci : 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ... Lucas-6 : 2 1 3 6 12 24 48 94 187 371 736 1460 2896 5744 11394 ... heptanacci : 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ... Lucas-7 : 2 1 3 6 12 24 48 96 190 379 755 1504 2996 5968 11888 ... octonacci : 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ... Lucas-8 : 2 1 3 6 12 24 48 96 192 382 763 1523 3040 6068 12112 ... nonanacci : 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ... Lucas-9 : 2 1 3 6 12 24 48 96 192 384 766 1531 3059 6112 12212 ... decanacci : 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ... Lucas-10 : 2 1 3 6 12 24 48 96 192 384 768 1534 3067 6131 12256 ...
D
Basic Memoization
<lang d>import std.stdio, std.algorithm, std.range, std.conv;
void main() {
int[] memo; size_t addNum;
void setHead(int[] head) nothrow { memo = head; addNum = head.length; }
int fibber(in size_t n) /*nothrow*/ { if (n >= memo.length) memo ~= iota(n - addNum, n).map!fibber().reduce!q{a + b}(); return memo[n]; }
setHead([1, 1]); iota(10).map!fibber().writeln(); setHead([2, 1]); iota(10).map!fibber().writeln();
auto prefixes = "fibo tribo tetra penta hexa hepta octo nona deca"; foreach (n, name; zip(iota(2, 11), prefixes.split())) { setHead(1 ~ iota(n - 1).map!q{2 ^^ a}().array()); auto items = iota(15).map!(i => text(fibber(i)))().join(" "); writefln("n=%2d, %5snacci -> %s ...", n, name, items); }
}</lang>
- Output:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] n= 2, fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ... n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ... n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ... n= 6, hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ... n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ... n= 8, octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ... n= 9, nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ... n=10, decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
Callable Struct
The output is similar. <lang d>import std.stdio, std.algorithm, std.range, std.conv;
struct fiblike(T) {
T[] memo; immutable size_t addNum;
this(in T[] start) /*nothrow*/ { this.memo = start.dup; this.addNum = start.length; }
T opCall(in size_t n) /*nothrow*/ { if (n >= memo.length) memo ~= iota(n - addNum, n) .map!(i => opCall(i))() .reduce!q{a + b}(); return memo[n]; }
}
void main() {
auto fibo = fiblike!int([1, 1]); iota(10).map!fibo().writeln();
auto lucas = fiblike!int([2, 1]); iota(10).map!lucas().writeln();
const prefixes = "fibo tribo tetra penta hexa hepta octo nona deca"; foreach (n, name; zip(iota(2, 11), prefixes.split())) { auto fib = fiblike!int(1 ~ iota(n - 1).map!q{2 ^^ a}().array()); writefln("n=%2d, %5snacci -> %(%d %) ...", n, name, iota(15).map!fib()); }
}</lang>
Struct With opApply
The output is similar. <lang d>import std.stdio, std.algorithm, std.range, std.traits;
struct Fiblike(T) {
T[] tail;
int opApply(int delegate(ref T) dg) { int result, pos; foreach (x; tail) { result = dg(x); if (result) return result; } foreach (i; cycle(iota(tail.length))) { auto x = tail.reduce!q{a + b}(); 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, size_t n) {
typeof(return) result; foreach (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();
auto prefixes = "fibo tribo tetra penta hexa hepta octo nona deca"; foreach (n, name; zip(iota(2, 11), prefixes.split())) { auto fib = Fiblike!int(1 ~ iota(n-1).map!q{2 ^^ a}().array()); writefln("n=%2d, %5snacci -> %s", n, name, fib.takeApply(15)); }
}</lang>
Go
Solution using a separate goroutine. <lang go>package main
import "fmt"
func g(i []int, c chan int) {
var sum int b := append([]int{}, i...) for _, t := range b { c <- t sum += t } for { for j, t := range b { c <- sum b[j], sum = sum, sum+sum-t } }
}
func main() {
for _, s := range []struct { seq string i []int } { {"Fibonacci", []int{1, 1}}, {"Tribonacci", []int{1, 1, 2}}, {"Tetranacci", []int{1, 1, 2, 4}}, {"Lucas", []int{2, 1}}, } { fmt.Printf("%10s:", s.seq) c := make(chan int) go g(s.i, c) for j := 0; j < 10; j++ { fmt.Print(" ", <-c) } fmt.Println() }
}</lang>
- Output:
Fibonacci: 1 1 2 3 5 8 13 21 34 55 Tribonacci: 1 1 2 4 7 13 24 44 81 149 Tetranacci: 1 1 2 4 8 15 29 56 108 208 Lucas: 2 1 3 4 7 11 18 29 47 76
Haskell
<lang haskell>import Data.List (tails) import Control.Monad (zipWithM_)
fiblike :: [Integer] -> [Integer] fiblike st = xs where
xs = st ++ map (sum . take n) (tails xs) n = length st
nstep :: Int -> [Integer] nstep n = fiblike $ take n $ 1 : iterate (2*) 1
main :: IO () main = do
print $ take 10 $ fiblike [1,1] print $ take 10 $ fiblike [2,1] zipWithM_ (\n name -> do putStr (name ++ "nacci -> ") print $ take 15 $ nstep n) [2..] (words "fibo tribo tetra penta hexa hepta octo nona deca")</lang>
- Output:
[1,1,2,3,5,8,13,21,34,55] [2,1,3,4,7,11,18,29,47,76] fibonacci -> [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610] tribonacci -> [1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136] tetranacci -> [1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536] pentanacci -> [1,1,2,4,8,16,31,61,120,236,464,912,1793,3525,6930] hexanacci -> [1,1,2,4,8,16,32,63,125,248,492,976,1936,3840,7617] heptanacci -> [1,1,2,4,8,16,32,64,127,253,504,1004,2000,3984,7936] octonacci -> [1,1,2,4,8,16,32,64,128,255,509,1016,2028,4048,8080] nonanacci -> [1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144] decanacci -> [1,1,2,4,8,16,32,64,128,256,512,1023,2045,4088,8172]
J
Solution:<lang j> nacci =: (] , +/@{.)^:(-@#@]`(-#)`])</lang> Example (Lucas):<lang j> 10 nacci 2 1 NB. Lucas series, first 10 terms 2 1 3 4 7 11 18 29 47 76</lang> Example (extended 'nacci series):<lang j> TESTS =: }."1 fixdsv noun define [ require 'tables/dsv' NB. Tests from task description 2 fibonacci 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... 3 tribonacci 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ... 4 tetranacci 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ... 5 pentanacci 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ... 6 hexanacci 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ... 7 heptanacci 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ... 8 octonacci 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ... 9 nonanacci 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ... 10 decanacci 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ... )
testNacci =: ] -: #@] nacci {. NB. Given an order & test sequence, compare nacci to sequence OT =: __ ".&.> (<<<1) { |: TESTS NB. 'nacci order and test sequence (> 1 {"1 TESTS) ,. ' ' ,. (u: 16b274c 16b2713) {~ (testNacci }:)&>/ OT NB. ✓ or ❌ for success or failure
fibonacci ✓ tribonacci ✓ tetranacci ✓ pentanacci ✓ hexanacci ✓ heptanacci ✓ octonacci ✓ nonanacci ✓ decanacci ✓</lang>
Java
Code:
<lang java>class Fibonacci {
public static int[] lucas(int n, int numRequested) { if (n < 2) throw new IllegalArgumentException("Fibonacci value must be at least 2"); return fibonacci((n == 2) ? new int[] { 2, 1 } : lucas(n - 1, n), numRequested); } public static int[] fibonacci(int n, int numRequested) { if (n < 2) throw new IllegalArgumentException("Fibonacci value must be at least 2"); return fibonacci((n == 2) ? new int[] { 1, 1 } : fibonacci(n - 1, n), numRequested); } public static int[] fibonacci(int[] startingValues, int numRequested) { int[] output = new int[numRequested]; int n = startingValues.length; System.arraycopy(startingValues, 0, output, 0, n); for (int i = n; i < numRequested; i++) for (int j = 1; j <= n; j++) output[i] += output[i - j]; return output; } public static void main(String[] args) { for (int n = 2; n <= 10; n++) { System.out.print("nacci(" + n + "):"); for (int value : fibonacci(n, 15)) System.out.print(" " + value); System.out.println(); } for (int n = 2; n <= 10; n++) { System.out.print("lucas(" + n + "):"); for (int value : lucas(n, 15)) System.out.print(" " + value); System.out.println(); } }
}</lang>
Output:
nacci(2): 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 nacci(3): 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 nacci(4): 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 nacci(5): 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 nacci(6): 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 nacci(7): 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 nacci(8): 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 nacci(9): 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 nacci(10): 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 lucas(2): 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 lucas(3): 2 1 3 6 10 19 35 64 118 217 399 734 1350 2483 4567 lucas(4): 2 1 3 6 12 22 43 83 160 308 594 1145 2207 4254 8200 lucas(5): 2 1 3 6 12 24 46 91 179 352 692 1360 2674 5257 10335 lucas(6): 2 1 3 6 12 24 48 94 187 371 736 1460 2896 5744 11394 lucas(7): 2 1 3 6 12 24 48 96 190 379 755 1504 2996 5968 11888 lucas(8): 2 1 3 6 12 24 48 96 192 382 763 1523 3040 6068 12112 lucas(9): 2 1 3 6 12 24 48 96 192 384 766 1531 3059 6112 12212 lucas(10): 2 1 3 6 12 24 48 96 192 384 768 1534 3067 6131 12256
Mathematica
<lang Mathematica> f2=Function[{l,k},
Module[{n=Length@l,m}, m=SparseArray[{{i_,j_}/;i==1||i==j+1->1},{n,n}]; NestList[m.#&,l,k]]];
Table[Last/@f2[{1,1}~Join~Table[0,{n-2}],15+n]-18;;,{n,2,10}]//TableForm Table[Last/@f2[{1,2}~Join~Table[0,{n-2}],15+n]-18;;,{n,2,10}]//TableForm </lang> Output:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 2 1 3 6 10 19 35 64 118 217 399 734 1350 2483 4567 8400 15450 28417 2 1 3 6 12 22 43 83 160 308 594 1145 2207 4254 8200 15806 30467 58727 2 1 3 6 12 24 46 91 179 352 692 1360 2674 5257 10335 20318 39944 78528 2 1 3 6 12 24 48 94 187 371 736 1460 2896 5744 11394 22601 44831 88926 2 1 3 6 12 24 48 96 190 379 755 1504 2996 5968 11888 23680 47170 93961 2 1 3 6 12 24 48 96 192 382 763 1523 3040 6068 12112 24176 48256 96320 2 1 3 6 12 24 48 96 192 384 766 1531 3059 6112 12212 24400 48752 97408 2 1 3 6 12 24 48 96 192 384 768 1534 3067 6131 12256 24500 48976 97904
PARI/GP
The function gen
generates code to generate a given number of terms of the k-th sequence. Of course there are other approaches.
Use genV if you prefer to supply a different starting vector. <lang parigp>gen(n)=k->my(v=vector(k,i,1));for(i=3,min(k,n),v[i]=2^(i-2));for(i=n+1,k,v[i]=sum(j=i-n,i-1,v[j]));v genV(n)=v->for(i=3,min(#v,n),v[i]=2^(i-2));for(i=n+1,#v,v[i]=sum(j=i-n,i-1,v[j]));v for(n=2,10,print(n"\t"gen(n)(10)))</lang>
Perl
<lang perl>use 5.010;
use List::Util qw/max sum/;
sub fib {
my $n = shift; my $xs = shift // [1]; my @xs = @{$xs};
while (my $len = scalar @xs) { last if $len >= 20; push( @xs, sum(@xs[max($len - $n, 0)..$len-1]) ); } return @xs;
}
for (2..10) {
say join(' ', fib($_));
} say join(' ', fib(2, [2,1]));</lang>
- Output:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349
Perl 6
Lazy List with Closure
<lang perl6>sub fibo ($n) {
constant @starters = 1,1,2,4 ... *; nacci @starters[^$n];
}
sub nacci (*@starter) {
my &fun = eval join '+', '*' xx @starter; @starter, &fun ... *;
}
for 2..10 -> $n { say fibo($n)[^20] } say nacci(2,1)[^20];</lang>
- Output:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349
Generative
A slightly more straight forward way of constructing a lazy list.
<lang perl6>sub fib ($n, @xs is copy = [1]) {
gather { take @xs[*]; loop { take my $x = [+] @xs; @xs.push: $x; @xs.shift if @xs > $n; } }
}
for 2..10 -> $n {
say fib($n, [1])[^20];
} say fib(2, [2,1])[^20];</lang>
PicoLisp
<lang PicoLisp>(de nacci (Init Cnt)
(let N (length Init) (make (made Init) (do (- Cnt N) (link (apply + (tail N (made)))) ) ) ) )</lang>
Test: <lang PicoLisp># Fibonacci
- (nacci (1 1) 10)
-> (1 1 2 3 5 8 13 21 34 55)
- Tribonacci
- (nacci (1 1 2) 10)
-> (1 1 2 4 7 13 24 44 81 149)
- Tetranacci
- (nacci (1 1 2 4) 10)
-> (1 1 2 4 8 15 29 56 108 208)
- Lucas
- (nacci (2 1) 10)
-> (2 1 3 4 7 11 18 29 47 76)
- Decanacci
- (nacci (1 1 2 4 8 16 32 64 128 256) 15)
-> (1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172)</lang>
PL/I
<lang PL/I>(subscriptrange, fixedoverflow, size): n_step_Fibonacci: procedure options (main);
declare line character (100) varying; declare (i, j, k) fixed binary;
put ('n-step Fibonacci series: Please type the initial values on one line:'); get edit (line) (L); line = trim(line); k = tally(line, ' ') - tally(line, ' ') + 1; /* count values */
begin; declare (n(k), s) fixed decimal (15); get string (line || ' ') list ( n );
if n(1) = 2 then put ('We have a Lucan series'); else put ('We have a ' || trim(k) || '-step Fibonacci series.');
put skip edit ( (trim(n(i)) do i = 1 to k) ) (a, x(1)); do j = k+1 to 20; /* In toto, generate 20 values in the series. */ s = sum(n); /* the next value in the series */ put edit (trim(s)) (x(1), a); do i = lbound(n,1)+1 to k; /* Discard the oldest value */ n(i-1) = n(i); end; n(k) = s; /* and insert the new value */ end; end;
end n_step_Fibonacci;</lang> Output:
We have a Lucan series. 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 We have a 2-step Fibonacci series. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 We have a 3-step Fibonacci series. 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 We have a 4-step Fibonacci series. 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 We have a 5-step Fibonacci series. 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513
PureBasic
<lang PureBasic>
Procedure.i FibonacciLike(k,n=2,p.s="",d.s=".") Protected i,r if k<0:ProcedureReturn 0:endif if p.s n=CountString(p.s,d.s)+1 for i=0 to n-1 if k=i:ProcedureReturn val(StringField(p.s,i+1,d.s)):endif next else if k=0:ProcedureReturn 1:endif if k=1:ProcedureReturn 1:endif endif for i=1 to n r+FibonacciLike(k-i,n,p.s,d.s) next ProcedureReturn r EndProcedure
- The fact that PureBasic supports default values for procedure parameters
- is very useful in a case such as this.
- Since
- k=4
- Debug FibonacciLike(k) ;good old Fibonacci
- Debug FibonacciLike(k,3) ;here we specified n=3 [Tribonacci]
- Debug FibonacciLike(k,3,"1.1.2") ;using the default delimiter "."
- Debug FibonacciLike(k,3,"1,1,2",",") ;using a different delimiter ","
- the last three all produce the same result.
- as do the following two for the Lucas series
- Debug FibonacciLike(k,2,"2.1") ;using the default delimiter "."
- Debug FibonacciLike(k,2,"2,1",",") ;using a different delimiter ","
m=10 t.s=lset("n",5) for k=0 to m
t.s+lset(str(k),5) next
Debug t.s for n=2 to 10
t.s=lset(str(n),5) for k=0 to m t.s+lset(str(FibonacciLike(k,n)),5) next
Debug t.s next Debug "" p.s="2.1" t.s=lset(p.s,5) for k=0 to m
t.s+lset(str(FibonacciLike(k,n,p.s)),5) next
Debug t.s Debug ""
</lang>
Sample Output
n 0 1 2 3 4 5 6 7 8 9 10 2 1 1 2 3 5 8 13 21 34 55 89 3 1 1 2 4 7 13 24 44 81 149 274 4 1 1 2 4 8 15 29 56 108 208 401 5 1 1 2 4 8 16 31 61 120 236 464 6 1 1 2 4 8 16 32 63 125 248 492 7 1 1 2 4 8 16 32 64 127 253 504 8 1 1 2 4 8 16 32 64 128 255 509 9 1 1 2 4 8 16 32 64 128 256 511 10 1 1 2 4 8 16 32 64 128 256 512 2.1 2 1 3 4 7 11 18 29 47 76 123
Python
Python: function returning a function
<lang python>>>> def fiblike(start): addnum = len(start) memo = start[:] def fibber(n): try: return memo[n] except IndexError: ans = sum(fibber(i) for i in range(n-addnum, n)) memo.append(ans) return ans return fibber
>>> fibo = fiblike([1,1]) >>> [fibo(i) for i in range(10)] [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> lucas = fiblike([2,1]) >>> [lucas(i) for i in range(10)] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] >>> for n, name in zip(range(2,11), 'fibo tribo tetra penta hexa hepta octo nona deca'.split()) : fibber = fiblike([1] + [2**i for i in range(n-1)]) print('n=%2i, %5snacci -> %s ...' % (n, name, ' '.join(str(fibber(i)) for i in range(15))))
n= 2, fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ...
n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ...
n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ...
n= 6, hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ...
n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ...
n= 8, octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ...
n= 9, nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ...
n=10, decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
>>> </lang>
Python: Callable class
<lang python>>>> class Fiblike(): def __init__(self, start): self.addnum = len(start) self.memo = start[:] def __call__(self, n): try: return self.memo[n] except IndexError: ans = sum(self(i) for i in range(n-self.addnum, n)) self.memo.append(ans) return ans
>>> fibo = Fiblike([1,1])
>>> [fibo(i) for i in range(10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> lucas = Fiblike([2,1])
>>> [lucas(i) for i in range(10)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
>>> for n, name in zip(range(2,11), 'fibo tribo tetra penta hexa hepta octo nona deca'.split()) :
fibber = Fiblike([1] + [2**i for i in range(n-1)])
print('n=%2i, %5snacci -> %s ...' % (n, name, ' '.join(str(fibber(i)) for i in range(15))))
n= 2, fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ...
n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ...
n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ...
n= 6, hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ...
n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ...
n= 8, octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ...
n= 9, nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ...
n=10, decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
>>> </lang>
Python: Generator
<lang python>from itertools import islice, cycle
def fiblike(tail):
for x in tail: yield x for i in cycle(xrange(len(tail))): tail[i] = x = sum(tail) yield x
fibo = fiblike([1, 1]) print list(islice(fibo, 10)) lucas = fiblike([2, 1]) print list(islice(lucas, 10))
suffixes = "fibo tribo tetra penta hexa hepta octo nona deca" for n, name in zip(xrange(2, 11), suffixes.split()):
fib = fiblike([1] + [2 ** i for i in xrange(n - 1)]) items = list(islice(fib, 15)) print "n=%2i, %5snacci -> %s ..." % (n, name, items)</lang>
- Output:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55] [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] n= 2, fibonacci -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] ... n= 3, tribonacci -> [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136] ... n= 4, tetranacci -> [1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536] ... n= 5, pentanacci -> [1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930] ... n= 6, hexanacci -> [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617] ... n= 7, heptanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936] ... n= 8, octonacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080] ... n= 9, nonanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144] ... n=10, decanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172] ...
REXX
<lang rexx>/*REXX program calculates and displays N-step Fibonacci sequences. */ parse arg FibName values /*allow user to specify which Fib*/
if FibName\= then do /*if specified, show that Fib. */
call nStepFib FibName,values exit end /*nothing given, so show a bunch.*/
call nStepFib 'Lucas',2 1 call nStepFib 'fibonacci',1 1 call nStepFib 'tribonacci',1 1 2 call nStepFib 'tetranacci',1 1 2 4 call nStepFib 'pentanacci',1 1 2 4 8 call nStepFib 'hexanacci',1 1 2 4 8 16 call nStepFib 'heptanacci',1 1 2 4 8 16 32 call nStepFib 'octonacci',1 1 2 4 8 16 32 64 call nStepFib 'nonanacci',1 1 2 4 8 16 32 64 128 call nStepFib 'decanacci',1 1 2 4 8 16 32 64 128 256 call nStepFib 'undecanacci',1 1 2 4 8 16 32 64 128 256 512 call nStepFib 'dodecanacci',1 1 2 4 8 16 32 64 128 256 512 1024 call nStepFib '13th-order',1 1 2 4 8 16 32 64 128 256 512 1024 2048 exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────NSTEPFIB subroutine─────────────────*/ nStepFib: procedure; parse arg Fname,vals,m; if m== then m=30; L= N=words(vals); do pop=1 for N; @.pop=word(vals,pop); end /*populate*/
do j=1 for m /*calculate M Fibonacci numbers*/ if j>N then do; s=0; do k=j-N for N; s=s+@.k; end /*k*/ @.j=s /*assign this sum to the series. */ end L=L @.j /*append this Fib num to the list*/ end /*j*/
say right(Fname,11)'[sum' N "terms]:" strip(L) '...' /*show&tell time*/ return</lang> output when using the default input
Lucas[sum 2 terms]: 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127 24476 39603 64079 103682 167761 271443 439204 710647 1149851 ... fibonacci[sum 2 terms]: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 ... tribonacci[sum 3 terms]: 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 121415 223317 410744 755476 1389537 2555757 4700770 8646064 15902591 29249425 ... tetranacci[sum 4 terms]: 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 283953 547337 1055026 2033628 3919944 7555935 14564533 28074040 54114452 104308960 ... pentanacci[sum 5 terms]: 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513 400096 786568 1546352 3040048 5976577 11749641 23099186 45411804 89277256 175514464 ... hexanacci[sum 6 terms]: 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904 463968 920319 1825529 3621088 7182728 14247536 28261168 56058368 111196417 220567305 ... heptanacci[sum 7 terms]: 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888 495776 987568 1967200 3918592 7805695 15548665 30972384 61695880 122895984 244804400 ... octonacci[sum 8 terms]: 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005 510994 1019960 2035872 4063664 8111200 16190208 32316160 64504063 128752121 256993248 ... nonanacci[sum 9 terms]: 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328 518145 1035269 2068498 4132920 8257696 16499120 32965728 65866496 131603200 262947072 ... decanacci[sum 10 terms]: 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864 521472 1042432 2083841 4165637 8327186 16646200 33276064 66519472 132973664 265816832 ... undecanacci[sum 11 terms]: 1 1 2 4 8 16 32 64 128 256 512 1024 2047 4093 8184 16364 32720 65424 130816 261568 523008 1045760 2091008 4180992 8359937 16715781 33423378 66830392 133628064 267190704 ... dodecanacci[sum 12 terms]: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4095 8189 16376 32748 65488 130960 261888 523712 1047296 2094336 4188160 8375296 16748544 33492993 66977797 133939218 267845688 ... 13th-order[sum 13 terms]: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8191 16381 32760 65516 131024 262032 524032 1048000 2095872 4191488 8382464 16763904 33525760 67047424 134086657 268156933 ...
Tcl
<lang tcl>package require Tcl 8.6
proc fibber {args} {
coroutine fib[incr ::fibs]=[join $args ","] apply {fn {
set n [info coroutine] foreach f $fn { if {![yield $n]} return set n $f } while {[yield $n]} { set fn [linsert [lreplace $fn 0 0] end [set n [+ {*}$fn]]] }
} ::tcl::mathop} $args
}
proc print10 cr {
for {set i 1} {$i <= 10} {incr i} {
lappend out [$cr true]
} puts \[[join [lappend out ...] ", "]\] $cr false
} puts "FIBONACCI" print10 [fibber 1 1] puts "TRIBONACCI" print10 [fibber 1 1 2] puts "TETRANACCI" print10 [fibber 1 1 2 4] puts "LUCAS" print10 [fibber 2 1]</lang>
- Output:
FIBONACCI [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...] TRIBONACCI [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ...] TETRANACCI [1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...] LUCAS [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, ...]
XPL0
<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations
proc Nacci(N, F0); \Generate Fibonacci N-step sequence int N, \step size
F0; \array of first N values
int I, J; def M = 10; \number of members in the sequence int F(M); \Fibonacci sequence [for I:= 0 to M-1 do \for all the members of the sequence...
[if I < N then F(I):= F0(I) \initialize sequence else [F(I):= 0; \sum previous members to get member I for J:= 1 to N do F(I):= F(I) + F(I-J); ]; IntOut(0, F(I)); ChOut(0, ^ ); ];
CrLf(0); ];
[Text(0, " Fibonacci: "); Nacci(2, [1, 1]);
Text(0, "Tribonacci: "); Nacci(3, [1, 1, 2]); Text(0, "Tetranacci: "); Nacci(4, [1, 1, 2, 4]); Text(0, " Lucas: "); Nacci(2, [2, 1]);
]</lang>
Output:
Fibonacci: 1 1 2 3 5 8 13 21 34 55 Tribonacci: 1 1 2 4 7 13 24 44 81 149 Tetranacci: 1 1 2 4 8 15 29 56 108 208 Lucas: 2 1 3 4 7 11 18 29 47 76