Project Euler - Shortening Problem 2

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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