Sum of even Fibonacci numbers

Question

So, in my first attempt I created a code that generated all fibonacci numbers and appended to a list. This list I then traversed to get the even numbers and added them up. It worked, but took like 5 complete seconds to work. Then I decided to not create a list and add the even numbers as I'm generating them. It looked like this

a = 1
b = 1
c = 0
Sum = 0
while c<4000000:
    c = a + b
    if c%2==0:
        Sum+=c
    a = b
    b = c
print Sum

It still took quite a lot of time (didn't record it) compared to the people who got it done in like 100 milliseconds or something (I got this question on Project Euler). Is there a way to make it faster? Here's the link to the problem

https://projecteuler.net/problem=2

Answer 1

Obviously, every third Fibonacci number is even, and the rest of them are odd. Less obviously (but trivially follows from, say, Binet's formula), they satisfy another linear recurrence:

\$F_{3(n+1)} = 4 F_{3n} + F_{3(n-1)}\$

Using this fact, you may cut the execution time threefold.

Answer 2

You should adhere to the recommendations of pythons official style-guide, PEP8. This means using lower_case for variable (and function) names. CamelCase is recommended for classes only.

At the same time it recommends using a leading _ if you would otherwise shadow a built-in variable. So I would use _sum or even better the more descriptive even_sum instead of Sum.

It also recommends putting spaces around operators.

---

You could use python's tuple assignment to shorten your code a bit:

a, b, c = b, c, a+b

---

Final code:

I used fn for \$f_n\$ (the current fibonacci number), fn_1 for \$f_{n-1}\$ and fn_2 for \$f_{n-2}\$.

I put the code into a function to allow reusability.

def even_fib_sum(limit=4000000):
    fn_2, fn_1, fn = 1, 1, 0
    even_sum = 0
    while fn < limit:
        fn_2, fn_1, fn = fn_1, fn, fn_1 + fn_2
        if fn%2 == 0:
            even_sum += fn
    return even_sum

print even_fib_sum()

Answer 3

The Fibonacci sequence grows fast enough that it exceeds 4 000 000 with its 34th term, as shown on the OEIS.

Given this fact, hardcoding the set of even Fibonacci numbers under 4 000 000 - or even their sum - would be far from impractical and would be an obvious solution to drastically increase execution time.

Answer 4

Firstly, we can observe that the sum of Fibonacci numbers is simply offset from a Fibonacci number. I'll take the convention that \$F_0 = 0\$, \$F_1 = 1\$. Then $$\sum_{i=0}^n F_i = F_{n+2} - 1$$ Proof by induction is easy: \$\sum_{i=0}^{n+1} F_i = F_{n+1} + \sum_{i=0}^n F_i = F_{n+1} + F_{n+2} - 1 = F_{n+3}-1\$.

Secondly, we can observe that since the Fibonacci numbers go odd, odd, even, the sum of the first \$n\$ even Fibonacci numbers is the sum of the first \$2n\$ odd Fibonacci numbers, and half the sum of the first \$3n\$ Fibonacci numbers. I.e. $$\sum_{i=1}^n F_{3n} = \frac{F_{3n+2} - 1}2$$

So you can skip the sum provided that you can compute how many terms you need. And you can compute the \$n\$^th Fibonacci number in \$O(\lg n)\$ operations using \$F_{m+n} = F_{m+1} F_n + F_m F_{n-1}\$.