Project Euler Question #2: Sum of even Fibonacci numbers under 4 million

Question

The question is:

Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

#Problem 2
P2 = 0
fib= 0
f1 = 1
f2 = 0
debugP2 = []
while fib < 4000000:
    fib = f1 + f2
    f2 = f1
    f1 = fib
    if fib % 2 == 0:
        P2 += fib
        debugP2.append(fib)
print(debugP2)
print(P2)

This script can

1. Give me all Fibonacci numbers up to 4000000

2. Give the sum of all even numbers up to 4000000

3. It satisfies Project Euler Question #2.

Is there a way to make this shorter or more efficient?

Answer 1

Your current implementation, and the suggested improvements are all brute force implementations, i.e. enumerating all fibonacci numbers, and they will all run in O(n).

By using some mathematical tricks, you can turn this into an O(1) implementation. Since this is a project Euler problem, I won't spell out the answer, but here are some pointers:

1. When starting at F(0) = 1 (instead of starting at F(1) as in the problem description), every third number is an even fibonacci number

2. Because the fibonacci numbers are by definition based on the addition of the previous two numbers, the sum of all even fibonacci numbers up to n is equal to the sum of all fibonacci numbers up to n divided by two.

3. There are cool formula's to calculate the sum of fibonacci numbers and the index of the highest fibonacci number up to n. Refer to wolframalpha or wikipedia to find them.

Answer 2

More elegantly, using a generator:

def fib(max):
    f1, f2 = 0, 1
    while f1 < max:
        yield f1
        f1, f2 = f2, f1 + f2

print(sum(filter(lambda n: n % 2 == 0, fib(4000000))))

I would consider this to be more elegant because it decomposes the problem into describable, reusable components, instead of mingling all the logic together:

• The fib() generator is responsible for generating Fibonacci numbers
• filter(lambda n: n % 2 == 0, ...) keeps just the even-valued elements
• sum(...) adds them up

Answer 3

Assuming you want to stick with a minimalist for-loop implementation, it could be simplified by using Python's simultaneous assignment feature to eliminate a variable and perform the "swap" gracefully. Of course, the question does not require you to produce the even-valued items of the Fibonacci sequence, so you could eliminate debugP2 as well.

sum = 0
f1, f2 = 0, 1
while f2 < 4000000:
    if f2 % 2 == 0:
        sum += f2
    f1, f2 = f2, f1 + f2
print(sum)