(16 votes, average: 5.00 out of 5)

## Project Euler 2: Find the sum of the even-valued terms in the Fibonacci sequence

#### Project Euler 2 Problem Description

Project Euler 2: 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.

#### Analysis

The problem is asking to consider all Fibonacci numbers less than or equal to 4 million and sum the even numbered ones.

The sequence is formally defined by the recurrence relation:

$F_1=1, F_2=1, F_n=F_{n-1}+F_{n-2}$

The Fibonacci sequence enumerated is: {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, … } and every third number is even. All the rest are odd.

This is because adding two odd numbers (1+1) sum to an even number, followed by adding 2 sets of even and odd numbers (1+2 and 2+3) which sum to an odd number. This principle propagates through the series ad infinitum. A good explaination on Fibonacci multiples, such as the even ones, is provided in the paper: Fibonacci mod k, by Robert McCann, Univ. of Toronto Bahen Centre.

To solve, we will need a program for this limit of 4×106 and the hackerRank Project Euler 2 version which requires us to test 100,000 problems at once with a more ambitious limit of 4×1016 in less than a second. We can bypass iterating the full sequence and just focus on every third term.

This can be easily achieved by defining a new generalized Fibonacci sequence of even Fibonacci numbers starting from zero as: {0, 2, 8, 34, 144, 610, … }.

$G_0=0, G_1=2, G_n = 4G_{n-1} + G_{n-2}$

This works very well, requiring only 11 iterations for a limit of 4×106 and 27 iterations for 4×1016.

This program and method
solves all test cases for
Project Euler 2 on HackerRank

#### Project Euler 2 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 2 Solution Python 2.7 source.

#### Afterthoughts

Phi is calculated as
$\frac{1+\sqrt5}{2}$

The Fibonacci Series and the Golden Spiral

A Golden spiral is very similar to the Fibonacci spiral but is based on a series of identically proportioned golden rectangles, each having a golden ratio of 1.618 of the length of the long side to that of the short side of the rectangle:

The Fibonacci spiral gets closer and closer to a Golden Spiral as it increases in size because of the ratio of each number in the Fibonacci series to the one before it converges on Phi, 1.618, as the series progresses (e.g., 1, 1, 2, 3, 5, 8 and 13 produce ratios of 1, 2, 1.5, 1.67, 1.6 and 1.625, respectively)

Project Euler 2

Project Euler 2 Solution last updated

## Discussion

### One Response to “Project Euler 2 Solution”

1. #include
#include

int main() {
/* code */
int c, n=4000000,s=0,x=0,y=2;

while (y < n){
x=y,y=4*y+x,s=s+y;
//printf("%d\n", );

}

printf("Sum of even Fibonacci numbers<4000000 is %d\n",s);
return 0;
}

i am using same logic as given above for C language, it gives me wrong answer, any resolution please suggest the soln. i am getting o/p as 24414060, but correct answer is: 4613732

Posted by Viral Prajapati | November 30, 2018, 4:08 AM