sum of even fibonacci numbers up to 4million

Question

The method I've used to try and solve this works but I don't think it's very efficient because as soon as I enter a number that is too large it doesn't work.

def fib_even(n):
    fib_even = []
    a, b = 0, 1
    for i in range(0,n):
        c = a+b
        if c%2 == 0:
            fib_even.append(c)
            a, b = b, a+b
return fib_even

def sum_fib_even(n):
    fib_evens = fib_even(n)
    s = 0
    for i in fib_evens:
        s = s+i
    return s

n = 4000000
answer = sum_fib_even(n)
print answer

This for example doesn't work for 4000000 but will work for 400. Is there a more efficient way of doing this?

Answer 1

It is not necessary to compute all the Fibonacci numbers.

Note: I use in what follows the more standard initial values F[0]=0, F[1]=1 for the Fibonacci sequence. Project Euler #2 starts its sequence with F[2]=1,F[3]=2,F[4]=3,.... For this problem the result is the same for either choice.

Summation of all Fibonacci numbers (as a warm-up)

The recursion equation

F[n+1] = F[n] + F[n-1]

can also be read as

F[n-1] = F[n+1] - F[n]

or

F[n] = F[n+2] - F[n+1]

Summing this up for n from 1 to N (remember F[0]=0, F[1]=1) gives on the left the sum of Fibonacci numbers, and on the right a telescoping sum where all of the inner terms cancel

sum(n=1 to N) F[n] = (F[3]-F[2]) + (F[4]-F[3]) + (F[5]-F[4])
                     + ... + (F[N+2]-F[N+1])
                   = F[N+2] - F[2] 

So for the sum using the number N=4,000,000 of the question one would have just to compute

F[4,000,002] - 1

with one of the superfast methods for the computation of single Fibonacci numbers. Either halving-and-squaring, equivalent to exponentiation of the iteration matrix, or the exponential formula based on the golden ratio (computed in the necessary precision).

Since about every 20 Fibonacci numbers you gain 4 additional digits, the final result will consist of about 800000 digits. Better use a data type that can contain all of them.

---

Summation of the even Fibonacci numbers

Just inspecting the first 10 or 20 Fibonacci numbers reveals that all even members have an index of 3*k. Check by subtracting two successive recursions to get

F[n+3]=2*F[n+2]-F[n]

so F[n+3] always has the same parity as F[n]. Investing more computation one finds a recursion for members three indices apart as

F[n+3] = 4*F[n] + F[n-3]

Setting

S = sum(k=1 to K) F[3*k]

and summing the recursion over n=3*k gives

F[3*K+3]+S-F[3] = 4*S + (-F[3*K]+S+F[0])

or

4*S = (F[3*K]+F[3*K]) - (F[3]+F[0]) = 2*F[3*K+2]-2*F[2]

So the desired sum has the formula

S = (F[3*K+2]-1)/2

A quick calculation with the golden ration formula reveals what N should be so that F[N] is just below the boundary, and thus what K=N div 3 should be,

N = Floor(  log( sqrt(5)*Max )/log( 0.5*(1+sqrt(5)) )  )

---

Reduction of the Euler problem to a simple formula

In the original problem, one finds that N=33 and thus the sum is

S = (F[35]-1)/2;

---

Reduction of the problem in the question and consequences

Taken the mis-represented problem in the question, N=4,000,000, so K=1,333,333 and the sum is

(F[1,333,335]-1)/2

which still has about 533,400 digits. And yes, biginteger types can handle such numbers, it just takes time to compute with them.

If printed in the format of 60 lines a 80 digits, this number fills 112 sheets of paper, just to get the idea what the output would look like.

Answer 2

It should not be necessary to store all intermediate Fibonacci numbers, perhaps the storage causes a performance problem.