Project Euler 2: Adding Only the Even Fibonacci Numbers

This is the second problem in the Project Euler series. You can solve it by generating Fibonacci numbers one after another and keeping the even ones, but if you first work out where the even terms sit, you get a recurrence that jumps straight from one even term to the next. Tracking parity and reshaping a recurrence are both techniques that come back in later problems.

Spoiler warning: this post contains a full solution and the answer. If you want to try it yourself first, start with the original problem. Posts in this series never carry ads, because the problem text is licensed under CC BY-NC-SA 4.0, which is non-commercial.

Problem

Take the Fibonacci sequence that starts with 1 and 2, where every later term is the sum of the two before it: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … Look only at the terms whose values do not exceed four million (4,000,000), and add up the ones that are even.

The bound is “does not exceed”, so 4,000,000 itself is included. 4,000,000 is not a Fibonacci number, so reading it as “below” gives the same result here, but once the solution becomes a reusable function it should implement the inclusive bound exactly.

Background

The Fibonacci sequence and its numbering. This post follows the problem’s starting values: F₁ = 1, F₂ = 2, and Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 3. So F₃ = 3, F₄ = 5, F₅ = 8, F₆ = 13, F₇ = 21, F₈ = 34. Compared with the familiar 1, 1, 2, 3, … the indices are shifted by one, so formulas taken from elsewhere need their indices adjusted.

The sequence is strictly increasing. F₂ > F₁, and for n ≥ 3, Fₙ = Fₙ₋₁ + Fₙ₋₂ > Fₙ₋₁ because every term is positive. So no value appears twice, and once a term exceeds the bound, every later term does too. That is why a loop that stops at the first term over the bound is correct.

Adding parities. Even + even = even, even + odd = odd, odd + odd = even: add the remainders mod 2 and take the remainder again (0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 2 → 0). Since each Fibonacci term is the sum of the two before it, the parities of two consecutive terms decide the parity of the next.

Exponential growth. When terms grow exponentially, the number of terms below a bound N is proportional to log N, not N. The Complexity section turns this into a concrete inequality for the even terms.

Brute force

Two approaches come to mind first.

1. Walk through every integer from 1 to 4,000,000 and check whether it is a Fibonacci number and whether it is even. That is at least O(N) checks for a bound N, plus the cost of each Fibonacci-membership test.
2. Generate the Fibonacci sequence directly and add the terms up to the bound that are even.

a, b = 1, 2
total = 0
while a <= 4000000:
    if a % 2 == 0:
        total += a
    a, b = b, a + b

The second approach is already fast. Fibonacci numbers grow exponentially, so there are only 32 terms up to 4,000,000 and the loop runs 32 times: O(log N) time and O(1) space. But only 11 of those 32 terms are even; the other 21 iterations check a parity and throw the term away. Below we prove exactly where the even terms appear and derive a recurrence that produces only them. The asymptotic complexity stays the same, but the loop runs about a third as often, the parity test disappears, and the result explains why in a formula.

Derivation

Step 1: look for a pattern in a small example. Write the first ten terms next to their parities.

n      :  1  2  3  4  5  6  7  8  9 10
Fₙ     :  1  2  3  5  8 13 21 34 55 89
parity :  o  e  o  o  e  o  o  e  o  o

The even terms are F₂ = 2, F₅ = 8 and F₈ = 34: indices 2, 5, 8, every third term. The even terms up to 89 add up to 2 + 8 + 34 = 44, a value the code will use as its small-example check.

Step 2: prove that exactly every third term is even. Look at the parity pair of two consecutive terms (Fₙ, Fₙ₊₁). The next pair is (Fₙ₊₁, Fₙ + Fₙ₊₁), so it depends only on the current pair.

(odd, even) → (even, odd + even = odd) → (odd, even + odd = odd) → (odd, odd + odd = even) → (odd, even) → …

The first pair (F₁, F₂) = (1, 2) is (odd, even), and after three steps it returns to (odd, even). Because each pair is determined by the one before it, this cycle of length 3 repeats forever. So Fₙ is even exactly when n leaves remainder 2 on division by 3, that is, when n = 3k − 1 for k = 1, 2, 3, … From here on, call the even terms Eₖ = F₃ₖ₋₁: E₁ = F₂ = 2, E₂ = F₅ = 8, E₃ = F₈ = 34.

Step 3: relate terms three apart. For n ≥ 7 the definition Fₘ = Fₘ₋₁ + Fₘ₋₂ applies at m = n, n − 1, n − 2 and n − 4 (all at least 3). Expand one step at a time:

