Fibonacci n-step number sequences: Difference between revisions
m (→Generator) |
|||
Line 138: | Line 138: | ||
import Control.Monad (zipWithM_) |
import Control.Monad (zipWithM_) |
||
fiblike :: |
fiblike :: [Integer] -> [Integer] |
||
fiblike |
fiblike st = xs where |
||
xs = st ++ map (sum . take n) (tails xs) |
xs = st ++ map (sum . take n) (tails xs) |
||
n = length st |
|||
nstep :: Int -> [Integer] |
nstep :: Int -> [Integer] |
||
nstep n = fiblike |
nstep n = fiblike $ take n $ 1 : iterate (2*) 1 |
||
main :: IO () |
main :: IO () |
||
main = do |
main = do |
||
print $ take 10 $ fiblike |
print $ take 10 $ fiblike [1,1] |
||
print $ take 10 $ fiblike |
print $ take 10 $ fiblike [2,1] |
||
zipWithM_ (\n name -> do putStr (name ++ "nacci -> ") |
zipWithM_ (\n name -> do putStr (name ++ "nacci -> ") |
||
print $ take 15 $ nstep n) |
print $ take 15 $ nstep n) |
Revision as of 08:35, 26 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;
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 ...
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) /*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), " "); 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>
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]
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 collections import deque >>> def fiblike(start): ... q = deque() ... for x in start: ... yield x ... q.append(x) ... while True: ... x = sum(q) ... yield x ... q.popleft() ... q.append(x) ... >>> from itertools import islice >>> fibo = fiblike([1,1]) >>> list(islice(fibo, 10)) [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> lucas = fiblike([2,1]) >>> list(islice(lucas, 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, 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] ... 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, ...]