Problem Statement

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.

Understanding the Problem

We need to:

  1. Generate Fibonacci numbers up to 4,000,000
  2. Filter for only the even ones
  3. Sum them up

The even Fibonacci numbers in the sequence are: 2, 8, 34, 144, 610, 2584, 10946, 75025, 317811, 1346269, 5702887…

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13

from typing import Iterator
from itertools import takewhile

def fibonacci(a: int = 0, b: int = 1) -> Iterator[int]:
    while True:
        yield a
        a, b = b, a + b

sum(
    x
    for x in takewhile(lambda x: x <= 4_000_000, fibonacci())
    if x % 2 == 0
)

Result: 4613732

How This Solution Works

The Fibonacci Generator

1
2
3
4

def fibonacci(a: int = 0, b: int = 1) -> Iterator[int]:
    while True:
        yield a
        a, b = b, a + b

This creates an infinite generator that produces Fibonacci numbers:

  • yield a returns the current Fibonacci number
  • a, b = b, a + b is Python’s elegant way to update both values simultaneously
  • The generator is lazy - it only computes values when requested

Using takewhile

1

takewhile(lambda x: x <= 4_000_000, fibonacci())

takewhile stops the generator as soon as a condition becomes false:

  • It takes values from fibonacci() while they’re ≤ 4,000,000
  • Once we hit a number > 4,000,000, it stops completely
  • This prevents infinite iteration

The Complete Pipeline

1
2
3
4
5

sum(
    x
    for x in takewhile(lambda x: x <= 4_000_000, fibonacci())
    if x % 2 == 0
)

This creates a processing pipeline:

  1. Generate Fibonacci numbers infinitely
  2. Take only those ≤ 4,000,000
  3. Filter for even numbers (x % 2 == 0)
  4. Sum the results

Alternative Solutions

Solution 1: Traditional Loop

1
2
3
4
5
6
7
8
9
10

def solution_traditional():
    a, b = 0, 1
    total = 0
    
    while a <= 4_000_000:
        if a % 2 == 0:
            total += a
        a, b = b, a + b
    
    return total

Solution 2: List-Based Approach

1
2
3
4
5
6
7

def solution_list():
    fibs = [0, 1]
    
    while fibs[-1] <= 4_000_000:
        fibs.append(fibs[-1] + fibs[-2])
    
    return sum(x for x in fibs if x <= 4_000_000 and x % 2 == 0)

Solution 3: Mathematical Pattern (Most Efficient)

1
2
3
4
5
6
7
8
9
10
11

def solution_mathematical():
    # Every 3rd Fibonacci number is even: F(3k)
    # We can generate only even Fibonacci numbers directly
    total = 0
    a, b = 2, 8  # First two even Fibonacci numbers
    
    while a <= 4_000_000:
        total += a
        a, b = b, 4 * b + a  # Formula for next even Fibonacci
    
    return total

Deep Dive: Why Every 3rd Fibonacci is Even

Here’s a fascinating pattern in Fibonacci numbers:

1
2
3
4
5
6
7
8
9

F(1) = 1  (odd)
F(2) = 1  (odd) 
F(3) = 2  (even) ✓
F(4) = 3  (odd)
F(5) = 5  (odd)
F(6) = 8  (even) ✓
F(7) = 13 (odd)
F(8) = 21 (odd)
F(9) = 34 (even) ✓

Pattern: Even, Odd, Odd, Even, Odd, Odd, …

This happens because:

  • Even + Even = Even
  • Odd + Odd = Even
  • Even + Odd = Odd

So the sequence follows: O, O, E, O, O, E, O, O, E…

Performance Comparison

  • My solution: O(n) time, O(1) space, very readable
  • Traditional loop: O(n) time, O(1) space, most straightforward
  • List-based: O(n) time, O(n) space, less efficient
  • Mathematical pattern: O(log n) time, O(1) space, most efficient

Why I Like This Solution

  1. Functional Programming Style: Uses generator + takewhile + filter pipeline
  2. Infinite Generator: The fibonacci function is reusable for any range
  3. Lazy Evaluation: Only computes what’s needed
  4. Readable: The intent is very clear from the code structure
  5. Memory Efficient: No intermediate lists stored

Key Takeaways

  1. Generators are powerful for infinite sequences
  2. itertools.takewhile is perfect for conditional stopping
  3. Tuple unpacking (a, b = b, a + b) makes Fibonacci elegant
  4. Pipeline processing with generators is memory-efficient
  5. Mathematical patterns often exist in sequences - look for them!

Python Concepts Demonstrated

  • Type hints (Iterator[int])
  • Generator functions with yield
  • itertools module usage
  • Lambda functions
  • Generator expressions
  • Tuple unpacking

Test Your Understanding

Try modifying this solution for:

  1. Sum of odd Fibonacci numbers below 1,000,000
  2. Find the largest Fibonacci number below 10,000,000
  3. Generate Fibonacci numbers starting with different seeds (like 2, 3)
1
2
3
4

# Hint for #3:
def fibonacci_custom(a: int = 2, b: int = 3) -> Iterator[int]:
    # Your implementation here
    pass

Complete Working Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from typing import Iterator
from itertools import takewhile

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

def solve_euler_2():
    """Solve Project Euler Problem 2."""
    return sum(
        x
        for x in takewhile(lambda x: x <= 4_000_000, fibonacci())
        if x % 2 == 0
    )

if __name__ == "__main__":
    result = solve_euler_2()
    print(f"Sum of even Fibonacci numbers below 4,000,000: {result}")
    
    # Show first few even Fibonacci numbers for verification
    even_fibs = [x for x in takewhile(lambda x: x <= 100, fibonacci()) if x % 2 == 0]
    print(f"First few even Fibonacci numbers: {even_fibs}")

This is part of my Python Problem Solving series. Check out more solutions on my GitHub!