Project Euler #2 in Python

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.

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

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))

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