Project Euler #2 in Python

Question

Here is my Python code for Project Euler #2:

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.

How well did I do and what improvements can I make?

sum = 0
fib = []
i = 2
fib.append(0), fib.append(1), fib.append(1)
while fib[i] < 4000000:
 i += 1
 fib.append(fib[i-1] + fib[i-2])
 if (fib[i] % 2 ==0):
 sum += fib[i]
print sum

EDIT: Thanks everyone for answering and commenting. All answers and some comments provide different suggestions which is very helpful.

• user14393: As an aside, this would make a nice math question: you can work out a closed form formula (with 4000000 replaced with a variable) with paper and pencil with the right mathematical techniques.

Answer 1

Your use of an array to store previous entries is convenient, but it requires a lot of memory use for values that will be thrown away and not reused. It's very simple to keep the two most recent values in simple variables, and not have the array at all.

Consider:

sum = 0
current = 1
previous = 1
while True:
 fib = current + previous
 if (fib > 4000000):
 break
 previous = current
 current = fib
 if (fib % 2 == 0):
 sum += fib
print sum

By eliminating the array you save a lot of management time, and space.

The code above contains a break condition inside the infinite loop instead of a loop condition. This is a common practice solution in Python for a do-while loop instead of a while-do loop.

• user14393: Yes, using the break statement is key. In my opinion, it's usually best to write code in the most natural way -- e.g. "stop when you get past 4 million" -- rather than go through contortions to put the stopping condition in the while condition.

Answer 2

It is not hard to see that the sequence follows a 2-odd-1-even pattern. So you can directly get the next even entry by jumping three positions ahead.

Based on these two simple formulas:

f[i] = f[i-1] + f[i-2] = 2*f[i-2] + f[i-3] = 3*f[i-3] + 2*f[i-4]
f[i-1] = f[i-2] + f[i-3] = 2*f[i-3] + f[i-4]

It should be obvious that the following, code, that doesn't need to explicitly check for even entries, also gets the job done:

odd = 1
even = 2
total = 0 # Using sum shadows the built-in function
while even < 4000000:
 total += even
 odd, even = 2*even + odd, 3*even + 2*odd
print total

EDIT As @Hurkyl suggest in the comments, it is even better to use the formula:

f[i] = 4*f[i-3] + f[i-6]

which cuts out all odd terms:

prev = 2
last = 8 # 1, *2*, 3, 5, *8*
total = 2
while last < 4000000:
 total += last
 last, prev = 4*last + prev, last

• user14393: If you're going to do that, you might as well use f[i] = 4 * f[i-3] + f[i-6] to cut out the odd terms entirely.
• Jaime: Nice! Not that hard to arrive at that expression once you know it exists, but not obvious it was even possible either. Have edited.

Answer 3

In my opinion, rather than writing

fib = []
fib.append(0), fib.append(1), fib.append(1)

you should write

fib = [0, 1, 1]

If you feel it's important to write the code so as to start with an empty list and extend it, you could instead use

fib = []
fib += 0, 1, 1

or instead

fib = []
fib.extend((0, 1, 1))

Answer 4

Nice work getting the problem right. Here are a few pointers:

1. Storing the full array of Fibonacci numbers isn't necessary. You are taking the sum "as you go" and not storing every summand in the sum. You would do well to do the same for the Fibonacci sequence itself. Just store the last two values.

2. I think your code could be nicer if it were wrapped into a function. You could use Python's yield keyword to make your function a "generator function", a technique that works well with "state machine"-like approach of storing only the terms necessary to compute the next term instead of storing the full sequence.

3. You used the reserved keyword sum as a variable name. That's bad; try to avoid doing that if at all possible.

I had my own solution to PE #2 lying around and in case it's interesting or useful to you here it is. (It uses yield and is wrapped into a function.)

def sum_fibonacci_modulo_n(start_1=1, start_2=2, n=2, max_num=4000000):
 sum_ = 0
 if not start_1 % n: 
 sum_ += start_1
 while start_1 < max_num:
 if not start_2 % n:
 sum_ += start_2
 yield sum_
 start_1, start_2 = start_2, start_1 + start_2