Euler Problem 2 — Even Fibonacci Numbers

20 November, 2023 Python Mathematics

Project Euler hosts interesting mathematical/programming challenges. Quoting the site itself:

The first one-hundred or so problems are generally considered to be easier than the problems which follow.

In this post, I am presenting my solution to the first problem. I do not have the intention to spoil the problem for anyone. However, the solutions for the first 100 problems can be posted

as long as any discussion clearly aims to instruct methods, not just provide answers, and does not directly threaten to undermine the enjoyment of solving later problems.

The problem can be found here. For convenience, I quoted verbatim here:

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, \ldots$$ By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Creating the test cases

I start by manually creating the test cases; by N I mean the upper limit to consider for summing the Fibonacci number. The problem is asking for $N\leq 4 000 000$.

For N equals to 5, the expected result is 1.
For N equals to 11, the expected result is 10.
For N equals to 35, the expected result is 44.
For N equals to 145, the expected result is 188.

In term of Python code, the tests in file test_euler2.py are the following:

import pytest
from euler import even_fibonacci_number


def test_0():
    assert even_fibonacci_number(5) == 2

def test_1():
    assert even_fibonacci_number(11) == 10

def test_2():
    assert even_fibonacci_number(35) == 44

def test_3():
    assert even_fibonacci_number(145) == 188

The reasoning for getting the solution

In this case, I just use a brute force approach; rather than using recursion, I keep track with two auxiliary variables that store the values of the last two Fibonacci numbers ($n_0$ and $n_1$).

The even Fibonacci numbers in the sequence starting with 1 and 2 occurs every three numbers starting for the second element. In other terms, the even Fibonacci numbers are the those at position $3k+1$), with $k \in \mathbb{K}$. Thus, I create a variable to keep track if the Fibonacci number I am calculating is in the $3k+1$)-th position (variable counter in the code below).

Finally, I retur the sum.

The implementation

The code I wrote is the following:

import math


def even_fibonacci_number(N: int) -> int:
    n_0 = 1
    n_1 = 2
    counter = 0
    total = 0

    while n_0 < N:
        n_new = n_0 + n_1
        n_0 = n_1
        n_1 = n_new
        counter += 1
        if (counter % 3) == 1:
            total += n_0

    return int(total)

I got the answer by calling:

even_fibonacci_number(4_000_000)