Project Euler Problems 6-10: Primes, Squares & Sequences

TL;DR

Problems 6-10 introduce algorithmic number theory: computing sums and squares (Problem 6), prime generation via the Sieve of Eratosthenes (Problems 7, 10), digit manipulation (Problem 8), and Pythagorean triplets (Problem 9). Solutions jump from O(n) to O(n log log n) using sieves and memoization.

Project Euler problems 6-10 represent a significant difficulty step up from 1-5. You move from simple divisibility into prime sieves, sliding-window algorithms, and Diophantine equations. These problems teach essential techniques that scale to the full 100-problem set: the Sieve of Eratosthenes is foundational for any computational math work, and understanding Pythagorean triplets opens doors to combinatorial problem-solving.

This guide walks through all five problems with both naive and optimized solutions, emphasizing the mathematical insights that lead to dramatic speedups. By the end, you'll understand why a prime sieve beats trial division by orders of magnitude, and how to apply these lessons to even harder challenges.

Problem 6: Sum Square Difference

The Problem: For the first 100 natural numbers, find the difference between the square of the sum and the sum of the squares. That is, compute (1+2+...+100)² - (1²+2²+...+100²).

This problem tests understanding of mathematical formulas versus brute computation.

Brute Force Solution:

def sum_square_difference_bruteforce(n: int) -> int:
    """O(n): compute both sums via iteration."""
    sum_of_squares = sum(i**2 for i in range(1, n + 1))
    square_of_sum = sum(range(1, n + 1)) ** 2
    return square_of_sum - sum_of_squares

result = sum_square_difference_bruteforce(100)
print(result)  # 25164150

Time: O(n), Space: O(1). Straightforward but doesn't leverage mathematical structure.

Optimized Solution (Closed-Form Formulas):

Using well-known formulas:

• Sum: 1+2+...+n = n(n+1)/2
• Sum of squares: 1²+2²+...+n² = n(n+1)(2n+1)/6

def sum_square_difference_optimized(n: int) -> int:
    """O(1): use closed-form formulas."""
    sum_n = n * (n + 1) // 2
    sum_of_squares = n * (n + 1) * (2 * n + 1) // 6

    square_of_sum = sum_n ** 2

    return square_of_sum - sum_of_squares

result = sum_square_difference_optimized(100)
print(result)  # 25164150

Complexity: O(1) vs O(n). For n=100, brute force does 100 iterations; optimized does 6 operations. For n=10,000, brute force does 10K iterations; optimized still does 6.

---

Problem 7: 10001st Prime

The Problem: What is the 10,001st prime number?

Finding the nth prime requires either trial division (slow) or the Sieve of Eratosthenes (fast). This is the classic motivator for learning sieves.

Brute Force Solution (Trial Division):

