Problem 2 - Even Fibonacci Numbers Link to heading

The problem statement asks to find the sum of the even Fibonacci numbers whose value is less than one million.

Fibonacci Series for even numbers Link to heading

I’ll go short with this one. This is really popular and consist of the series

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, \cdots $$

They are generated using a recurrence relation

$$ \begin{equation} F_{n} = F_{n-1} + F_{n-2} \qquad n \ge 2 \end{equation} $$

We can notice the sequence,

$$ \begin{align*} &\text{even}, &&\text{odd}, &&\text{odd}, &&\text{even}, &&\text{odd}, &&\text{odd}, &&\text{even}, &&\cdots \\ &0, &&1, &&2, &&3, &&5, &&8, &&13, &&\cdots \end{align*} $$

(yes, I consider that $0 = 2i$ for $i=0$ is even.)

So the even Fibonacci are the numbers $E_{k} = F_{3k}$ . From the recurrence formula we have

$$ E_{k} = F_{3k} = F_{(3k)-1} + F_{(3k)-2} $$

Lets expand and find a simplified recurrence equation that allows an easier computation,

$$ \begin{alignat*}{2} E_{k} &= F_{3k-1} &&+ F_{3k-2} \\ &= \left(F_{(3k-1)-1} + F_{(3k-1)-2}\right) &&+ \left(F_{(3k-2)-1} + F_{(3k-2)-2}\right) \\ &= \left(F_{3k-2} + F_{3k-3}\right) &&+ \left(F_{3k-3} + F_{3k-4}\right); \qquad \text{since} \quad F_{3k-2} = F_{3k-3} + F_{3k-4} \\ &= \left(\left(F_{3k-3}+F_{3k-4}\right) + F_{3k-3}\right) &&+ \left(F_{3k-3} + F_{3k-4}\right) \\ &= 3F_{3k-3}&&+2F_{3k-4} \end{alignat*} $$

But given that,

$$ \begin{align*} F_{3k-3} &= F_{3k-4} + F_{3k-5} \\ F_{3k-4} &= F_{3k-5} + F_{3k-6} \implies F_{3k-5} = F_{3k-4} - F_{3k-6} \\ \end{align*} $$

we can compute,

$$ \begin{align*} F_{3k-3} &= F_{3k-4} + (F_{3k-4} - F_{3k-6})\\ F_{3k-3} + F_{3k-6} &= 2F_{3k-4} \\ \end{align*} $$

So we finally have,

$$ \begin{align*} E_{k} &= 3F_{3k-3}+2F_{3k-4}\\ E_{k} &= 3F_{3k-3}+(F_{3k-3} + F_{3k-6})\\ &= 4F_{3k-3}+F_{3k-6} \end{align*} $$

So

$$ E_{k} = 4F_{3(k-1)}+F_{3(k-2)} \qquad k \ge 2 $$

Provided $F_{3(k-1)} = E_{k-1}$ and $F_{3(k-2)} = E_{k-2}$ as a consequence of $F_{3j} = E_{j}$ we arrive at

$$ \begin{equation} \boxed{E_{k} = 4E_{k-1}+E_{k-2} \qquad k \ge 2} \end{equation} $$

With this recurrence relationship we can iterate even Fibonacci numbers without having to check them using the modulo $F_{k} \% 2 = 0$.

Generating Function Link to heading

I once had the fortune to read part of Lectures on Generating Functions by Sergei Lando and was amazed of this knowledge that can be used to count, combine, and do some mathematical tricks I though where only dealed with using computers. I’m interested in using generating-functions aiming for a faster computation of each Even number,

$$ G(s) = \sum_{k=0}^{\infty} E_{k}s^{k} = E_{0} + E_{1}s+ E_{2}s^{2} + E_{3}s^{3} + E_{4}s^{4} + \cdots $$

Taking a look at the recurrence relation $(2)$, for $k=2$

$$ E_{2} = 4E_{1} + E_{0} $$

This suggests the following operations with the generating function $G(s)$

