Fibonacci n-step number sequences: Difference between revisions
(Add ref.) |
(Lucas number ref.) |
||
Line 6: | Line 6: | ||
# For general <math>n>2</math> we have the Fibonacci n-step sequence - <math>F_k^n</math>; with initial values of the first n values of the (n-1)'th Fibonacci n-step sequence <math>F_k^{n-1}</math>; and k'th value of this n'th sequence being <math>F_k^n = \sum_{i=1}^{(n)} {F_{k-i}^{(n)}}</math> |
# For general <math>n>2</math> we have the Fibonacci n-step sequence - <math>F_k^n</math>; with initial values of the first n values of the (n-1)'th Fibonacci n-step sequence <math>F_k^{n-1}</math>; and k'th value of this n'th sequence being <math>F_k^n = \sum_{i=1}^{(n)} {F_{k-i}^{(n)}}</math> |
||
Allied sequences can be generated where the initial values are changed |
Allied sequences can be generated where the initial values are changed: |
||
: The [[wp:Lucas number|Lucas series]] sums the two preceeding values like the fibonacci series for <math>n=2</math> but has the values <math>[2, 1]</math> as its initial values. |
|||
The task is to: |
The task is to: |
Revision as of 05:35, 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
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 has the values 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 the first ten members of the Fibo/tribo/tetra-nacci and Lucas sequences.
- C.f
Python
<lang python>>>> def fiblike(start): addnum = len(start) def fibber(n): try: return fibber.memo[n] except: 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] >>> f3= fiblike([1,1,2]) # tribo- >>> [f3(i) for i in range(10)] [1, 1, 2, 4, 7, 13, 24, 44, 81, 149] >>> f4 = fiblike([1,1,2,4]) # tetra- >>> [f4(i) for i in range(10)] [1, 1, 2, 4, 8, 15, 29, 56, 108, 208] >>> f5 = fiblike([1,1,2,4,8]) # penta- >>> [f5(i) for i in range(10)] [1, 1, 2, 4, 8, 16, 31, 61, 120, 236] >>> f6 = fiblike([1,1,2,4,8,16]) # hexa- >>> [f6(i) for i in range(10)] [1, 1, 2, 4, 8, 16, 32, 63, 125, 248] >>> f7 = fiblike([1,1,2,4,8,16,32]) # hepta >>> [f7(i) for i in range(10)] [1, 1, 2, 4, 8, 16, 32, 64, 127, 253] >>> </lang>
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, ...]