def is_prime_trial(n: int) -> bool:
    """Check primality via trial division up to sqrt(n)."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def nth_prime_bruteforce(n: int) -> int:
    """O(n sqrt(n)): find nth prime by trial division."""
    count = 0
    candidate = 2

    while count < n:
        if is_prime_trial(candidate):
            count += 1
            if count == n:
                return candidate
        candidate += 1

result = nth_prime_bruteforce(10001)
print(result)  # 104743

Time: O(n√p) where p is the nth prime (~104,743). This is very slow for large n.

Optimized Solution (Sieve of Eratosthenes):

The sieve builds a boolean array marking all primes up to a limit, eliminating composites by marking multiples of each prime.

def sieve_of_eratosthenes(limit: int) -> list[int]:
    """O(n log log n): sieve all primes up to limit."""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            # Mark all multiples of i as composite
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False

    return [i for i in range(2, limit + 1) if is_prime[i]]

def nth_prime_optimized(n: int) -> int:
    """O(limit log log limit): use sieve to find nth prime."""
    # Approximate upper bound: nth prime ~ n * ln(n) for large n
    limit = max(15, int(n * (__import__('math').log(n + 1) + 2)))

    while True:
        primes = sieve_of_eratosthenes(limit)
        if len(primes) >= n:
            return primes[n - 1]
        limit *= 2

result = nth_prime_optimized(10001)
print(result)  # 104743

Complexity: Sieve is O(n log log n) vs trial division O(n√n). For the 10,001st prime:

• Trial division: ~104,743 candidates × √104,743 ≈ 10M operations
• Sieve: ~130,000 limit × log(log(130,000)) ≈ 2M operations

The sieve is 5-10x faster and easily handles larger n.

---

Problem 8: Largest Product of 13 Consecutive Digits

The Problem: Given a 1000-digit number (hardcoded in the problem), find the 13 consecutive digits whose product is largest.

This is a sliding-window problem: maintain a window of 13 digits, slide it across the string, compute products, track the maximum.

Brute Force Solution:

def largest_product_bruteforce(digits_str: str, window_size: int) -> int:
    """O(n*k): check all windows of size k."""
    max_product = 0

    for i in range(len(digits_str) - window_size + 1):
        window = digits_str[i:i + window_size]
        product = 1
        for digit in window:
            product *= int(digit)
        max_product = max(max_product, product)

    return max_product

# Example (using first 100 digits of the 1000-digit number)
digits = "73167176531330624919225119674151088626142863460141595621011573228220635045648233182332206999"
result = largest_product_bruteforce(digits, 13)

Time: O(n × k) where n=1000, k=13, so ~13,000 operations. Space: O(1).

Optimized Solution (Sliding Window with Smart Recomputation):

Key optimization: when sliding the window, the new product can be computed as (old_product / left_digit) × new_right_digit. However, this requires division, which fails if there are zeros in the window. Better approach: skip windows containing 0 (product is 0 anyway).

def largest_product_optimized(digits_str: str, window_size: int) -> int:
    """O(n): sliding window with zero-skipping."""
    max_product = 0

    i = 0
    while i <= len(digits_str) - window_size:
        window = digits_str[i:i + window_size]

        # If window contains 0, skip to after the 0
        if '0' in window:
            i += window.index('0') + 1
            continue

        # Compute product for this window
        product = 1
        for digit in window:
            product *= int(digit)

        max_product = max(max_product, product)
        i += 1

    return max_product

digits = "73167176531330624919225119674151088626142863460141595621011573228220635045648233182332206999"
result = largest_product_optimized(digits, 13)

Complexity: O(n) amortized. In the worst case (no zeros), every position is checked once. With zeros, windows are skipped, reducing iterations. The inner product computation is O(k), but k is constant (13), so overall O(n).

---

Problem 9: Special Pythagorean Triplet

The Problem: A Pythagorean triplet (a, b, c) satisfies a² + b² = c². Find the unique triplet where a + b + c = 1000, and return a × b × c.

This involves solving a Diophantine equation: find (a, b, c) such that a² + b² = c² and a + b + c = 1000.

Brute Force Solution:

def special_pythagorean_triplet_bruteforce() -> int:
    """O(n³): triple nested loop."""
    for a in range(1, 1000):
        for b in range(a + 1, 1000):
            for c in range(b + 1, 1000):
                if a + b + c == 1000 and a**2 + b**2 == c**2:
                    return a * b * c
    return 0

result = special_pythagorean_triplet_bruteforce()
print(result)  # 31875000

Time: O(n³) with n=1000, so ~1 billion iterations. Very slow.

Optimized Solution (Reduce to Double Loop):

Constraint: a + b + c = 1000. So c = 1000 - a - b. Pythagorean constraint: a² + b² = c² = (1000 - a - b)².

Expand: a² + b² = 1000² - 2×1000(a+b) + (a+b)² Simplify: a² + b² = 1,000,000 - 2000(a+b) + a² + 2ab + b² Rearrange: 0 = 1,000,000 - 2000(a+b) + 2ab Solve: 2ab - 2000(a+b) = -1,000,000 ab - 1000(a+b) = -500,000 ab - 1000a - 1000b = -500,000 a(b - 1000) = 1000b - 500,000 a = (1000b - 500,000) / (b - 1000)

def special_pythagorean_triplet_optimized() -> int:
    """O(n²): derive c from a,b; compute algebraically."""
    for a in range(1, 500):
        for b in range(a + 1, 1000 - a):
            c = 1000 - a - b
            if a**2 + b**2 == c**2:
                return a * b * c
    return 0

result = special_pythagorean_triplet_optimized()
print(result)  # 31875000

Further optimized using algebra:

def special_pythagorean_triplet_algebraic() -> int:
    """O(n): use derived formula."""
    # From: a(b - 1000) = 1000b - 500,000
    # We iterate b and solve for a
    for b in range(2, 500):
        numerator = 1000 * b - 500_000
        denominator = b - 1000
        if numerator % denominator == 0:  # a must be integer
            a = numerator // denominator
            if a > 0 and a < b:
                c = 1000 - a - b
                if a**2 + b**2 == c**2:
                    return a * b * c
    return 0

result = special_pythagorean_triplet_algebraic()
print(result)  # 31875000

Complexity: O(n²) optimized vs O(n³) brute force. The algebraic version approaches O(n) but includes division overhead. Practical speedup: ~100x for n=1000.

---

Problem 10: Sum of Primes Below 2 Million

The Problem: Find the sum of all prime numbers below 2,000,000.

This is pure sieve application: generate all primes below 2M, sum them.

Brute Force Solution (Trial Division):

def is_prime_trial(n: int) -> bool:
    """Trial division primality test."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def sum_primes_bruteforce(limit: int) -> int:
    """O(n sqrt(n)): trial division on each candidate."""
    total = 0
    for i in range(2, limit):
        if is_prime_trial(i):
            total += i
    return total

