Mihir Yerande

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.

The Fibonacci numbers are interesting for many reasons, and much discussion can be had about them.
I've discussed them a bit here: Fibonacci Numbers
However, for the sake of solving this problem, we will avoid that discussion and skip ahead to find a practical solution.

Note that we define the Fibs as follows:

• \(F_0 = 0\)
• \(F_1 = 1\)
• \(F_n = F_{n-1} + F_{n-2}\), where \(n \in \mathbb{N}\) and \(n \geq 2\)

• Lowercase phi: \(\hspace{1em}\displaystyle\phi = \frac{1+\sqrt{5}}{2} \approx 1.618\cdots\)
• Lowercase psi: \(\hspace{1em}\displaystyle\psi = \frac{1-\sqrt{5}}{2} \approx -0.618\cdots\)

At first glance, we could easily write some code to iterate upwards and enumerate the Fibs in sequence.
The following code would accomplish what we need:
The computational complexity, namely the time-complexity here, depends on the number of iterations needed to enumerate until \(M\)
Recall that the sequence turns out to be roughly exponential, where \(F_n \sim \phi^n\).
Thus the number of iterations as well as the time-complexity are of magnitude \(O(log(M))\)

Can we do better? → YES

Let's look closer at the Fibs sequence.
 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Recall that we're only concerned with the even entries of the sequence.
It seems that only every third entry in the sequence is even.
Why?

Consider only the parity (even-ness or odd-ness) of the sequence, as follows:

\( \begin{align*} \hspace{1em}F_0 &= 0 & & \rightarrow\text{ even} \\ \hspace{1em}F_1 &= 1 & & \rightarrow\text{ odd} \\ \hspace{1em}F_2 &= F_0 + F_1 \rightarrow & \text{ even + odd } & \rightarrow\text{ odd} \\ \hspace{1em}F_3 &= F_1 + F_2 \rightarrow & \text{ odd + odd } & \rightarrow\text{ even} \\ \hspace{1em}F_4 &= F_2 + F_3 \rightarrow & \text{ odd + even } & \rightarrow\text{ odd} \\ \hspace{1em}F_5 &= F_3 + F_4 \rightarrow & \text{ even + odd } & \rightarrow\text{ odd} \\ \end{align*} \)

It turns out that the parity of the sequence has a cyclical nature, which explains why every third element, \(F_{3j}\), is even!
We can use this to our advantage to avoid the parity check by simply skipping to every 3^rd Fib, and adding.

The previous code can be modified to the following:
Although we've modified the code to avoid divisibility checks, it is still iterating similarly as before.
The time-complexity thus remains at \(O(log(M))\).

Can we do better !? → YES

Let's look directly at the desired answer, formulated as a summation:

\( \begin{align*} \hspace{1em}S &= \displaystyle\sum_{i \in \mathbb{N}_0} F_i \cdot \mathbb{1}_{\{F_i\text{ is even } \wedge\hspace{0.2em}F_i \leq M\}} & \text{Desired answer} \\ \hspace{1em} &= \displaystyle\sum_{i \in \mathbb{N}_0} F_i \cdot \mathbb{1}_{\{F_i\text{ is even}\}} \cdot \mathbb{1}_{\{F_i \leq M\}} & \text{Split indicator into separate predicates} \\ \hspace{1em} &= \displaystyle\sum_{i \in \mathbb{N}} F_i \cdot \mathbb{1}_{\{F_i\text{ is even}\}} \cdot \mathbb{1}_{\{F_i \leq M\}} & F_0 = 0 \end{align*} \)

where \(\mathbb{1}_{\cdots}\) is an indicator variable taking values 0 or 1, depending on the specified predicate.

Element-wise Parity

We discovered previously that only every third Fib is even, so we can improve our summation:

\( \hspace{1em}S = \displaystyle\sum_{j \in \mathbb{N}} F_{3j} \cdot \mathbb{1}_{\{F_{3j} \leq M\}} \)

Upper Bound

Now we need to determine the upper bound, \(j_{max}\), of the iterator variable, \(j\).
This would be the maximum such \(j\) for which \(F_{3j} \leq M\).
We can determine it as follows:

