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.

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.

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 

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