Fₙ = Fₙ₋₁ + Fₙ₋₂
   = (Fₙ₋₂ + Fₙ₋₃) + Fₙ₋₂              ← expand Fₙ₋₁
   = 2Fₙ₋₂ + Fₙ₋₃
   = 2(Fₙ₋₃ + Fₙ₋₄) + Fₙ₋₃             ← expand Fₙ₋₂
   = 3Fₙ₋₃ + 2Fₙ₋₄
   = 3Fₙ₋₃ + Fₙ₋₄ + (Fₙ₋₅ + Fₙ₋₆)       ← expand one copy of Fₙ₋₄
   = 3Fₙ₋₃ + (Fₙ₋₄ + Fₙ₋₅) + Fₙ₋₆
   = 3Fₙ₋₃ + Fₙ₋₃ + Fₙ₋₆               ← Fₙ₋₄ + Fₙ₋₅ = Fₙ₋₃
   = 4Fₙ₋₃ + Fₙ₋₆

The step Fₙ₋₄ + Fₙ₋₅ = Fₙ₋₃ is the definition at m = n − 3, which is allowed because n ≥ 7 gives n − 3 ≥ 4.

Step 4: turn it into a recurrence on even terms. Substitute n = 3k − 1. Then n − 3 = 3(k − 1) − 1 and n − 6 = 3(k − 2) − 1, so

Eₖ = 4Eₖ₋₁ + Eₖ₋₂    (k ≥ 3, where n = 3k − 1 ≥ 8 ≥ 7)

Checking by hand: E₃ = 4 · 8 + 2 = 34 and E₄ = 4 · 34 + 8 = 144, and indeed F₁₁ = 144 (F₉ = 55, F₁₀ = 89, F₁₁ = 144).

Step 5: settle the starting values. The recurrence is proved for k ≥ 3, so E₁ = 2 and E₂ = 8 are the natural seeds. For convenience the code adds one more value, E₀ = 0. Since 4 · E₁ + E₀ = 4 · 2 + 0 = 8 = E₂, starting from (E₀, E₁) = (0, 2) produces E₂ and everything after it with the same formula. E₀ is only a helper and is never added.

Final algorithm

With the bound called limit:

1. Start with previous = 0 (E₀), current = 2 (E₁) and sum = 0.
2. While current ≤ limit, add current to sum, then replace (previous, current) with (current, 4 · current + previous).
3. Once current > limit, return sum.
4. Before printing the answer, check small bounds: 1 → 0 (no even term), 2 → 2, 8 → 2 + 8 = 10 (the bound itself is included), and 89 → 44 (the example from Step 1). If any of them differs, exit with a nonzero status.

The C++ version has one extra check so that computing the next term cannot overflow for very large bounds; the integer-range notes below explain it.

Correctness proof

When the loop makes its j-th test (j = 1, 2, …), the following invariant holds:

• previous = Eⱼ₋₁ and current = Eⱼ
• sum = E₁ + E₂ + … + Eⱼ₋₁

At the start (j = 1), previous = 0 = E₀, current = 2 = E₁ and sum = 0 (the empty sum). If current ≤ limit, adding Eⱼ makes sum = E₁ + … + Eⱼ, the new current is 4Eⱼ + Eⱼ₋₁ = Eⱼ₊₁ (by Step 5 when j = 1 and by the recurrence of Step 4 when j ≥ 2), and the new previous is Eⱼ, so the invariant holds for j + 1.

The E values are Fibonacci terms, so they strictly increase and eventually exceed limit. The loop ends at the first j with Eⱼ > limit, and at that point sum = E₁ + … + Eⱼ₋₁. Because the sequence is strictly increasing, E₁, …, Eⱼ₋₁ are all at most limit and every term from Eⱼ on exceeds it. Step 2 showed that the even Fibonacci terms are exactly E₁, E₂, …, and strict increase means each value occurs once. So sum is exactly the sum of the even Fibonacci terms not exceeding limit.

Complexity

Number of iterations. For k ≥ 3, Eₖ = 4Eₖ₋₁ + Eₖ₋₂ > 4Eₖ₋₁, and E₂ = 8 = 4E₁, so Eₖ ≥ 4Eₖ₋₁ for all k ≥ 2. Hence Eₖ ≥ 2 · 4^(k−1), and the number K of even terms up to limit satisfies 2 · 4^(K−1) ≤ limit, that is, K ≤ 1 + log₄(limit / 2). For limit = 4,000,000, log₄(2,000,000) ≈ 10.47, so K ≤ 11, and there are in fact 11. The loop runs O(log limit) times and each iteration is constant time on fixed-width integers, so the time is O(log limit). Only three values are stored, so the space is O(1).

