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
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×1016.
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
- 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.