// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (17 votes, average: 5.00 out of 5)

Project Euler Solutions

Project Euler 2 Solution

Project Euler 2 Solution

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.


foxtrot20051011The 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.

Project Euler 2
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.
download arrowUse this link to get the Project Euler 2 Solution Python 2.7 source.


Phi is calculated as

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:

Project Euler 2: Golden Spiral

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


2 Responses to “Project Euler 2 Solution”

  1. #include
    using namespace std;
    #define ll long long
    int main()
    ll int t;
    ll n,t1,t2,c,sum=0;

    Posted by Rayhan | July 29, 2020, 3:27 AM
  2. #include

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

    while (y < n){
    //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

Post a comment