Project Euler Problem #2

It’s been a bit of time since my last post, but now it’s back to going through Project Euler.  The second problem works with a favorite problem in computer science:  Fibonacci numbers. 

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.

Now, before we step through the solution code (which, again, is written in Python), we can quickly see that we have another problem well suited for a solution involving generators.

Why do I think that?  Well, any time you see a problem that involved stepping through a sequence of numbers — or of any type of item, for that matter — you can find an elegant solution using a generator.

As a quick aside, let’s have a recap on what a generator is in Python.   According to the Python documentation:

Generators are a simple and powerful tool for creating iterators. They are written like regular functions but use the yield statement whenever they want to return data.

When we loop through a series of numbers, we are using an iterator idiom, even if the series doesn’t already exist.  (Such that the series is generated as the program executes via the calls to the generator.)

Now, with that short review out of the way, on to the solution to Project Euler’s problem #2.

def fib( ):
    x,y = 0,1
    while True:
        yield x
        x,y = y, x+y

def even( seq ):
    for number in seq:
        if not number % 2:
            yield number

def under( seq, the_max ):
    for number in seq:
        if number > the_max:
            break
        yield number

print sum( even( under( fib( ), 4000000 ) ) )

For this solution, I’m using 3 generators and I’ll walk through their purpose as you go through the call order.

The first generator function we call is even.  This function loops through the numbers produced by seq, only yielding when the number is an even number.

The generator supplied to even is under.  This function will continue to loop through the items provides by the sequence seq until we run into a number larger than the maximum value supplied — which, in our case, is 4,000,000.

Last, the sequence used by under is generated by the generator function  fib.  This is the heart of this program as it actually generates the series of Fibonacci numbers.  It will continue to generate the next number in the series each time it is called until such time that the number is just too big for Python to be able to handle.

Oh, and the answer is 4,613,732.