result = sum_primes_bruteforce(2_000_000)
# Very slow: ~2M candidates × √2M ≈ billions of operations

Time: O(n√n) with n=2M, so millions of operations per candidate. Impractical.

Optimized Solution (Sieve of Eratosthenes):

def sieve_of_eratosthenes_sum(limit: int) -> int:
    """O(n log log n): sieve + sum."""
    is_prime = [True] * limit
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit, i):
                is_prime[j] = False

    return sum(i for i in range(2, limit) if is_prime[i])

result = sieve_of_eratosthenes_sum(2_000_000)
print(result)  # 142913828922

Memory-Optimized Variant (Segmented Sieve):

For very large limits, a full sieve uses O(n) memory. A segmented sieve splits the range into chunks, sieving each chunk while keeping memory constant.

def simple_sieve(limit: int) -> list[int]:
    """Generate primes up to sqrt(limit)."""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return [i for i in range(2, limit + 1) if is_prime[i]]

def sum_primes_segmented(limit: int) -> int:
    """O(n log log n) time, O(sqrt(n)) space."""
    sqrt_limit = int(limit**0.5) + 1
    base_primes = simple_sieve(sqrt_limit)

    # Sieve all numbers up to sqrt(limit)
    total = sum(base_primes)

    # Segmented sieve for [sqrt+1, limit)
    low = sqrt_limit + 1
    high = min(low + 100_000, limit)

    while low < limit:
        is_prime = [True] * (high - low + 1)

        for p in base_primes:
            start = max(p * p, ((low + p - 1) // p) * p)
            for j in range(start, high + 1, p):
                is_prime[j - low] = False

        for i in range(len(is_prime)):
            if is_prime[i]:
                total += low + i

        low = high + 1
        high = min(low + 100_000, limit)

    return total

result = sum_primes_segmented(2_000_000)
print(result)  # 142913828922

Complexity: Standard sieve: O(n log log n) time, O(n) space. Segmented sieve: O(n log log n) time, O(√n) space.

For n=2M:

• Trial division: billions of operations, impractical
• Sieve: ~8M operations, completes in <1 second
• Segmented sieve: same complexity, 1/100th the memory

---

Key Takeaways

1. Closed-form formulas (Problem 6): Use math to eliminate loops. O(1) beats O(n) every time.
2. Sieve of Eratosthenes (Problems 7, 10): The gold standard for finding primes. O(n log log n) beats trial division by orders of magnitude.
3. Sliding window optimization (Problem 8): Smart iteration (skipping zeros) reduces redundant computation.
4. Algebraic simplification (Problem 9): Reduce the dimensionality of your search space using constraints. O(n³) → O(n).
5. Memory vs speed tradeoffs (Problem 10): Segmented sieves let you handle massive limits efficiently.

These techniques form the backbone of algorithmic problem-solving. Problems 6-10 mark the transition from "basic coding" to "algorithmic thinking"—master these, and problems 11-20 become approachable.

Conclusion

Project Euler problems 6-10 cement the fundamentals: mathematical insight beats brute force, and understanding your data's structure (primes, windows, constraints) reveals optimization opportunities. Whether you're prepping for technical interviews or building a foundation in computational mathematics, these five problems are essential. Implement them, time them, and feel the dramatic difference between naive and optimized approaches.