Project Euler - Shortening Problem 2

You might have read my question on shortening my code to a one-liner for Problem 1. So, I was wondering, is there any more tricks of the trade to shorten my Problem 2 solution:

fib = [0, 1]
final = 1
ra = 0
while final < 4000000:
    fib.append(fib[-1] + fib[-2])
    final = fib[-1]
fib.pop()
for a in fib:
    if a%2 == 0:
        ra += a
print(ra)

Down to one line??

This is the official Problem 2 question: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.
Thanks!

The first few are probably OK, but you really shouldn't be publishing solutions to Project Euler problems online: don't spoil the fun for others!

This said, there are several things you could consider to improve your code. As you will find if you keep doing Project Euler problems, eventually efficiency becomes paramount. So to get the hang of it, you may want to try and write your program as if being asked for a much, much larger threshold. So some of the pointers I will give you would generally be disregarded as micro optimizations, and rightfully so, but that's the name of the game in Project Euler!

Keeping the general structure of your program, here are a few pointers:

• Why start with [0, 1] when they tell you to go with [1, 2]? The performance difference is negligible, but it is also very unnecessary.

• You don't really need several of your intermediate variables.

• You don't need to pop the last value, just ignore it when summing.

• An important thing is that in the Fibonacci sequence even numbers are every third element of the sequence, so you can avoid the divisibility check.

Putting it all together:

import operator

def p2bis(n) :
    fib = [1, 2]
    while fib[-1] < n :
        fib.append(fib[-1] + fib[-2])
    return reduce(operator.add, fib[1:-1:3])

This is some 30% faster than your code, not too much, but the idea of not checking divisibility, but stepping in longer strides over a sequence, is one you want to hold to:

In [4]: %timeit p2(4000000)
10000 loops, best of 3: 64 us per loop

In [5]: %timeit p2bis(4000000)
10000 loops, best of 3: 48.1 us per loop

If you wanted to really streamline things, you could get rid of the list altogether and keep a running sum while building the sequence:

def p2tris(n) :
    a, b, c = 1, 1, 2
    ret = 2
    while c < n :
        a = b + c
        b = c + a
        c = a + b
        ret += c
    return ret - c

This gives a 7x performance boost, not to mention the memory requirements:

In [9]: %timeit p2tris(4000000)
100000 loops, best of 3: 9.21 us per loop

So now you can compute things that were totally unthinkable before:

In [19]: %timeit p2tris(4 * 10**20000)
1 loops, best of 3: 3.49 s per loop

This type of optimization eventually becomes key in solving more advanced problems.

StackExchange Code Review Q#23383, answer score: 3