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

Problem

Solution

Links