Project Euler #2: Even Fibonacci numbers

Problem statement

Project Euler version

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.

Link to ProjectEuler version.

Project Euler+ version (Generic)

By considering the terms in the Fibonacci sequence whose values do not exceed N, find the sum of the even-valued terms.

Input Format: First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Constraints: 10 ≤ N ≤ 4 × 10¹⁶ and 1 ≤ T ≤ 10⁵

Link to Hackerrank version.

Analysis

Before reading through this section, I encourage you to think of a possible solution of your own first ~🎀

Quick reminder of the definition of the Fibonacci sequence:

• Dare to brute force..

Please don’t get scared by the constraint 4 × 10¹⁶. Indeed, it is the upper bound of N and it’s huge, but hey, did you know that the 82nd Fibonacci number is Fib(82)=61 305 790 721 611 591 (you definitely didn’t, why would you remember such a number 🤷🏾‍ ). I’ll save you some time, we are looking at 16 digits starting with a 6, and that’s the external border of our inputs.

It smells the brute force! It is possible to naively calculate all the Fibonacci terms under that constraints, it’s just 81 term after all, and sum the even ones.

Bonus python code, I kept it simple with a basic Fibonacci algorithm:

Naive implementation

• Let’s gets cocky…

Let’s take a look at the first few Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…

We actually get the pattern: odd, odd, even, odd, odd, even, odd, odd, even… (proof of this pattern could be drawn from the addition laws on even and odd numbers.) (1)

If we can get the even numbers only and skip the odd ones, that will make our first algorithm much better, since the odd ones are unnecessary. We will save some time filtering them.

Let’s assume that Fn is even, according to the pattern (1), Fn-1 and Fn-2 are odd, Fn-3 is even, Fn-4 and Fn-5 are odd, Fn-6 is even.

If we can express Fn using Fn-3 and Fn-6 only, then we will modify the Fibonacci sequence to only generate Even numbers ;)

Let’s call our new sequence EvenFibonacci:

If we take the previous python code, we can tweak it as below:

Clever implementation

• I love O(1) solutions

After doing some homework, I came upon a closed format of the fibonacci number also known as Binet’s formula:

Where phi, φ is the golden ratio and psi, ψ is the silver ratio (or more known as golden ratio conjugate):

Following the same logic of considering the third terms only (index as 3i), the sum could be deducted as below:

The third line is expressed using the geometric series formula.

reminder: we are calculating the sum of the even Fibonacci numbers less than N

so given Fn (noted N in our case), we can use the reverse fibonacci formula to find n the last index:

Then we can deduct the index of the last even number 3k:

So much math! Let’s see the code:

Explicit expression of the sum of the even Fibonacci numbers

It looks so cool, right? Sadly our implementation suffers floating precision issues, the following table shows a comparison of results between the exact implementation and our fancy one for different value of N:

precision issue for bigger numbers

Since all platforms map Python floats to IEEE 754 double precision, and apparently that’s not enough for us, we need either a language that support a high floating point precision such as Wolfram Language famously known as Wolfram Mathematica. or a library that implements a more advanced floating point system.

In the following code I used Decimal, a great module that provides support for extended floating point precision, but apparently it’s a slow solution that depends on the performance of the library used.

Explicit expression of the sum of the even Fibonacci numbers using the Python Decimal library

• Preprocessing

Bonus solution using preprocessing, the idea is to use an algorithm to generate the fibonacci numbers up to 4 × 10¹⁶, you store the even one in an array and you sum from the beginning to you limit:

Preprocessing implementation

`Show your love and support by clicking the clap 👏