4
\$\begingroup\$

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);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Quick & Dirty search of questions that may interest you. \$\endgroup\$ – RubberDuck Sep 28 '15 at 20:13
  • \$\begingroup\$ Thanks. The ones on the algorithm devised for solving this are great. \$\endgroup\$ – kafka Sep 28 '15 at 20:21
  • 1
    \$\begingroup\$ If you notice that each 3rd Fibonacci number is even, you can skip the odd numbers altogether. \$\endgroup\$ – Dennis_E Sep 28 '15 at 20:24
  • \$\begingroup\$ In terms of a method performing only one task, I'm thinking that the part which sums 'evenTerms' should be a separate method. \$\endgroup\$ – kafka Sep 30 '15 at 11:36
4
\$\begingroup\$

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 ;
}
\$\endgroup\$
3
\$\begingroup\$

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();
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.