Original problem

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,\dots$$

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

Formal statement

Define

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

Compute

$$S=\sum _{\begin{array}{c}n\ge 1\\ F_n\le 4\times {10}^6\\ 2\mid F_n\end{array}}{F}_n.$$

Hints

Open one at a time

Write down the parity pattern of consecutive Fibonacci numbers.

Every third term is even.

Solution

Best opened after a real attempt

Approach

Parity in the Fibonacci sequence repeats every three terms: odd, even, odd. Therefore every third term is even. If the even-valued terms are written as $E_1,E_2,\dots$, eliminating the two odd terms between them gives

$$E_k=4E_{k-1}+E_{k-2}.$$

Starting from the first even term, this recurrence visits only values that contribute to the sum. It avoids generating and testing the intervening odd Fibonacci numbers while preserving a simple loop.

Code & final result

Password-protected content

Enter the access password. Decryption happens only in this browser.

Access password

The original problem is reproduced from Project Euler Problem 2 under CC BY-NC-SA 4.0.