Detailed mathematical approach

Problem Summary

Project Euler Problem 2 asks for the sum of the even-valued Fibonacci terms that do not exceed four million. The implementations generalize that statement to an arbitrary limit \(N\), but the underlying stream is the same one used in the problem: \(1,2,3,5,8,13,\dots\).

So the real task is not to generate all integers up to \(N\), but to understand the special structure of the Fibonacci sequence well enough to identify and accumulate only the relevant terms.

Mathematical Approach

Let the Fibonacci sequence for this problem be

$F_1=1,\qquad F_2=2,\qquad F_{n+2}=F_{n+1}+F_n\quad(n\ge 1).$

We want

$S(N)=\sum_{\substack{n\ge 1\\F_n\le N\\F_n\text{ even}}}F_n.$

The important mathematical objects are the recurrence itself, the parity pattern of the terms, and the invariant that consecutive Fibonacci numbers determine the next state completely.

The Fibonacci stream used by the problem

Because every term is the sum of the previous two, once two consecutive terms are known, the entire future of the sequence is fixed. Starting from \(F_1=1\) and \(F_2=2\), the first values are

$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\dots$

This recurrence immediately gives a useful implementation invariant: if at some moment we hold two consecutive terms \((F_k,F_{k+1})\), then one update step replaces them by \((F_{k+1},F_{k+2})\). That is exactly what the code exploits.

Why the even terms appear every third step

The fastest conceptual simplification comes from looking at the recurrence modulo \(2\). Since parity is all that matters here, reduce each term to \(0\) or \(1\):

$F_1\equiv 1,\qquad F_2\equiv 0\pmod 2.$

Now track consecutive pairs modulo \(2\):

$\bigl(F_n,F_{n+1}\bigr)\equiv (1,0)\to(0,1)\to(1,1)\to(1,0)\pmod 2.$

The pair returns after three steps, so the parity pattern is periodic with period \(3\). Therefore

$F_n\text{ is even}\iff n\equiv 2\pmod 3.$

That identifies the even-valued subsequence exactly:

$E_m=F_{3m-1}\qquad(m\ge 1),$

whose first terms are \(2,8,34,144,\dots\).

A recurrence for the even-valued subsequence

Sampling every third Fibonacci term produces its own linear recurrence. Write

$A=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix},\qquad \begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix}=A^{n-1}\begin{pmatrix}2\\ 1\end{pmatrix}.$

Advancing three Fibonacci steps at a time means multiplying by

$A^3=\begin{pmatrix}3 & 2\\ 2 & 1\end{pmatrix}.$

This matrix has trace \(4\) and determinant \(-1\), so its characteristic polynomial is

$\lambda^2-4\lambda-1=0.$

Any scalar sequence obtained by repeated multiplication with \(A^3\) therefore satisfies

$x_{m+2}=4x_{m+1}+x_m.$

In particular, the even Fibonacci terms obey

$\boxed{E_{m+2}=4E_{m+1}+E_m,\qquad E_1=2,\qquad E_2=8.}$

This recurrence is often used for an even-only solution. The implementations discussed here do not need it, but it explains why the even terms grow so quickly and regularly.

Collapsing the partial sum

There is also a clean identity for the sum of the first \(m\) even Fibonacci terms. Start from the basic recurrence in the rearranged form

$F_{n+2}=2F_n+F_{n-1}.$

Set \(n=3j-1\). Since \(E_j=F_{3j-1}\), this becomes

$F_{3j+1}-F_{3j-2}=2E_j.$

Summing from \(j=1\) to \(m\) makes the middle terms telescope:

$2\sum_{j=1}^{m}E_j=\sum_{j=1}^{m}\left(F_{3j+1}-F_{3j-2}\right)=F_{3m+1}-F_1=F_{3m+1}-1.$

Hence

$\boxed{\sum_{j=1}^{m}E_j=\frac{F_{3m+1}-1}{2}.}$

So once the last even Fibonacci term below the limit is known, the whole sum can be recovered from one later Fibonacci number. The code still uses direct iteration because it is simpler and already fast enough.⁷

Worked Example: \(N=100\)

The Fibonacci terms below \(100\) are

$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89.$

The even ones are \(2,8,34\), so the required sum is

$2+8+34=44.$

In the subsequence notation this is \(E_1+E_2+E_3\). The closed identity gives the same result immediately:

$E_1+E_2+E_3=\frac{F_{10}-1}{2}=\frac{89-1}{2}=44.$

How the Code Works

The C++, Python, and Java implementations keep two consecutive Fibonacci terms and a running total. Before each loop iteration, the stored pair is exactly \((F_k,F_{k+1})\) for some \(k\). The second term is the current candidate because the stream starts at \(1,2\), so the first value that can contribute is already in that position.

Each iteration does three things: it checks whether the current Fibonacci term is still within the limit, it adds that term to the sum if it is even, and it advances the pair to the next consecutive pair. This preserves the invariant \((F_k,F_{k+1})\mapsto(F_{k+1},F_{k+2})\).

The loop stops as soon as the current term exceeds the limit. Since Fibonacci numbers are strictly increasing after the first two positive terms, every eligible even term is visited exactly once and no extra bookkeeping is required. The implementations also include the checkpoint \(N=100\mapsto 44\), matching the worked example above.

Complexity Analysis

Let \(t\) be the largest index with \(F_t\le N\). Because Fibonacci numbers grow exponentially, \(t=\Theta(\log N)\). The implementations perform constant work per generated term, so the running time is

$O(\log N).$

Only a fixed number of integer variables is stored, so the memory usage is

$O(1).$

An implementation based on the even-only recurrence \(E_{m+2}=4E_{m+1}+E_m\) would improve only the constant factor, not the asymptotic order.

Footnotes and References

1. Problem page: Project Euler Problem 2
2. Fibonacci numbers: Wikipedia - Fibonacci number
3. Parity periodicity modulo \(2\): Wikipedia - Pisano period
4. Matrix form of the Fibonacci recurrence: Wikipedia - Fibonacci number, matrix form
5. Linear recurrences: Wikipedia - Linear recurrence with constant coefficients
6. Even Fibonacci numbers: OEIS A001906
7. Advanced note: Binet's formula can be combined with the closed identity above to jump directly to the relevant even Fibonacci index or value, but for Problem 2 that route requires careful numerical precision control to recover exact integers. The direct loop is therefore preferable here, whereas in Project Euler Problem 25 the logarithmic use of Binet's formula is more natural because only the index is needed. See also Wikipedia - Closed-form expression for Fibonacci numbers.