Fibonacci n-step number sequences
You are encouraged to solve this task according to the task description, using any language you may know.
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
![{\displaystyle [1, 1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a93c33bf544dd008f34d152345c97525bda7fe8)
![{\displaystyle [1, 1, 2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d71f58dd89883e71cb666a8522a27b5691e501e)
![{\displaystyle [1, 1, 2, 4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d79ac367ab68d7a724b5e6187f58c6b3f2e635dd)
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.
![{\displaystyle [2, 1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d31e115ea18c317bc1a35526e68c32612274bcb1)
- 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.
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)
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(T[] start) /*nothrow*/ {
this.memo = start.dup;
this.addNum = start.length;
}
T opCall(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]);
//writeln(iota(10).map!fibo());
foreach (i; 0 .. 10)
//write(fibo(i), " "); // opCall doesn't work
write(fibo.opCall(i), " ");
writeln();
auto lucas = fiblike!int([2, 1]);
//writeln(iota(10).map!lucas());
foreach (i; 0 .. 10)
//write(lucas(i), " ");
write(lucas.opCall(i), " ");
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());
//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>
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>
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]
Perl 6
<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
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>
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 to calculate and display 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 /*─────────────────────────────────────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, ...]