Project Euler and infinite sequences in C#

The second problem at Project Euler proposes:

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.

One way of solving this problem is by defining an endless sequence in C#. Something along these lines:

    IEnumerable<int> FibonacciSequence()

    {

        int n1 = 0;

        int n2 = 1;

 

        while (true)

        {

            int n3 = n1 + n2;

            yield return n3;

            n1 = n2;

            n2 = n3;

        }

    }

The FibonacciSequence() function returns the next value in the sequence everytime its execution hits the yield statement, and conveniently enough, n3 gets the values 1, 2, 3, 5, 8, ... in each next round of the loop. It's notable that the loop never finishes by itself, this responsability actually belongs to the code invoking FibonacciSequence(). So in fact we are seeing a way of representing an infinite set (all Fibonacci numbers) in C#. In our case we need all elements no bigger than 4'000.000, so we can write something like this:

FibonacciSequence().TakeWhile(n => n <= 4000000).Where(n => n % 2 == 0).Sum()

The TakeWhile() method stops asking for more terms as soon as an item bigger than four millions is produced, afterwards the Where() method leaves us with a sequence containing only the even terms, and these terms are finally added up by Sum().

No Comments