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

The Fibonacci sequence is formally defined by the recurrence relation:

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:

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.

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

HackerRank version

Extended to solve all test cases for Project Euler Problem 2

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

Python Source Code

 Use this link to download the Project Euler Problem 2: Even Fibonacci numbers Python source.

 Run Project Euler Problem 2 using Python on repl.it

Last Word

• See Project Euler Problem 104 for more uses of generalized Fibonacci sequences.
• Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000045: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.