Integer range. Every value in this problem is small: the last even term added is at most four million, and the next even term built when the loop ends is about fifteen million, which fits even in 32 bits. Still, the function should be reusable with other bounds, so here is the range analysis.

• Size of the sum: applying Eⱼ₋₁ ≤ Eⱼ / 4 repeatedly, with E_K the last term added, the sum is E_K (1 + 1/4 + 1/16 + …) < (4/3) E_K ≤ (4/3) limit. The sum is always less than 4/3 of the bound.
• The C++ code uses unsigned long long. The C++ standard guarantees it is at least 64 bits wide (it follows the C standard’s minimum for ULLONG_MAX), and unsigned arithmetic is defined modulo 2^N, so there is no undefined behaviour. Overflow would still silently give a wrong value, so it has to be avoided.
• The next term 4 · current + previous can overflow when the bound is close to 2^64. If it wrapped around to a small value, the loop could run forever or add a wrong term. So before computing it, the C++ code tests current > (limit − previous) / 4. For integers, 4 · current > limit − previous is the same as current > ⌊(limit − previous) / 4⌋, so when the test is true the next term would exceed limit and the loop would end anyway; stopping without computing it gives the same result. Inside the loop previous ≤ current ≤ limit, so limit − previous cannot wrap below zero either.
• With that check, the next term is computed only when it is at most limit, so it never overflows, and the sum is below (4/3) limit, which is below 2^64 whenever limit ≤ 2^63. The C++ function is exact for limit ≤ 2^63.
• Python’s int has unlimited precision and cannot overflow, so the Python version leaves the check out. The algorithm is the same.

Boundary cases

• limit < 2: there is no even term, since the smallest is 2, and the result is 0. The loop condition is false from the start, so no special case is needed. In Python, zero and negative bounds also give 0; the C++ type is unsigned and cannot hold a negative bound.
• limit equal to an even term: “does not exceed” is inclusive, so that term is added. limit = 2 must give 2 and limit = 8 must give 10; both are among the program’s small-example checks.
• Starting with 1, 1: under the other common definition, 1, 1, 2, 3, …, the value 1 appears twice, but 1 is odd, so the sum of the even terms is unaffected. Starting with 1 and 2 does not change the result of this particular sum.
• Very large limit (C++): as shown above, the result is exact for limit ≤ 2^63; beyond that the sum itself may overflow.

C++17

#include <iostream>

// Sum of the even Fibonacci terms (1, 2, 3, 5, 8, ...) that do not exceed limit.
// The even terms are 2, 8, 34, ..., and each one is 4 * previous + the one before.
unsigned long long sum_even_fibonacci_up_to(unsigned long long limit) {
    unsigned long long previous = 0;
    unsigned long long current = 2;
    unsigned long long sum = 0;
    while (current <= limit) {
        sum += current;
        // previous <= current <= limit, so limit - previous does not wrap.
        // If 4 * current + previous would exceed limit, stop before computing it.
        if (current > (limit - previous) / 4) {
            break;
        }
        const unsigned long long next = 4 * current + previous;
        previous = current;
        current = next;
    }
    return sum;
}

int main() {
    if (sum_even_fibonacci_up_to(1) != 0 || sum_even_fibonacci_up_to(2) != 2 ||
        sum_even_fibonacci_up_to(8) != 10 || sum_even_fibonacci_up_to(89) != 44) {
        return 1;
    }
    std::cout << sum_even_fibonacci_up_to(4000000) << '\n';
    return 0;
}

The small examples are checked with if, not assert, because assert disappears in builds that define NDEBUG. If any check fails, return 1 gives a nonzero exit status.

Python 3

def sum_even_fibonacci_up_to(limit: int) -> int:
    """Sum of the even Fibonacci terms (1, 2, 3, 5, 8, ...) that do not exceed limit.

    The even terms are 2, 8, 34, ..., and each one is 4 * previous + the one before.
    """
    previous, current = 0, 2
    total = 0
    while current <= limit:
        total += current
        previous, current = current, 4 * current + previous
    return total


