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!

• Writing everything in a single line is rarely a good idea. Why not strive for the most expressive, readable version, regardless of the number of lines? – Adam Mar 3 '13 at 15:59
• please note that the sharing projecteuler solutions outside the scope of the website is not appreciated. See projecteuler.net/about (after loggin in) – Andreas Grapentin Mar 4 '13 at 8:52

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

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 : %timeit p2(4000000)
10000 loops, best of 3: 64 us per loop

In : %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 : %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 : %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.

• p2tris seems to be computing something slightly different than p2bis: it's off by 2. – DSM Mar 3 '13 at 20:09
• @DSM Thanks for checking my code! It is solved now. – Jaime Mar 4 '13 at 5:20

Rather than trying to cram everything into one line, I'd try to put things in small discrete units which map closely to the problem requirements.

We need to sum (1) the terms in the Fibonacci sequence (2) whose values don't exceed 4 million (3) which are even.

And so I'd write something like this:

from itertools import takewhile

def gen_fib():
f0, f1 = 0, 1
while True:
yield f0
f0, f1 = f1, f0+f1

limit = 4000000
low_fibs = takewhile(lambda x: x <= limit, gen_fib())
even_total = sum(f for f in low_fibs if f % 2 == 0)
print(even_total)

where gen_fib yields the Fibonacci terms in sequence, low_fibs is an iterable object which yields terms until (and not including) the first term which is > 4000000, and even_total is the sum of the even ones. You could combine the last two into one line, if you wanted, but why?

This has the advantage of never materializing one big list, as the terms are produced and consumed as needed.

• I was doing some timings, and with Python 2.7 sum appeared to be extremely slow compared to reduce or plain summing in a for loop. Maybe I had numpy running in the background, and there was something going on there, but I was very surprised. – Jaime Mar 3 '13 at 19:46
• @Jaime: I can't reproduce that. genexps often show performance hits relative to loops/listcomps, but I don't see a major difference. sum(i for i in xrange(10) if i % 2 == 0) is only ~20% slower than the equivalent for loop version, and the difference becomes negligible in longer cases. – DSM Mar 3 '13 at 20:08

In one line (plus an import):

from math import floor, log, sqrt
(int(round((pow((1+sqrt(5))/2,2+floor(log(4e6*sqrt(5),(1+sqrt(5))/2)))/sqrt(5))))-1)//2
• Congratulations on a successful defactoring of the original code. – Adam Mar 3 '13 at 20:43