Project Euler — Problem 2

Even Fibonacci numbers

Argp / Docs / Project Euler / Problem 2

Problem

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

The problem seems simple enough, all we have to do is find a way to generate Fibonacci numbers and test whether the number is even. If so, add it to the total sum. The $$n^{th}$$ Fibonacci number is the sum of $$(n - 1)^{th}$$ Fibonacci number and $$(n - 2)^{th}$$ Fibonacci number which gives us a recursive definition. The classic recursive method to calculate Fibonacci numbers comes in mind.

def fib(n):
if n is 0 or n is 1:
return n
else:
return fib(n - 1) + fib(n - 2)

Even though the function defined above is straightforward, it is possibly the worst way to generate Fibonacci numbers because it is a tree-recursive algorithm with an exponential order of growth.

                                         fib (5)
+
|
+---------------------------------------+
|                                       |
v                                       v
fib (4)                                 fib (3)
+                                       +
|                                       |
+-------------------+                   +-------------------+
|                   |                   |                   |
v                   v                   v                   v
fib (3)             fib (2)             fib (2)             fib (1)
+                   +                   +                   +
|                   |                   |                   |
+-----------+       +-----------+       +-----------+             v
|           |       |           |       |           |             1
v           v       v           v       v           v
fib (2)     fib (1) fib (1)     fib (0) fib (1)     fib (0)
+           +       +           +       +           +
|           |       |           |       |           |
+---------+      v       v           v       v           v
|         |      1       1           0       1           0
v         v
fib (1)   fib (0)
+         +
|         |
v         v
1         0

Notice how much redundant calculation is being done in this algorithm and on increasing n by one, a whole another tree gets added. This is an example of a bad algorithm for this problem. Section 1.2.2 (Wayback) of Structure and Interpretation of Computer Programs book discusses Tree- Recursion in detail.

We can generate Fibonacci numbers using a clever algorithm, described in Exercise 1.19 of Structure and Interpretation of Computer Programs, in a logarithmic number of steps.

def fib_log(n):
a, b, p, q = 1, 0, 0, 1
while n != 0:
if n % 2 == 0:
p, q = ((p ** 2) + (q ** 2)), ((q ** 2) + (2 * p * q))
n = int(n / 2)
else:
a, b = ((b * q) + (a * q) + (a * p)), ((b * p) + (a * q))
n -= 1
return b

But this is also inefficient because we still have to go through all the Fibonacci numbers less than 4 million and therefore the overall runtime complexity of the program will be $$O(n\cdot\log(n))$$. However this can be improved by instead of generating Fibonacci numbers, we iterate over them. We’ll keep track of the last 2 Fibonacci numbers to generate the next one in constant time. Therefore, this will bring the overall runtime complexity to $$O(n)$$.

def sumEvenFibIter(limit):
if limit is 0 or limit is 1:
return limit

fibSum = 0
a, b = 0, 1

while b < limit:
if b % 2 == 0:
fibSum += b
a, b = b, a + b

return fibSum

This is the best possible runtime complexity you’ll get for this problem but, we can optimize it a little bit by observing how Fibonacci numbers grow.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 …

If you observe, after 2, every third number is even. We can use this to our benefit by just calculating every third term and therefore we’ll have to perform $$n/3$$ steps. The ratio between two numbers of Fibonacci sequence is approximately equal to Golden Ratio ($$\varphi$$). Hence, the ratio between the even numbers is approximately ($$\varphi^{3}$$). The complexity of resulting algorithm is still of the order of $$n$$, i.e., linear but it is 3 times faster in reality than the previous algorithm.

def sumEvenFibIterEven(limit):
if limit is 0 or limit is 1:
return limit

phi_3 = (((1 + (5 ** (1 / 2))) / 2) ** 3)
a = 2
fibSum = 0

while a < limit:
fibSum += a
a = round(a * phi_3)

return fibSum