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

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?

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.

• Upvoted for interesting mathematical observations, even though it's not exactly a code review. In practice, applying the O(1) formula is not that easy, and the "brute-force" approach might be faster once you consider the ease of implementation vs. the trivial amount of computation involved. Nov 19, 2013 at 11:09
• @200_success you raise an interesting point -- in my opinion, discussions about the underlying algorithm and its impact on performance are part of a code review. However, the about pages are a bit vague on this. Could anyone clarify? Nov 19, 2013 at 12:44
• I take that back about "not exactly a code review". "You used the wrong algorithm because …" is perfectly fair as a review. It's just that I disagree that your suggested O(1) solution would result in better code. Nov 19, 2013 at 15:47
• Point taken, and I agree that the O(1) solution is not necessarily more readable; probably not. I do feel that this solution is more in the spirit of project Euler :) Nov 20, 2013 at 11:10

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

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)