CODEWITHSUNDEEP
pythonmathfibonacci
user2652949
user2652949

Reputation: 13

sum of even fibonacci numbers up to 4million

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?

Upvotes: 0

Views: 1004

Answers (2)

Lutz Lehmann
Lutz Lehmann

Reputation: 25992

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.

Upvotes: 3

Codor
Codor

Reputation: 17605

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

Upvotes: 0

Related Questions