Project Euler problem 2

Question

This is a question about Project Euler number 2, a relatively easy one. The question is:

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.

My code is pretty simple; I'm interested in other ways of doing it (lamdba expressions for instance).

namespace ProjectEuler
{
    public class Fibonacci
    {
        // find even number fibonacci terms < 4 mil.
        public void FibonacciSequence(int limit)
        {
            var sw = Stopwatch.StartNew();
            int a = 0;
            int b = 1;
            int total = 0;
            int evenTerms = 0;

            while (total < limit)
            {
                total = a + b;
                a = b;
                b = total;
                if (total % 2 == 0)
                {
                    evenTerms += total;
                }                
            }
            sw.Stop();
            Console.WriteLine(evenTerms);
            Console.WriteLine(sw.ElapsedMilliseconds);
        }
    }
}

Answer 1

This is the solution I came up with using the Fibonacci succession closed form:

that uses the golden radio:

First we can see that for any even Fibonacci number the sum of all the previous even and odd Fibonacci is equal.

Each even Fibonacci number is preceded by 2 odd Fibonacci numbers.

o o e o o e

1 1 2 3 5 8....

This means that we can transform each of the even Fibonacci in the sum of the 2 previous odd Fibonacci .

So n being any even Fibonacci and f(n) the sum of all even Fibonacci up to n we have:

Also the sum of all Fibonacci numbers up to fib(x) is equal to fib(x+2)-1.

So given any number f we find x by calculating the closest Fibonacci number fib(x) that is even and less than or equal to f. We then can finally compute fib(x+2)-1.

The code (this is C++ but it can easily be translated to C#):

long fib ( int i, double golden )
{
    return pow ( golden, i ) / sqrt ( 5 ) + 0.5 ;
}


long findSumEvenFibUpto ( int number )
{
    const double golden = ( 1 + sqrt ( 5 ) ) / 2 ;
    long nearest = round ( log ( sqrt ( 5 ) * number ) / log ( golden ) );

    int fibo = 0 ;
    while ( ( fibo = fib( nearest -- , golden ) ) % 2 || fibo > number ) ;

    return ( fib ( nearest + 3 , golden ) - 1 ) / 2 ;
}

Answer 2

There's plenty of ways to do this, I'll just show how I did it.
The first step is to notice that each 3rd Fibonacci number is even. With a little rewriting we can express F(n) in terms of F(n-3) and F(n-6):

F(n)
= F(n-1)                   + F(n-2)
= F(n-2)          + F(n-3) + F(n-3) + F(n-4)
= F(n-3) + F(n-4) + F(n-3) + F(n-3) + F(n-5) + F(n-6)
= 3 * F(n-3) + (F(n-4) + F(n-5)) + F(n-6)
= 4 * F(n-3) + F(n-6)

We can then write a simple method to generate only the even numbers:

IEnumerable<int> EvenFibs() {
    for (int a = 2, b = 0; ;) {
        yield return a += 4 * b;
        yield return b += 4 * a;
    }
}

And then sum them up:

int SolveProblem2() {
    const int Limit = 4000000;
    return EvenFibs().TakeWhile(i => i < Limit).Sum();
}

Answer 3

Hmm, you can probably make it more effective by using the following principle. odd plus odd equals even, even plus odd equals odd, even plus even equals even

So in your own code, you're checking if each total == 0. This waste of execution time can be saved if you utilize the above principle in only doing the condition check when you need to. Similar to what @Dennis_E was saying.