Fibonacci n-step number sequences: Difference between revisions
(→{{header|REXX}}: added the REXX language. -- ~~~~) |
(+ two D versions) |
||
Line 44: | Line 44: | ||
* [http://mathworld.wolfram.com/Fibonaccin-StepNumber.html Wolfram Mathworld] |
* [http://mathworld.wolfram.com/Fibonaccin-StepNumber.html Wolfram Mathworld] |
||
* [[Hofstadter Q sequence]] |
* [[Hofstadter Q sequence]] |
||
=={{header|D}}== |
|||
<lang d>import std.stdio, std.algorithm, std.range, std.conv, std.functional; |
|||
void main() { |
|||
int[] head; |
|||
int fibber(in size_t n) /*nothrow*/ { |
|||
alias memoize!fibber f; |
|||
if (n < head.length) |
|||
return head[n]; |
|||
return iota(n - head.length, n).map!f().reduce!q{a + b}(); |
|||
} |
|||
head = [1, 1]; |
|||
iota(10).map!fibber().writeln(); |
|||
head = [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())) { |
|||
head = [1] ~ iota(n-1).map!q{2 ^^ a}().array(); |
|||
const items = iota(15).map!(i => text(fibber(i)))().join(" "); |
|||
writefln("n=%2d, %5snacci -> %s ...", n, name, items); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>[1, 1, 2, 3, 5, 8, 13, 21, 34, 55] |
|||
[2, 1, 2, 3, 5, 8, 13, 21, 34, 55] |
|||
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 6 10 16 26 42 68 110 178 288 466 754 ... |
|||
n= 4, tetranacci -> 1 1 2 4 7 11 18 29 47 76 123 199 322 521 843 ... |
|||
n= 5, pentanacci -> 1 1 2 4 8 12 19 31 50 81 131 212 343 555 898 ... |
|||
n= 6, hexanacci -> 1 1 2 4 8 16 20 32 52 84 136 220 356 576 932 ... |
|||
n= 7, heptanacci -> 1 1 2 4 8 16 32 33 53 86 139 225 364 589 953 ... |
|||
n= 8, octonacci -> 1 1 2 4 8 16 32 64 54 87 141 228 369 597 966 ... |
|||
n= 9, nonanacci -> 1 1 2 4 8 16 32 64 128 88 142 230 372 602 974 ... |
|||
n=10, decanacci -> 1 1 2 4 8 16 32 64 128 256 143 231 374 605 979 ...</pre> |
|||
===Alternative Version=== |
|||
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) { |
|||
if (n < memo.length) { |
|||
return memo[n]; |
|||
} else { |
|||
auto ans = iota(n - addNum, n) |
|||
.map!(i => opCall(i))().reduce!q{a + b}(); |
|||
memo ~= ans; |
|||
return ans; |
|||
} |
|||
} |
|||
} |
|||
void main() { |
|||
auto fibo = fiblike!int([1, 1]); |
|||
//writeln(iota(10).map!fibo()); |
|||
foreach (i; 0 .. 10) |
|||
//write(fibo(i), " "); |
|||
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 fibber = fiblike!int([1] ~ iota(n-1) |
|||
.map!q{2 ^^ a}().array()); |
|||
//auto items = iota(15).map!(i => text(fibber(i)))().join(" "); |
|||
string[] items; |
|||
foreach (i; 0 .. 15) |
|||
//items ~= text(fibber(i)); |
|||
items ~= text(fibber.opCall(i)); |
|||
writefln("n=%2d, %5snacci -> %s ...", n,name, items.join(" ")); |
|||
} |
|||
}</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 21:51, 25 May 2012
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 n-step sequence - ; with initial values of the first n values of the (n-1)'th Fibonacci n-step sequence ; and k'th value of this n'th sequence being
For small values of n, Greek numeric prefixes are sometimes used to individually name each series.
Fibonacci n-step sequences n 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 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.
- Use this to print and show here at least the first ten members of the Fibo/tribo/tetra-nacci and Lucas sequences.
- Cf.
D
<lang d>import std.stdio, std.algorithm, std.range, std.conv, std.functional;
void main() {
int[] head; int fibber(in size_t n) /*nothrow*/ { alias memoize!fibber f; if (n < head.length) return head[n]; return iota(n - head.length, n).map!f().reduce!q{a + b}(); }
head = [1, 1]; iota(10).map!fibber().writeln(); head = [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())) { head = [1] ~ iota(n-1).map!q{2 ^^ a}().array(); const 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, 2, 3, 5, 8, 13, 21, 34, 55] 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 6 10 16 26 42 68 110 178 288 466 754 ... n= 4, tetranacci -> 1 1 2 4 7 11 18 29 47 76 123 199 322 521 843 ... n= 5, pentanacci -> 1 1 2 4 8 12 19 31 50 81 131 212 343 555 898 ... n= 6, hexanacci -> 1 1 2 4 8 16 20 32 52 84 136 220 356 576 932 ... n= 7, heptanacci -> 1 1 2 4 8 16 32 33 53 86 139 225 364 589 953 ... n= 8, octonacci -> 1 1 2 4 8 16 32 64 54 87 141 228 369 597 966 ... n= 9, nonanacci -> 1 1 2 4 8 16 32 64 128 88 142 230 372 602 974 ... n=10, decanacci -> 1 1 2 4 8 16 32 64 128 256 143 231 374 605 979 ...
Alternative Version
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) { if (n < memo.length) { return memo[n]; } else { auto ans = iota(n - addNum, n) .map!(i => opCall(i))().reduce!q{a + b}(); memo ~= ans; return ans; } }
}
void main() {
auto fibo = fiblike!int([1, 1]); //writeln(iota(10).map!fibo()); foreach (i; 0 .. 10) //write(fibo(i), " "); 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 fibber = fiblike!int([1] ~ iota(n-1) .map!q{2 ^^ a}().array()); //auto items = iota(15).map!(i => text(fibber(i)))().join(" "); string[] items; foreach (i; 0 .. 15) //items ~= text(fibber(i)); items ~= text(fibber.opCall(i)); writefln("n=%2d, %5snacci -> %s ...", n,name, items.join(" ")); }
}</lang>
Python
<lang python>>>> def fiblike(start): addnum = len(start) def fibber(n): try: return fibber.memo[n] except IndexError: ans = sum(fibber(i) for i in range(n-addnum, n)) fibber.memo.append(ans) return ans fibber.memo = start[:] 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>
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, ...]