Problem 2 gives us the opportunity to play around with 2 nifty features of Python, generators and itertools.

Project Euler asks us to find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

The Fibonacci sequence runs from 0, 1, 1, 2, 3, 5, 8,.. to infinity. Note that the example at Project Euler starts of with 1, 2, 3, ..., but because we're only interested in the even numbers this doesn't really concern us.

A python generator is a perfect mechanism to 'yield' a possibly infinite stream of values.

def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

The 'problem' here is, that you can't use my beloved list comprehensions to iterate through an infinite generator. That's where itertools comes in.

Itertools contains a function called takewhile(predicate, iterable), which you can wrap around a generator and have it yield it's values while predicate remains True. Make the predicate a simple lambda function and you have a nice one-liner to solve this problem.

from itertools import takewhile
sum([i for i in takewhile(lambda x: x<4000000, fibonacci()) if i%2==0])

update: : As per Damjan's advice (thanks!), it's more efficient to write the list comprehension as an implicit generator comprehension like this:

sum(i for i in takewhile(lambda x: x<4000000, fibonacci()) if i%2==0)
blog comments powered by Disqus