Project Euler: solution to problem 002

Jorge Martínez Garrido

March 15, 2023

Problem 2

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.

Mathematical background

The Fibonaci sequence is defined as:

$$ \phi_{n} = \phi_{n-1} + \phi_{n-2} $$

where $\phi_{0} = 0$ and $\phi_{1} = 1$.

A number is even if the remainder of its Euclidean division by two is zero.

Therefore, we only need to sum the even terms of the Fibonacci sequence whose values do not exceed four million.

Implementing the Fibonacci sequence

There are two ways to implement the Fibonacci sequence: using recursive functions or using a loop. The recursive approach is very readable while not performant. The loop approach may be less readable but avoids computing various times the same terms of the series.

Trying to generate a Fibonacci function is not the best from the performance point of view, not matter if it uses a loop or recursion. The issue is that we need to check for an UPPER_BOUND, in this case $4000000$. However, we have no idea for which $n$ this bound is achieved. Hence, it is better to keep computing sequence values.

Solution

/**
 * This program solves problem 001 from Project Euler. The statement is as
 * follows:
 *
 * 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.
 *
 */

#include <stdio.h>
#include <stdlib.h>

#define UPPER_BOUND 4000000


int main(int argc, char *argv[])
{
    unsigned long int even_fib_values_sum = 0;

    unsigned long int f_n1 = 0;
    unsigned long int f_n2 = 1;
    unsigned long int f_ith = f_n1 + f_n2;

    while (f_ith < UPPER_BOUND) {
        f_n1 = f_n2;
        f_n2 = f_ith;
        f_ith = f_n1 + f_n2;

        if (f_ith % 2 == 0) {
            even_fib_values_sum += f_ith;
        }
    }
    printf("Answer: %li\n", even_fib_values_sum);

    return EXIT_SUCCESS;
}

/**
 * This program solves problem 001 from Project Euler. The statement is as
 * follows:
 *
 * 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.
 *
 */


const UPPER_BOUND: u32 = 4_000_000;


fn main() {

    let mut even_fib_values_sum: u32 = 0;

    let mut f_n1: u32 = 0;
    let mut f_n2: u32 = 1;
    let mut f_ith: u32 = f_n1 + f_n2;

    while f_ith < UPPER_BOUND {
        f_n1 = f_n2;
        f_n2 = f_ith;
        f_ith = f_n1 + f_n2;

        if f_ith % 2 == 0 {
            even_fib_values_sum = even_fib_values_sum + f_ith;
        }
    }

    println!("Answer: {even_fib_values_sum}");
}

"""
This program solves problem 001 from Project Euler. The statement is as follows:

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.
"""

UPPER_BOUND = 4_000_000


def main():

    even_fib_values_sum = 0

    f_n1 = 0
    f_n2 = 1
    f_ith = f_n1 + f_n2

    while f_ith < UPPER_BOUND:
        f_n1 = f_n2
        f_n2 = f_ith
        f_ith = f_n1 + f_n2

        if f_ith % 2 == 0:
            even_fib_values_sum += f_ith

    print(f"Answer: {even_fib_values_sum}")


if __name__ == "__main__":
    main()

Output

Answer: 4613732