$$ \begin{alignat*}{5} 4sG(s) &= 4E_{0}s + 4&&E_{1}s^{2}+ 4&&E_{2}s^{3} + 4&&E_{3}s^{4} + 4&&E_{4}s^{5} + \cdots \\ s^{2}G(s) &= &&E_{0}s^{2} + &&E_{1}s^{3}+ &&E_{2}s^{4} + &&E_{3}s^{5} + E_{4}s^{6} + \cdots \\ \end{alignat*} $$

Noting that $E_{2} = 4E_{1}+E_{0}$ it makes sense to attempt the sum,

$$ 4sG(s) + s^{2}G(s) = 4E_{0}s + \left(4E_{1}+E_{0}\right)s^{2}+ \left(4E_{2}+E_{1}\right)s^{3} + \left(4E_{3}+E_{2}\right)s^{4} + \cdots $$

With some factorization,

$$ \begin{align*} 4sG(s) + s^{2}G(s) &= 4E_{0}s + \left(4E_{1}+E_{0}\right)s^{2}+ \left(4E_{2}+E_{1}\right)s^{3} + \left(4E_{3}+E_{2}\right)s^{4} + \cdots \\ &= 4E_{0}s + \left(4E_{1}+E_{0}\right)s^{2}+ \sum_{k=2}^{\infty} (4E_{k}+E_{k-1})s^{k+1} \\ &= 4E_{0}s + \left(4E_{1}+E_{0}\right)s^{2}+ \sum_{k=3}^{\infty} (4E_{k-1}+E_{k-2})s^{k} \end{align*} $$

Now, following the recurrence relation we can perform the addition $-G(s)$

$$ \begin{align*} 4sG(s) + s^{2}G(s) - G(s) &= 4E_{0}s + (4E_{1}+E_{0})s^{2} + \sum_{k=3}^{\infty} (4E_{k-1}+E_{k-2})s^{k} - \sum_{j=0}^{\infty} E_{j}s^{j} \\\\ &= 4E_{0}s + (4E_{1}+E_{0})s^{2} - E_{0} - E_{1}s - E_{2}s^{2} + \sum_{k=3}^{\infty} (4E_{k-1}+E_{k-2})s^{k} - \sum_{j=3}^{\infty} E_{j}s^{j} \\\\ &= (4E_{0}- E_{1})s + (4E_{1}+E_{0}-E_{2})s^{2} - E_{0} + \sum_{k=3}^{\infty} (4E_{k-1}+E_{k-2} - E_{k})s^{k} \\\\ &= (4E_{0}- E_{1})s + (4E_{1}+E_{0}-E_{2})s^{2} - E_{0} + \sum_{k=3}^{\infty} \left(\underbrace{4E_{k-1} + E_{k-2} - E_{k}}_{=0}\right)s^{k} \\\\ &= (4\overset{0}{E_{0}} - \overset{2}{E_{1}})s + (4\overset{2}{E_{1}} + \overset{0}{E_{0}} - \overset{8}{E_{2}})s^{2} - \overset{0}{E_{0}} \\\\ &= 2s + (4\overset{2}{E_{1}} + \overset{0}{E_{0}} - \overset{8}{E_{2}})s^{2} \\\\ &= 2s \end{align*} $$

So we arrive at the result

$$ \begin{align*} 4sG(s) + s^{2}G(s) - G(s) &= 2s \\ \left(4s + s^{2} - 1\right)G(s) &= 2s \\ G(s) &= \frac{2s}{4s + s^{2} - 1} \end{align*} $$

The generating function results to be

$$ \boxed{G(s) = \frac{2s}{4s + s^{2} - 1}} $$

To find a closed form for the generating function’s coefficients $E_{l}$

$$ G(s) = \frac{2s}{4s + s^{2} - 1} = \sum_{l=0}^{\infty}E_{l}s^{l} $$

Using the quadratic formula

