Project Euler Problem 2

Jun 4th, 2022

7 min read

Even Fibonacci Numbers

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

Before we dive into three different ways to solve this problem, consider reading more about the Fibonacci sequence.

Note that the problem statement assumes that the first two terms of the sequence are 1 and 2, whereas conventionally $F_0 = 0$ and $F_1 = F_2 = 1$ . The solutions will follow the latter convention, but it doesn't technically matter how you start as only the even-valued terms are of interest.

Brute Force - Naive

First we'll make the solution scalable as a function that accepts any upper limit, and we'll use Long values to prepare for any integer overflow as this limit increases.

Then we'll iterate over all Fibonacci terms (that are not greater than the limit) using $equation (1)$ and add any that are divisible by 2 without a remainder.

\begin{gather*} F_n=F_{n-2}+F_{n-1}\tag{1}\\[.5em] \text{with }F_1=F_2=1\text{ and }F_3=2 \end{gather*}

1fun sumOfEvenFibsNaive(limit: Long): Long {
2    var sum = 0L
3    var fNMinus2 = 1L  // F(2)
4    var fNMinus1 = 2L  // F(3)
5    while (fNMinus1 <= limit) {
6        if (fNMinus1 % 2 == 0L) sum += fNMinus1
7        val fN = fNMinus2 + fNMinus1
8        fNMinus2 = fNMinus1
9        fNMinus1 = fN
10    }
11    return sum
12}

Modulo vs Bitwise AND

Bitwise operators offer many nifty tricks for replacing arithmetic operations that can even boost performance. When considering using the modulo operation with a power of 2, as in the case of checking whether a number is even, the bitwise AND operator (and()) can be substituted as follows:

x\mod 2^n==x\land (2^n-1)

As a reminder, the logical AND ( $\land$ ) takes two booleans and returns true if, and only if, both booleans are true. When applied to types with a binary representation, like Int, the AND operator compares each bit and returns 1 when both bits are 1; otherwise, it returns 0.

1// Bitwise AND
2val ten = Integer.toBinaryString(10)
3val nine = Integer.toBinaryString(9)
4val one = Integer.toBinaryString(1)
5val even = Integer.toBinaryString(10 and 1)
6val odd = Integer.toBinaryString(9 and 1)
7println("$ten AND $one = $even == 10 mod 2 = ${10 % 2}")
8println("$nine AND $one = $odd == 9 mod 2 = ${9 % 2}\n")
9
10// Modulo versus Bitwise AND
11val nums = 1..6
12val modCheck = { num: Int -> num % 2 == 0 }
13val bitCheck = { num: Int -> num and 1 == 0 }
14println(nums.map(modCheck))  
15println(nums.map(bitCheck))

1010 AND 1 = 0 == 10 mod 2 = 0
1001 AND 1 = 1 == 9 mod 2 = 1

[false, true, false, true, false, true]
[false, true, false, true, false, true]

Note that and() can be used with the infix notation like 10 and 1 to improve code readability.

Performing a benchmark test on the lambda functions modCheck() and bitCheck() (to assess the parity of numbers in the range 1..1000 over 10 million iterations after warmups) returned the following results:

FUNCTION	BEST	AVERAGE	WORST
bitCheck	400ns	459ns	1.7e+05ns
modCheck	400ns	553ns	9.80ms

For this problem set we'll keep using the modulo operator in the first solution even if it is slower, but don't forget to consider the possible advantage of using bitwise operators if you're performing a modulo operation frequently and are crunched for time.

Brute Force - Pattern

If we write out the first twenty Fibonacci terms (excluding 0) we'll observe a pattern:

1\;\;1\;\;\bold{2}\;\;3\;\;5\;\;\bold{8}\;\;13\;\;21\;\;\bold{34}\;\;55\;\;89\;\;\bold{144}\;\;233\;\;377\;\;\bold{610}\;\;987\;\;1597\;\;\bold{2584}\;\;4181\;\;6765\dots

Starting with $F_3$ , every third Fibonacci term is an even number. This pattern occurs because the first two terms are odd and the sum of two odd numbers must be an even number ( $1+1=2$ ). Then the sum of an odd and an even number must produce a new odd number ( $1+2=3$ ) and this is repeated to produce another odd number ( $2+3=5$ ), so the cycle can start again by producing an even number from two odds ( $3+5=8$ ).

Given this pattern, the first iterative solution can be altered to remove any need for a parity check by stepping forward to every third term in the sequence.

1fun sumOfEvenFibsPattern(limit: Long): Long {
2    var sum = 0L
3    var prev = 1L  // F(2)
4    var evenFib = 2L  // F(3)
5    while (evenFib <= limit) {
6        sum += evenFib
7        val next = prev + evenFib  // step #1
8        prev = next + evenFib  // step #2
9        evenFib = next + prev  // step #3
10    }
11    return sum
12}

Formula

This pattern can be taken a step further and reduced to a formula that calculates the next even Fibonacci term based on the previous two even terms in the sequence. The aim of the reduction is to convert the right-hand side of the equation to only include terms that are multiples of 3 away from $n$ .

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

$Equation (2)$ is an example of expansion to the previous Fibonacci terms as $F_{n-2}=F_{n-3}+F_{n-4}$ .

$Equation (6)$ is an example of contraction to the next Fibonacci term as $F_{n-5}+F_{n-4}=F_{n-3}$ .

1fun sumOfEvenFibsFormula(limit: Long): Long {
2    if (limit <= 8) return 2L
3    var fNMinus6 = 2L  // F(3)
4    var fNMinus3 = 8L  // F(6)
5    var sum = 10L
6    while (true) {
7        // fN will equal F(9) in the first iteration
8        val fN = fNMinus6 + 4 * fNMinus3
9        if (fN > limit) break
10        sum += fN
11        fNMinus6 = fNMinus3
12        fNMinus3 = fN
13    }
14    return sum
15}

Speed Comparison

We've covered three solutions to Problem 2, which have different approaches to iterating over the Fibonacci terms. Let's compare the average speed when each solution is executed 1000 times for different limits.

LIMIT	BF - NAIVE (ns)	BF - PATTERN (ns)	FORMULA (ns)
4e6	571	458	263
4e12	1715	1008	367
4e16	5309	2948	489

Note that the average execution times shown in the "Brute Force - Naive" column are for the solution version that uses the modulo operator. If the modulo operator is replaced by the bitwise AND operator, the average speeds start to differ as the limit increases with more terms requiring a parity check.

LIMIT	OPERATOR	BEST (ns)	AVERAGE (ns)	WORST (ns)
4e6	Modulo	100	571	1.4e+05
4e6	Bitwise	200	578	6.5e+04
4e12	Modulo	300	1715	5.2e+05
4e12	Bitwise	200	1235	1.3e+05
4e16	Modulo	1800	5309	1.6e+06
4e16	Bitwise	600	1826	5.6e+04

Overall the formula solution performs best of the three but none of them are by any means slow. This exploration has been more of a means to scratch the surface of the Fibonacci sequence in preparation for future Project Euler problems.

Here's the full source code for this problem (and its corresponding test suite).

This solution set is also available in Python and in C++ on my GitHub.

Problem content on the Project Euler site is licensed under a Creative Commons (CC) License: CC BY-NC-SA 4.0. Solutions to only the first hundred problems are encouraged to be distributed publicly.

Thanks for reading!🏝️🐚