# 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

**, the first**

*2***terms will be:**

*10**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.

## 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

**lines, each containing an integer,**

*T*

*N.***Constraints: 10 ≤ N ≤ 4 **×

**and**

*10¹⁶*

*1 ≤ T ≤ 10⁵*# 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 **×

**Indeed, it is the upper bound of N and it’s huge, but hey, did you know that the**

*10¹⁶.***Fibonacci number is**

*82nd***(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.**

*Fib(82)=61 305 790 721 611 591*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:

**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)**,

**and**

*Fn-1***are odd**

*Fn-2***is even,**

*, Fn-3***and**

*Fn-4***are odd,**

*Fn-5***is even.**

*Fn-6*If we can express ** Fn** using

**and**

*Fn-3***only, then we will modify the Fibonacci sequence to only generate Even numbers ;)**

*Fn-6*Let’s call our new sequence EvenFibonacci:

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

**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

**in our case), we can use the reverse fibonacci formula to find**

*N***the last index:**

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

So much math! Let’s see the code:

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:

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.

**Preprocessing**

Bonus solution using preprocessing, the idea is to use an algorithm to generate the fibonacci numbers up to ** 4 **×

**you store the even one in an array and you sum from the beginning to you limit:**

*10¹⁶,*`Show your love and support by clicking the clap 👏