$$ \begin{align*} s &= \frac{-(4) \, \pm \sqrt{(4)^2 - 4(1)(-1)}}{2(1)} \\ &= \frac{-4 \, \pm \sqrt{16 + 4}}{2} \\ &= \frac{-4 \, \pm \sqrt{20}}{2} = \frac{-4 \, \pm \sqrt{4\times5}}{2} \\ &= -2 \, \pm \sqrt{5} \end{align*} $$

So the roots are $s_{1}= -2 + \sqrt{5}$ and $s_{2}= -2 - \sqrt{5}$ and the polynomial can be solved by partial fractions

$$ \frac{2s}{(s-s_{1})(s-s_{2})} = \frac{A}{(s-s_{1})} + \frac{B}{(s-s_{2})} $$

Solving for $A$ and $B$

$$ \left\{ \begin{alignat*}{4} \frac{2s}{s-s_{2}} &= &&A &&+ \frac{(s-s_{1})}{(s-s_{2})}&&B \\ \frac{2s}{s-s_{1}} &= \frac{(s-s_{2})}{(s-s_{1})}&&A &&+ &&B \end{alignat*} \right. $$

Setting the proper values for $s=s_{1}, s_{2}$,

$$ \left\{ \begin{alignat*}{2} \frac{2s_{1}}{s_{1}-s_{2}} &= A \\ \frac{2s_{2}}{s_{2}-s_{1}} &= B \end{alignat*} \right. $$

Formula for the coefficients Link to heading

$$ G(s) = \frac{2s}{4s + s^{2} - 1} = \frac{2s_{1}}{(s_{1}-s_{2})(s-s_{1})} + \frac{2s_{2}}{(s_{2}-s_{1})(s-s_{2})} $$

Recalling the Geometric series

$$ \sum_{j=0}^{\infty}s^{j} = \frac{1}{1-s} $$$$ \begin{align*} G(s) &= \frac{2s_{1}}{(s_{1}-s_{2})(s-s_{1})} + \frac{2s_{2}}{(s_{2}-s_{1})(s-s_{2})} \\ &= \frac{2s_{1}}{(s_{2}-s_{1})(s_{1}-s)} + \frac{2s_{2}}{(s_{1}-s_{2})(s_{2}-s)} \\ &= \frac{2}{(s_{2}-s_{1})(1-\frac{s}{s_{1}})} + \frac{2}{(s_{1}-s_{2})(1-\frac{s}{s_{2}})} \\ &= \sum_{j=0}^{\infty}\frac{2}{(s_{2}-s_{1})s_{1}^{j}} s^{j} + \sum_{m=0}^{\infty} \frac{2}{(s_{1}-s_{2})s_{2}^{m}} s^{m} \\ &= \sum_{m=0}^{\infty} \left[\frac{2}{(s_{2}-s_{1})s_{1}^{m}} + \frac{2}{(s_{1}-s_{2})s_{2}^{m}}\right] s^{m} = \sum_{m=0}^{\infty} E_{m} s^{m} \end{align*} $$

So we can compute

$$ E_{m} = \frac{2}{(s_{2}-s_{1})s_{1}^{m}} + \frac{2}{(s_{1}-s_{2})s_{2}^{m}} $$

replacing the values, $s_{1}= -2 + \sqrt{5}$ and $s_{2}= -2 - \sqrt{5}$ in $s_{2}-s_{1} = (-2 - \sqrt{5}) - (-2 + \sqrt{5}) = - 2\sqrt{5} = - (s_{1}-s_{2})$, and factoring out

$$ \boxed{E_{m} = \frac{1}{\sqrt{5} \, \left(-2 - \sqrt{5}\right)^{m}} - \frac{1}{\sqrt{5} \, \left(-2 + \sqrt{5}\right)^{m}}} $$

Coding both approaches Link to heading

My main approach is to follow the generator iterator pattern as we don’t know how much we do need to iterate. The iterator protocol allows virtually infinite iteration

Regular series Link to heading

Knowing the recurrence relation, my approach to the Fibonacci series involves keeping a small history of the most recent numbers, since I’m going to need some values of the series, but don’t want to store all the generated numbers to reduce the memory fingerprint, I’ll keep a list of the most recent Fibonacci numbers created at self.f also, the size of this buffer will be set to 6 due to the recurrence relation that we saw for the even series that needs the last 6 values.

class Fibonacci:
    def __init__(self):
        self.k = -1
        self.init_f = [0,1,1]
        self.f = [i for i in self.init_f]
        self.buffer = 6

    def __iter__(self):
        return self

    def __next__(self):
        self.k+=1
        if self.k <= 2:
            return self.f[self.k]
        f_n = self.f[-1] + self.f[-2]
        if len(self.f) < self.buffer:
            self.f.append(f_n)
        else:
            self.f = self.f[1:] + [f_n]
        return self.f[-1]

    def get(self, k):
        if k > self.k:
            ret = 0
            while self.k < k:
                ret = next(self)
            return ret
        else:
            self.__init__()
            return self.get(k)

We can create a class that follows the same pattern to evaluate the Even numbers.

class EvenFibonacci:
    def __init__(self):
        self.k = 0
        self.f = Fibonacci()
        self.e = [0, 2]

    def __iter__(self):
        return self

    def get(self, k):
        if k >= 2:
            return 4*self.f.get(3*(k-1)) + self.f.get(3*(k-2))
        else:
            return self.e[k]

    def __next__(self):
        res = self.get(self.k)
        self.k+=1
        return res

Generating Function Link to heading

I want to show the contrast between using the regular recurrence relation vs the most tailored solution through the generating function. To that end, we follow the same protocol and create the corresponding class

import math

class EvenFibonacciGeneratingFunction:
    def __init__(self):
        self.k = 0

    def __iter__(self):
        return self

    def get(self, k=0):
        """
        Computes the value of E_m for a given integer m using floating-point math.

        Formula:
          E_m = 1 / (sqrt(5) * (-2 + sqrt(5))^m) - 1 / (sqrt(5) * (-2 - sqrt(5))^m)
        """
        sqrt_5 = math.sqrt(5)

        term1 = 1 / (sqrt_5 * ((-2 - sqrt_5) ** k))
        term2 = 1 / (sqrt_5 * ((-2 + sqrt_5) ** k))

        return math.ceil(term2 - term1)

    def __next__(self):
        res = self.get(self.k)
        self.k+=1
        return res

Comparing results Link to heading

In order to run the experiments, I isolated each call, computed 10000 experiments and stored its execution times

import time
import pandas as pd

experiments = 10000

def even_fibonacci(upper_bound = 4000000):
    start = time.time()
    total_sum = 0

    e = EvenFibonacci()
    while True:
        even = next(e)
        if even >= upper_bound:
            break
        total_sum += even
    end = time.time()

    return end - start

def even_fibonacci_genfunc(upper_bound = 4000000):
    start = time.time()
    total_sum = 0

    e = EvenFibonacciGeneratingFunction()
    while True:
        even = next(e)
        if even >= upper_bound:
            break
        total_sum += even
    end = time.time()

    return end - start

data = [
    {"Time": even_fibonacci(), "GenFunc": even_fibonacci_genfunc()}
    for _ in range(experiments)
]

df = pd.DataFrame(data)

The execution statistics tell us a story,

--- Execution Time Statistics ---
               Time       GenFunc
count  10000.000000  1.000000e+04
mean       0.000053  3.930449e-06
std        0.000004  4.054573e-07
min        0.000049  2.622604e-06
25%        0.000050  3.814697e-06
50%        0.000053  4.053116e-06
75%        0.000054  4.053116e-06
max        0.000354  1.192093e-05

An histogram of the execution of the series shows that in general the Generating Function approach is faster.

(df["GenFunc"].mean()/df["Time"].mean())*100
# prints
# np.float64(7.479602424796772)

So the generating function, on average, was 92% faster than the iterative series. Again, algorithms and the approaches we follow impact performance of our systems