Project Euler: Problem 2

Alright, next Project Euler problem:

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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

– Project Euler Problem 2

Solution

I pretty soon decided I wanted to solve these problems in a good way, and also to sort of try to build up a collection of useful tools that I could hopefully use when solving later Euler problems as well. And even if I didn't find any use for them later, at least I would have gotten some practice when making them 😛

So, the first thing I figured I needed, was a source of Fibonacci numbers. So I created an interface for it, and an implementation (in case I wanted to swap out the implementation more easily later).

public interface IFibonacciSequence : IEnumerable<ulong> {}

public class FibonacciSequence : IFibonacciSequence
{
    #region IFibonacciSequence Members
    public IEnumerator<ulong> GetEnumerator()
    {
        var a = 0UL;
        var b = 1UL;
        var c = a + b;

        while (true)
        {
            yield return c;

            c = a + b;
            a = b;
            b = c;
        }
    }


    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    #endregion
}

After having created that class, solving the problem was pretty straight forward with a simple LINQ statement. I simple start taking numbers from the generator, filtering out the ones that are not even, up till I reach the highest number, and then I sum all of those up.

var answer = new FibonacciSequence()
    .Where(x => x%2 == 0)
    .TakeWhile(x => x < 4000000)
    .Aggregate((sum, x) => sum + x);

Voila 🙂 The reason why I don't use the Sum method is that there doesn't seem to be one for ulong, only for long. And I decided that I for the first time would try to use long instead of int since the answer to some of these problems seems to be quite large. And to use ulong here since there aren't really any need for negative numbers...

Anyways, that was my solution to this problem. According to my test results, it takes less than 5 ms to find it, which is fast enough to me.

So, what do you think? How did you do it?