\( \begin{align*} F_{3j} & \leq M & \text{Desired condition} \\ \frac{\phi^{3j} - \psi^{3j}}{\sqrt{5}} & \leq M & \text{Substitute with closed-form expression} \\ round\left(\frac{\phi^{3j}}{\sqrt{5}}\right) & \leq M & \text{Simplified formula version} \\ \frac{\phi^{3j}}{\sqrt{5}} & \lt M + 0.5 & \text{Accounting for rounding} \\ \phi^{3j} & \lt (M + 0.5) \cdot \sqrt{5} \\ ln(\phi^{3j}) & \lt ln((M + 0.5) \cdot \sqrt{5}) \\ 3j \cdot ln(\phi) & \lt ln(M + 0.5) + \frac{1}{2}ln(5) \\ j & \lt \frac{ln(M + 0.5) + \frac{1}{2}ln(5)}{3 \cdot ln(\phi)} \\ j_{max} & = ceil\left(\frac{ln(M + 0.5) + \frac{1}{2}ln(5)}{3 \cdot ln(\phi)}\right) - 1 & \text{Maximum possible value of }j \end{align*} \)

Given this upper bound, we can simplify our prior summation to the following:

\( \hspace{1em}S = \displaystyle\sum_{j=1}^{j_{max}} F_{3j} \)

Geometric Series

Additionally, as stated before, the Fibs turn out to be roughly equal to a geometric progression.
Perhaps, then, we can convert the summation to a closed-form expression!

Note that rounding many values and then summing is not necessarily the same as summing and the rounding.
For example, \(round(0.5) + round(0.5) = 1 + 1 = 2\), whereas \(round(0.5 + 0.5) = round(1) = 1\).
Hence we start with the unrounded expression:

\( \begin{align*} \hspace{1em}S &= \displaystyle\sum_{j=1}^{j_{max}} F_{3j} & \text{Desired summation} \\ \hspace{1em} &= \displaystyle\sum_{j=1}^{j_{max}} \frac{\phi^{3j} - \psi^{3j}}{\sqrt{5}} & \text{Exact formula} \\ \hspace{1em} &= \displaystyle\sum_{j=1}^{j_{max}} \frac{\phi^{3j}}{\sqrt{5}} - \sum_{j=1}^{j_{max}} \frac{\psi^{3j}}{\sqrt{5}} & \text{Separate into two summations} \\ \hspace{1em} &= \displaystyle\frac{1}{\sqrt{5}}\sum_{j=1}^{j_{max}} \phi^{3j} - \frac{1}{\sqrt{5}}\sum_{j=1}^{j_{max}} \psi^{3j} & \text{Factor out constant} \\ \hspace{1em} &= \displaystyle\frac{1}{\sqrt{5}} \cdot \frac{\phi^3 \cdot (1-(\phi^3)^{j_{max}})}{1-\phi^3} - \frac{1}{\sqrt{5}} \cdot \frac{\psi^3 \cdot (1-(\psi^3)^{j_{max}})}{1-\psi^3} & \text{Closed-form for finite geometric series} \\ \hspace{1em} &= round\left(\displaystyle\frac{1}{\sqrt{5}} \cdot \frac{\phi^3 \cdot (1-(\phi^3)^{j_{max}})}{1-\phi^3}\right) & \text{Subtracted term is negligible} \\ \end{align*} \)

Final Code

We've found a direct formula to calculate the sum!
The code is now as follows:


The time-complexity has been reduced to \(O(1)\) as we only need to compute a fixed number of arithmetic operations.

The answer can be easily computed manually with a calculator, giving the following:

\( \begin{align*} \hspace{1em}M &= 4,000,000 \\\\ \hspace{1em}j_{max} &= ceil\left(\frac{ln(M + 0.5) + \frac{1}{2}ln(5)}{3 \cdot ln(\phi)}\right) - 1 \\ \hspace{1em} &= ceil\left(11.088\cdots\right) - 1 \\ \hspace{1em} &= 11 \\\\ \hspace{1em}S &= round\left(\displaystyle\frac{1}{\sqrt{5}} \cdot \frac{\phi^3 \cdot (1-(\phi^3)^{j_{max}})}{1-\phi^3}\right) \\ \hspace{1em} &= round\left(\displaystyle\frac{1}{\sqrt{5}} \cdot \frac{\phi^3 \cdot (1-(\phi^3)^{11})}{1-\phi^3}\right) \\ \hspace{1em} &= round\left(4,613,731.9\cdots\right) \\ \hspace{1em} &= 4,613,732 \end{align*} \)

The full Python3 code for my solution implementation can be found here: GitHub Solution