Project Euler #002: Even Fibonacci Numbers

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 Mathematics

The Fibonacci sequence is defined by the recurrence $F(n) = F(n−1) + F(n−2)$ with seeds $F(0) = 0, F(1) = 1$.

A beautiful observation: every third Fibonacci number is even. This follows from the parity pattern of the sequence — even, odd, odd, even, odd, odd, even, … — which repeats with period 3. So rather than checking each term for evenness, we could jump three steps at a time using the identity $F(n+3) = 4·F(n) + F(n−3)$. Our solution below takes the simpler filtering approach, which is perfectly readable and fast enough for this limit.

The Python Solution

from typing import Iterator
from itertools import takewhile

def fibonacci(a: int = 0, b: int = 1) -> Iterator[int]:
    """
    Generate an infinite Fibonacci sequence.

    This function returns a generator that yields Fibonacci numbers indefinitely,
    starting from the given initial values a and b.

    Parameters
    ----------
    a : int, optional
        The first number in the sequence, by default 0
    b : int, optional
        The second number in the sequence, by default 1

    Yields
    ------
    Iterator[int]
        An infinite generator of Fibonacci numbers.

    Examples
    --------
    >>> gen = fibonacci()
    >>> next(gen)
    0
    >>> next(gen)
    1
    >>> next(gen)
    1
    >>> next(gen)
    2
    """
    while True:
        yield a
        a, b = b, a + b


def answer(limit: int) -> int:
    """
    Return the sum of even-valued Fibonacci numbers not exceeding n.

    This function solves Project Euler problem 2 by generating Fibonacci numbers
    and summing only the even-valued ones that are less than or equal to 4,000,000.

    Returns
    -------
    int
        The sum of even Fibonacci numbers not exceeding 4 million.

    Examples
    --------
    >>> answer(4_000_000)
    4613732
    """
    return sum(
        x for x in takewhile(lambda x: x <= limit, fibonacci())
        if x % 2 == 0
        )

print(answer(4_000_000))  # 4613732

Generator Functions in Python

The yield keyword transforms fibonacci into a generator function. Instead of computing the entire sequence and returning a list, it produces one value at a time — resuming where it left off each time the caller asks for the next item. Memory usage is O(1) regardless of how large limit gets.

The tuple-swap a, b = b, a + b is idiomatic Python: the right-hand side is fully evaluated before any assignment occurs, so no temporary variable is needed — the Fibonacci step is atomic.

Answer (limit = 4,000,000): 4613732

Direct Link