Fibonacci n-step number sequences: Difference between revisions
(New draft task and Python solution) |
(→{{header|Python}}: filled-out) |
||
Line 16: | Line 16: | ||
=={{header|Python}}== |
=={{header|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> |
Revision as of 21:57, 24 May 2012
These number series are an expansion of the ordinary Fibonacci sequence where:
- For n = 2 we have the Fibonacci sequence; with initial values [1, 1] and
- For n = 3 we have the tribonacci sequence; with initial values [1, 1, 2] and
- For n = 4 we have the tetranacci sequence; with initial values [1, 1, 2, 4] and
... - For general n>2 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 n==2 but has the values [2, 1] 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>