Solving Project Euler: Problem 2

Problem 2: Even Fibonacci Numbers

HackerRank link: https://www.hackerrank.com/contests/projecteuler/challenges/euler002/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 $N$, find the sum of the even-valued terms.

Solution

Brute Force Approach

The solution for this is fairly straight forward.

• Generate fibonacci numbers.
• While generating the fibonacci numbers for every even fibonacci number we encounter we store it in a variable and we add the next even number we encounter to that variable.
• We stop generating the fibonacci numbers when our present number generated exceeds $N$

The code for it is as follows:

n = int(input().strip())
first = 0
second = 1
third = 1
evenSum = 0
while True:
    first, second = second, third
    third = first + second
    if third > n:
        break
    if (third % 2 == 0):
        res+=third
print(evenSum)

While this works, there’s a more clever way to approach this problem mathematically by optimizing our Brute Force method.

Optimized Brute Force Approach

What we’re tasked with is to find the sum of even valued terms. Let’s look at the Fibonacci sequence again starting from 1 and 1:

\[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\]

If we carefully observe the sequence we can see that every third term in the fibonacci sequence is even. So if we devise a way to calculate every third term in the sequence then we can optimize our brute force to reduce the number of steps required to calculate the sum.

To do this we have to find a way to express our fibonacci sequence $F_n$ in terms of $F_{n-3}$ and $F_{n-6}$, this way we’re dealing with only even numbers.

We start with the general equation of fibonacci series:

\[F_n = F_{n-1} + F_{n-2}\]

and then we expand on from that as follows

\[\begin{align} F_n &= F_{n-1} + F_{n-2}\\ &= F_{n-2} + F_{n-3} + F_{n-3} + F_{n-4} & (F_{n-1} = F_{n-2} + F_{n-3})\\ &= F_{n-3} + F_{n-4} + F_{n-3} + F_{n-3} + F_{n-4}\\ &= 3F_{n-3} + 2F_{n-4}\\ &= 3F_{n-3} + F_{n-4} + F_{n-5} + F_{n-6}\\ &= 3F_{n-3} + F_{n-3} + F_{n-6} & (F_{n-3} = F_{n-4} + F_{n-5})\\ &= 4F_{n-3} + F_{n-6} \end{align}\]

We finally arrive at the equation

\[F_{n} = 4F_{n-3} + F_{n-6}\]

We can now code it out!

n = int(input().strip())
first_term = 2
second_term = 0
f_n = 2
evenSum = 0
while evenSum < n:
    evenSum += f_n
    f_n = 4*first_term + second_term
    second_term, first_term = first_term, f_n 
print(evenSum)

There are a few things to note here:

• We are starting the calculation from the 6th term in the fibonacci sequence, therefore the variable initialization is a bit different.
• The first_term variable corresponds to the first term in the equation we derived, therefore when calculating $F_6$, the first term will be $F_{6-3} = F_3$ and $F_3 = 2$
• The second_term variable corresponds to the second term in the equation we derived, therefore when calculating $F_6$, the second term will be $F_{6-6} = F_0$ and $F_0 = 0$
• Since we’re calculating only the even numbers in the sequence and summing it up, unlike the first brute force method we don’t have to check whether the sum is even because by definition it will always be even.

Other than the points listed above, this code is straightforward and simple. This is still brute forcing but we’ve optimized it quite a bit.