Project Euler #2: Even Fibonacci number

Problem statement (In Short):

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:

Links: Project Euler, HackerRank

I planned to first generate the Fibonacci sequence and then do the summation. Afterward, reiterate the algorithm to make it faster and better.

Generating the Fibonacci numbers:

Fibonacci numbers is a sequence where n^th number is addition of previous 2 numbers.

def rec_fibonacci_number(at: int) -> int:
    if at == 0:
        return 1
    if at == 1:
        return 2
    return rec_fibonacci_number(at - 1) + rec_fibonacci_number(at - 2)

However here we want the sequence, so we have to call the recursive method repeatedly (e.g. [rec_fibonacci_number(at=0), rec_fibonacci_number(at=0), ...]). As an optimization, we can modify the recursive function to populate/cache the Fibonacci series as it goes. Now we have to call this function with the index of the maximum Fibonacci number less than $N$ . But we don't have that index and calculating it would require generating the sequence once in some capacity. So here using an iterative algorithm should be the wisest choice.

Iterative code to generate the Fibonacci series till we reach the upper limit:

def fibonacci_numbers(till: int) -> int:
    if till <= 1:
        return []
    if till == 2:
        return [1]

    seq, nxt = [1], 2
    while nxt < till:
        seq.append(nxt)
        nxt = seq[-1] + seq[-2]

    return seq

#1 Naive solution:

We now have a sequence till $N$ , next we need to calculate the sum of even Fibonacci numbers. We can just iterate and add all even numbers from the sequence.

def naive_sum_of_even_fibonacci_numbers(till: int) -> int:
    sum_of_even_nums = 0
    for num in fibonacci_numbers(till):
        if num % 2 == 0:
            sum_of_even_nums += num
    return sum_of_even_nums

#2 Picky solution:

If we print the Fibonacci sequence we can see a pattern.

We can see that every 3^rd number is an even number. To prove this we first need to know that if we add 2 odd or even numbers, addition will be even and otherwise in the remaining 2 cases addition will be odd. Please refer to Even and Odd (Parity) Properties for more information.

The first and second numbers are odd and even respectively then the third and fourth numbers will be odd with respect to the summation of the previous numbers. The fifth number will be even as the last two numbers are odd. This is a repeating sequence, so from this point on wards odd, odd, even sequence will be followed.

Thus now we can just add every 3^rd number after 2^nd (i.e. 1^st index) number.

def picky_sum_of_even_fibonacci_numbers(till: int) -> int:
    fib_nums = fibonacci_numbers(till)
    return sum(fib_nums[i] for i in range(1, len(fib_nums), 3))

#3 Fast solution:

We know that every third number is an even number in the Fibonacci sequence. The question now is can we update the Fibonacci sequence formula to just calculate the even numbers (or each 3rd number). Upon scribbling the equations myself and looking some reference over the internet I figured out the formula to calculate the next even number of the Fibonacci series (i.e. formula for even Fibonacci series).

Here are the calculations to figure out the formula:

We know that every third number is an even number so with above formula if $f(n)$ is even then $f(n - 3)$ and $f(n - 6)$ will also be even. Let $f(n)$ be the $x^{th}$ even element and mark it as $ef(x)$ . If $f(n)$ is $ef(x)$ , then $f(n - 3)$ is previous even number i.e. $ef(x - 1)$ and $f(n - 6)$ is previous of $ef(x - 1)$ i.e. $ef(x - 1)$ . Therefore new equation for $x^{th}$ even element will become:

Referred from Nth Even Fibonacci Number to explain the equations in easy terms.

Now code to generate a list of even Fibonacci numbers till upper limit will look something like this:

def even_fibonacci_numbers(till: int) -> int:
    if till < 2:
        return [0]

    seq, nxt = [0], 2
    while nxt < till:
        seq.append(nxt)
        nxt = 4 * seq[-1] + seq[-2]

    return seq

Now we just need to do the addition of the sequence. The whole code should look something like this:

def even_fibonacci_numbers(till: int) -> int:
    if till < 2:
        return [0]

    seq, nxt = [0], 2
    while nxt < till:
        seq.append(nxt)
        nxt = 4 * seq[-1] + seq[-2]

    return seq


def fast_sum_of_even_fibonacci_numbers(till: int) -> int:
    return sum(even_fibonacci_numbers(till=till))

Final optimizations:

We have a relatively fast algorithm. However, the HackerRank problem will run this algorithm to create a sequence in each test case. We can minimize this calculation by generating it only once for the maximum $N$ and using it for each test case.

Final HackerRank looks something like this:

def even_fibonacci_numbers(till: int) -> int:
    if till < 2:
        return [0]

    seq, nxt = [0], 2
    while nxt < till:
        seq.append(nxt)
        nxt = 4 * seq[-1] + seq[-2]

    return seq

def sum_of_even_fibonacci_numbers(till: int) -> int:
    summation = 0
    for x in evaluated_even_fibonacci_numbers:
        if x >= till:
            break
        summation += x
    return summation

t = int(input().strip()) # Number of test cases

# Store each test case (i.e. $N$) in a list.
test_cases = []
for a0 in range(t):
    test_cases.append(int(input().strip()))

# Pre-evaluate fibonacci list with maximum $N$
evaluated_even_fibonacci_numbers = even_fibonacci_numbers(max(test_cases))

# Now calculate summation
for n in test_cases:
    print(sum_of_even_fibonacci_numbers(n))

We can make further optimization in this by caching the sum. But that's for some other day.

Thank you for reading.