Problem 2

This post tackles Problem 2 in the Project Euler series.

We have the Italian mathematician Fibonacci to thank for importing into Europe the Hindu-Arabic numerals that are the bane of every child learning their 1,2,3. If it wasn't for Fibonacci, we'd still be trying to do multiplication and division with Roman numerals. He also had the amazing insights into the mathematics of rabbit breading which led to the famous series that we consider today, the Fibonacci series.

To generate each term in the Fibonacci series, you simply add together the two terms in the series before it. So if the first two terms are 1 and 2, you continue, to get a series like

1,2,3,5,8,13,...

Problem 2 of Project Euler wants us to sum up all the terms in the Fibonacci series that are divisible by 2 and less than or equal to 4 million.

A while loop might spring to mind at this point, but we want to force ourselves to think differently. Lets try thinking in terms of sequences again, as we did last time. The Fibonacci series is an obvious sequence - an infinite one in fact. We need to generate terms in that sequence until they become too big, then filter out any that are odd, finally adding up what we have left.

Since C#2.0 there's been a very neat way of generating sequences: Iterators. An Iterator is just a method that returns an IEnumerable result (or another similar type - follow the link for the details), and contains the special yield keyword. Look at this one:

private static IEnumerable<int> FibonacciTerms(int firstTerm, int secondTerm)
        {
            yield return firstTerm;
            yield return secondTerm;

            int previous = firstTerm;
            int current = secondTerm;
  
            while (true)
            {
                int next = previous + current;
                previous = current;
                current = next;
                yield return current;
            }
        }

This iterator creates the Fibonacci sequence for us. You might look at the while(true) line, and think that we've just coded up an infinite loop. But there's more to it than meets the eye.

Iterators are very lazy creatures. They never do more than they're asked to do. In fact, if all you were to do was to call the FibonacciTerms method, none of the code above would get executed. It's only when you call an Iterator inside a foreach block that it reluctantly starts to do any work. The first time through a foreach loop, the iterator starts at the top of its method, huffing and puffing through each line of code, until it reaches a yield statement. With a sigh of relief, it returns to the foreach loop the value it has calculated so far, and then goes to sleep. For all subsequent iterations of the foreach loop, the iterator picks up from exactly where it left off, right after the previous yield statement, and carries on through the method until it finds another one, and then yields up its result and go back to sleep.

So rather than looping for ever, the FibonacciTerms method will keep going only as long as it is asked to produce more terms. Is a foreach loop the only way to put it to work? Step up the Enumerable class again. It provides the TakeWhile extension method that does the foreach loop for us. It pulls items out of a sequence, pushing them into an output sequence, until a certain condition is met. So we can say

FibonacciTerms(1, 2).TakeWhile(x => (x <= 4000000) )

and that will generate a sequence of all the Fibonacci terms less than 4 million. Again we're giving TakeWhile a lambda expression so it can decide whether the term that it got from FibonacciTerms meets the condition.

It only remains for us to filter out the odd terms, and to sum up everything else:

private static int SumEvenFibonarciTerms()
{
    return FibonacciTerms(1, 2)
            .TakeWhile(x => (x <= 4000000)).Where(x => x % 2 == 0)
            .Sum();
}