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?

In this post, a number of techniques are provided: http://stackoverflow.com/questions/18172257/efficient-calculation-of-fibonacci-series — ShadyFortress, Mar 14 '14 at 12:29
What do you mean with "Doesn't work"? Wrong answer, exception, crash? — simon, Mar 14 '14 at 12:40
_"The method I've used to try and solve this works"_. Are you sure about that? It just gives me zero for any input I give it. And that's after fixing the bad indentation of `return fib_even`. Can you double check that you formatted your code correctly here? — Kevin, Mar 14 '14 at 12:59
Every third Fibonacci number is even, so you could count those. This, incidentally, is the subject of the second question in the Euler Project, https://projecteuler.net/problem=2 — cjohnson318, Mar 14 '14 at 13:32
Your code uses a tremendous amount of storage, both because it (unnecessarily) creates the `fib_even` list, which has some very large numbers in it, and in iterating over it while calculating the sum (which is a _huge_ number). In Python number can be any size, and above a certain point, the amount of memory required to do so depends on their magnitude. — martineau, Mar 14 '14 at 14:27
it is allmost impossible not to find solutions to the euler problem 2 here. Look at the related posts — miracle173, Mar 15 '14 at 08:26
4000000-th Fibonacci number has about 835951 digits. As @lhf pointed out you misread the project euler problem 2 question — miracle173, Mar 15 '14 at 08:46
To complement the next to last remark, an appropriate query string gives http://stackoverflow.com/search?tab=votes&q=fibonacci%20even%20million%20euler — Lutz Lehmann, Mar 15 '14 at 15:00

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

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.

Python can store integers of virtually any size, limited to the available (and addressable) memory. `4,000,000 / 20 == 200,000`, not `800,000`. — martineau, Mar 14 '14 at 14:41
Yes, 200,000 blocks of 20 Fibonacci numbers, and after each block, the numbers are 4 digits longer, making a total of 800,000 digits. However, the problem was severely misstated, the solution of the original problem only requires all F[3*k] up to F[33] or with a clever formula only F[35]. — Lutz Lehmann, Mar 14 '14 at 15:00

score 0 · Answer 2 · answered Mar 14 '14 at 12:37

0

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

answered Mar 14 '14 at 12:37

Codor

17,447
9
29
56

True, but it's only storing the even ones and most computers can easily store a list of up to 4 million numbers. It would also be easy to test your theory, so why didn't you? – martineau Mar 14 '14 at 13:55
More to the point, storing all the intermediate fibonacci numbers saves them being recomputed multiple times. Storing them is a literal textbook example of making fibonacci more efficient using dynamic programing. – Joe Mar 15 '14 at 09:26

sum of even fibonacci numbers up to 4million

2 Answers2

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

Summation of the even Fibonacci numbers

Reduction of the Euler problem to a simple formula

Reduction of the problem in the question and consequences