Project Euler 002

Problem statement

Each new term in the Fibonacci sequence is generated by adding the previous two terms. If you start 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.

Overview

So, basically, the problem says that we have to compute a special sequence (i.e., the Fibonacci sequence) until its last term exceeds 4 million, and then calculate the sum of even numbers of that sequence.

A Fibonacci Sequence is a series of numbers in which each Fibonacci number is the sum of the two preceding numbers. The simplest sequence is the series 1, 1, 2, 3, 5, 8, etc.

Approach 1

We will first apply the brute force approach, i.e., we will keep track of the sum of even valued terms while calculating the required series.

Approach 2

Now, let’s try to get rid of the testing for even values. Here is the beginning of the Fibonacci sequence, even numbers are in bold:

1 1 2 3 5 8 13 21 34 …

It is easy to prove that every third Fibonacci number is even. Now, let us improve our program from checking if its even or not to just adding every third number.

Approach 3

There is another beautiful structure hidden beneath this problem:

If we only write the even numbers of the Fibonacci series:

2 8 34 144…

Here, 34 = 48 + 2 144 = 434 + 8

It seems that they obey the following recursive relation:

E(n) = 4*E(n-1) + E(n-2)

This makes the problem a lot clearer, and now we don’t even have to calculate the whole Fibonacci series. We’ll just create a series with the above equation.