Project Euler : Even Fibonacci Numbers

Problem Statement

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.

Generally Fibonacci Sequence is defined as follows:

F(1) =1;
F(2)=1;
F(n) = F(n-1)+F(n-2); for n > 2;

* here F(1) is omitted;

so instead of 1,1,2,3,5,8,....  it is just 1,2,3,5,8,........

Look up the wiki for Fibonacci Sequence http://en.wikipedia.org/wiki/Fibonacci_number

Brute-force Method :

C#

namespace euler
{
    class Program
    {
        private static void Main(string[] args)

        {
            int i = 0;
            int f1 = 1;
            int f2 = 2;
            int f = 0;
            int sum = f2;
            while (f <= 4000000)
            {
                f = f1 + f2;
                f1 = f2;
                f2 = f;
                if (f%2 == 0)
                    sum = sum + f;
            }
            Console.Write(sum);
            Console.ReadLine();
        }
    }
}
     
Define the first two numbers in the sequence i.e. f1 = 1 and f2 = 2 . Initialize the sum to 0.


Calculate the next number  f in the sequence , if it is even add it to the sum.

Move the index one up so that now f1(new) = f2(old) and f2(new) =f to calculate the next number.

One interesting observation is that even Fibonacci numbers occur 3 places apart.

eg : 2,3,5,8     8, 13, 21,34 and so on

it goes  even, odd, odd, even and so on

(Could be proven by Mathematical Induction)



The following should be faster because of the lesser number of loops required

            while (f <= 4000000)
            {
                f = 2*f1+3*f2;
                f1 = f1+2*f2;
                f2 = f;
                f = 2*f1 + 3*f2;
                sum = sum + f2;
            }

Ans : 4613732

Let me know what you think of the Post in the Comments.