Project Euler Problem 2

Even Fibonacci numbers

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.

Approach:

The first thought I had when I looked at this problem is that a recursive solution may cause a stack overflow. If the depth of recursion for the fibonacci sequence is too great, then we may push too many frames onto the stack. Fortunately, I happen to have memorized Binet's formula for the nth fibonacci number.

$$F_n = \frac{(1 + \sqrt 5)^n - (1 - \sqrt 5)^n}{2^n \sqrt 5}$$

This means that we could use a while loop to iterate through Fibonacci numbers, check if the Fn is in the group of even integers, and simply add that number to a sum. If the Fn exceeds four million, then we would break our loop. Let's give it a try.

In [2]:
#Attempt 1
import math
%time

def binetsFormula(n):
    Fn = (math.pow((1 + math.sqrt(5)), n) - math.pow((1 - math.sqrt(5)), n)) / (math.pow(2, n) * math.sqrt(5));
    return int(Fn)

summation = 0
count = 0
flag = True

while flag:
    count += 1
    Fn = binetsFormula(count)
    if (Fn % 2) == 0:
        if (Fn < 4000000):
            summation += Fn
        else:
            break
print(summation, count)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 5.48 µs
4613732 36

Cool, we have a solution. We definitely would have been fine with a recursive solution, 36 iterations is quite small, but the added overhead of pushing frames onto the stack probably would have held back the execution time anyways, so let's proceed with an iterative solution. There has to be a better way to go about this problem, however. I know we could find the sum of a fibonacci series with an upper bound by using:

$$\sum_{i=1}^n Fn = F_n+2 - F_2$$

But I am at a loss as to how we would know if Fn would be even, or how we would choose our numbers to check, so I am going to look at the problem thread...

Woah! Boy did I learn something new. It turns out that every third number of the fibonacci series is even! Let's tweak the code and see what happens when we take that into account.

In [3]:
#Attempt 2
import math
%time

def binetsFormulaEven(n):
    Fn = (math.pow((1 + math.sqrt(5)), 3 * n) - math.pow((1 - math.sqrt(5)), 3 * n)) / (math.pow(2, 3 * n) * math.sqrt(5));
    return int(Fn)

summation = 0
count = 0
flag = True

while flag:
    count += 1
    Fn = binetsFormulaEven(count)
    if (Fn % 2) == 0:
        if (Fn < 4000000):
            summation += Fn
        else:
            break

print(summation, count)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 3.81 µs
4613732 12

Obviously, the number of iterations is 1/3 the amount it took for our previous attempt. Not a huge improvement, but still cool.