Project Euler Problem 2 Solution

Project Euler & HackerRank Problem 2 Solution

Even Fibonacci numbers
by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank

Project Euler Problem 2 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, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Solution

FoxTrot cartoon

The Fibonacci sequence is formally defined by the recurrence relation:

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

and generates the sequence: {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …}.

The purpose of the problem is to sum the even-valued terms of the Fibonacci Sequence, as they are highlighted above, to an upper bound.

A blithe solution

This simple approach solves both Project Euler’s and HackerRank’s problems easily. We generate the Fibonacci sequence and sum the even terms by checking their parity (odd or even) with a mod 2 conditional.

s=0; f0=1; f1=1; L=4000000
while f1<L:
    if f1%2==0: s+= f1
    f0, f1 = f1, f0+f1
print s

A more efficient solution with a generalized Fibonacci sequence

Remember that adding two odd numbers together always sums to an even number just as adding an even and odd number will sum to an odd number. As the Fibonacci sequence begins with two odd numbers and each subsequent Fibonacci number is the sum of the previous two, then the following term will be even. This will yield two odd numbers after every even because an odd plus an even will be odd. This principle propagates through the series ad infinitum.

A good explanation on Fibonacci multiples, such as finding the even ones, is provided in the paper Fibonacci mod k, by Robert McCann, Univ. of Toronto Bahen Centre. And if you're still not convinced, here’s a proof:

Proof that every 3rd Fibonacci number is even.

We solve this problem by defining a new generalized Fibonacci sequence for even-valued Fibonacci numbers starting from zero as: {0, 2, 8, 34, 144, 610, … }. Then, by iterating over this new sequence, we sum the terms until we reach the designated upper bound.

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

This works very well, requiring only 11 iterations for an upper bound of 4×106 and 27 iterations for 4×1016. The first program, shown above, takes about 14 times longer to execute.

HackerRank version

HackerRank requires us to run 10,000 test cases and sum even Fibonacci numbers to an upper bound, N, where 10 ≤ N ≤ 4×1016.

Python Source Code

Last Word