Fibbonaci-like Sequence Of Last 3 Numbers

Is there a non-recursive way I can make a 'Fibonacci-like'sequence of the by adding the last 3 numbers? Here's the recursive way I tried to do it. def fib3(n): if n < 3:

Solution 1:

Yes, and quite elegantly, with Python's multiple assignment ability:

>>>deffib3(n):...if n < 3:...return1...    a = b = c = 1...for i inrange(3, n):...# We "shift" a, b, and c to the next values of the sequence....        a, b, c = b, c, (a + b + c)...return c...>>>fib3(4)
3
>>>fib3(5)
5
>>>fib3(6)
9
>>>fib3(7)
17

And the iterative method would definitely be preferred to the recursive method - as @mu writes, the running time of the recursive implementation is approximately O(3^n), while this method is O(n).

Solution 2:

fib_sum to calculate m last integer:

>>>deffib_sum(n,m):
        if n < m:
            return "n should be greater than m"
        a,b,sumit = 0,1,0
        for x in range(n):
            print b,
            if x >= n-m:
                sumit += b
            a,b = b,a+b
        return sumit

>>>fib_sum(3,4)
'n should be greater than m'
>>>fib_sum(3,2)
1 1 2
3
>>>fib_sum(3,1)
1 1 2
2
>>>fib_sum(2,1)
1 1
1
>>>fib_sum(2,2)
1 1 
2
>>>fib_sum(7,2)
1 1 2 3 5 8 13
21
>>>fib_sum(7,3)
1 1 2 3 5 8 13
26
>>>fib_sum(8,6)
1 1 2 3 5 8 13 21
52
>>>fib_sum(8,8)
1 1 2 3 5 8 13 21
54

Solution 3:

I've arrived late at the party, but: one can easily derive a formula to get the n'th element of any linear recurrence such as the Fibonacci sequence or a generalization of that, without having to compute all the intermediate elements. Say your recurrence is f[n] = a[1] f[n - 1] + a[2] f[n - 2] + ... + a[m] f[n - m]. Suppose that f[n] = (some constant)^n. (This is the kind of "lucky guess" hypothesis that often appears in solutions for differential equations. I don't know how to justify it a priori. It can be justified after the fact by actually finding such a constant.) Then the constant must be a root of the polynomial x^m - a[1] x^(m - 1) - a[2] x^(m - 2) - ... - a[m]. Any linear combination of solutions must also be a solution. You can find the coefficients c[1], ..., c[m] for the linear combination by solving the linear system derived from the first m values (obviously the value of all the later values in the sequence are determined by the first m values).

For the stated recurrence f[n] = f[n - 1] + f[n - 2] + f[n - 3], we have a[1] = a[2] = a[3] = 1 and the roots of x^3 - x^2 - x - 1 are - 0.6063 %i - 0.4196, 0.6063 %i - 0.4196, 1.839, respectively. It is given that the first 3 values are 1, 1, 1. Solving c[1] + c[2] + c[3] = 1, c[1] a[1] + c[2] a[2] + c[3] a[3] = 1, c[1] a[1]^2 + c[2] a[2]^2 + c[3] a[3]^2 = 1 for c[1], c[2], c[3] yields 0.3592 %i + 0.2822, 0.2822 - 0.3592 %i, 0.4356, respectively. (I've written these as approximate, floating point numbers. As roots of polynomials with rational coefficients, these are algebraic numbers, but exact expressions might easily become messy.)

In summary, f[n] = c[1] a[1]^n + c[2] a[2]^n + c[3] a[3]^n, with the stated values for the a's and c's, is a function which gives the n'th element of the recurrence f[n] = f[n - 1] + f[n - 2] + f[n - 3], with f[2] = f[1] = f[0] = 1.

I calculated the a's and c's in Maxima. I can say more about how I did that if there is any interest.