def main() -> None:
    if (
        sum_even_fibonacci_up_to(1) != 0
        or sum_even_fibonacci_up_to(2) != 2
        or sum_even_fibonacci_up_to(8) != 10
        or sum_even_fibonacci_up_to(89) != 44
    ):
        raise SystemExit(1)
    print(sum_even_fibonacci_up_to(4000000))


if __name__ == "__main__":
    main()

Same algorithm and same small examples as the C++ version. previous, current = current, 4 * current + previous evaluates the whole right-hand side before assigning, so no temporary is needed. A failed small example raises SystemExit(1) for exit status 1; assert is avoided because running Python with -O removes it.

Answer and checks

Building the even terms up to four million with the recurrence gives the following (running total in parentheses):

E₁  = 2                              (2)
E₂  = 8                              (10)
E₃  = 4 · 8      + 2      = 34       (44)
E₄  = 4 · 34     + 8      = 144      (188)
E₅  = 4 · 144    + 34     = 610      (798)
E₆  = 4 · 610    + 144    = 2584     (3382)
E₇  = 4 · 2584   + 610    = 10946    (14328)
E₈  = 4 · 10946  + 2584   = 46368    (60696)
E₉  = 4 · 46368  + 10946  = 196418   (257114)
E₁₀ = 4 · 196418 + 46368  = 832040   (1089154)
E₁₁ = 4 · 832040 + 196418 = 3524578
E₁₂ = 4 · 3524578 + 832040 = 14930352 > 4,000,000 → stop

So the answer is 1089154 + 3524578 = 4613732.

The result is checked three ways.

1. Small examples. Before printing the answer, both programs check that bounds 1, 2, 8 and 89 give 0, 2, 10 and 44, and exit with a nonzero status otherwise. The value 44 for bound 89 was also confirmed by hand from the first ten terms in Step 1 of the derivation.
2. Both implementations agree. In this series’ repository a check script compiles the C++ with g++ -std=c++17 -O2 -Wall -Wextra -Werror (warnings count as failures), runs it, and runs the Python with python3 -I -B. Both outputs must match the stored answer.txt byte for byte; a nonzero exit status or a timeout (1 s for C++, 10 s for Python) is a failure. By the series rules, only code that passes this check is published.
3. By hand and another method. You can confirm that each row of the table is a real Fibonacci number (for example 610 = F₁₄ and 2584 = F₁₇) by adding terms pairwise. Running the brute-force loop above, generating all 32 terms and adding the even ones, and comparing the results is good practice too.

Going further

• Sum of the odd terms. How would you get the sum of the odd terms under the same bound? Subtract the even sum from the sum of all terms. There is a closed form for F₁ + F₂ + … + Fₙ in terms of Fₙ₊₂; derive it yourself for this post’s numbering (F₁ = 1, F₂ = 2).
• Other remainders. How often does a multiple of 3 appear among the Fibonacci terms? Follow the pairs (Fₙ mod 3, Fₙ₊₁ mod 3) as in Step 2 to find the period, then see whether Step 3’s method gives a recurrence between those terms too.
• m steps instead of three. Generalising the expansion in Step 3 expresses Fₙ in terms of Fₙ₋ₘ and Fₙ₋₂ₘ. What are the coefficients for m = 2, and why does 4 appear for m = 3?
• An overflow experiment. Remove the overflow check from the C++ code and pass a bound close to ULLONG_MAX. What happens? For bounds above 2^63, does the sum actually overflow? Compare with Python’s result.
• Later problems in this series. Fibonacci numbers and recurrences show up again in other problems within 1–100, sometimes with terms too large for fixed-width integers, so the range analysis here is worth keeping in mind.

Sources and license

• Project Euler, Problem 2 — the original problem. The Problem section of this post is my own summary of it and is shared under the same CC BY-NC-SA 4.0 license. Attribution for the problem: Project Euler.
• Project Euler, Copyright — the license of the problem text and how to link to problems. Because of the non-commercial condition, this post carries no ads.
• The solution, proofs and code are original. No Project Euler overview or editorial, forum post, member-only material or solution site was consulted. Motitory is not affiliated with or sponsored by Project Euler, and Project Euler has not reviewed this post.
• C++17 final working draft N4659 — §6.9.1 fundamental types (unsigned arithmetic modulo 2^N), §21.3.6 <climits> (ranges follow the C standard), §22.3 assert (NDEBUG)
• Python Standard Library: Numeric Types — unlimited precision of int
• Python Language Reference: The assert statement — assert is removed in optimised mode