Project Euler Problem 2 Solution: Even Fibonacci numbers

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:

$$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, …

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 %2 (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

Recall 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 number. 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.

Proof that every third Fibonacci number is even, i.e., show $F_{3} \mid F_{3n}$. We'll prove this using ordinary induction on $n$:

$$\textrm{Base case: }F_{3} \mid F_{3}\emph{ i.e., }2 \mid 2\textrm{ }\checkmark\\ \textrm{Suppose }F_{3k}\textrm{ is even: }2 \mid F_{3k}$$ $$ \begin{split} \textrm{Then }F_{3(k+1)} &= F_{3k+3}\\ &= F_{3k+1} + F_{3k+2}\\ &= F_{3k+1} + (F_{3k} + F_{3k+1})\\ &= 2F_{3k+1} + F_{3k}. \end{split} $$

Thus, being the sum of two even numbers, $F_{3(k+1)}$ is even. ✓
Therefore, $F_{3n}$ is even for all positive integers.

By defining a new generalized Fibonacci sequence for even-valued Fibonacci numbers starting from zero as: 0, 2, 8, 34, 144, 610, … we have the basis for a fast solution. 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\times 10^6$ and $27$ iterations for $4\times 10^{16}$. The first program, shown above, takes about 14 times longer to execute.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 2

HackerRank Project Euler 2 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

for _ in range(int(input())):
    N = int(input())
    x, y, s = 0, 2, 0
    while y < N:
         x, y, s = y, 4*y + x, s+y
    print(s)

Last Word

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.