Project Euler Problems 11-15: Grids, Divisors & Combinatorics

TL;DR

Problems 11-15 introduce grid manipulation (Problem 11), divisor counting (Problem 12), string parsing and slicing (Problem 13), iterative sequences (Problem 14), and combinatorics via dynamic programming (Problem 15). Solutions highlight the power of memoization, efficient iteration, and recognizing structural patterns in data.

Project Euler problems 11-15 represent a significant jump in conceptual difficulty. You're no longer working with simple arithmetic—now you're manipulating 2D grids, counting divisors efficiently, parsing multi-digit numbers, and computing massive combinatorial values. These problems teach essential algorithmic patterns: grid traversal, memoization, divisor enumeration, and dynamic programming.

Problem 11: Largest Product in a Grid

The Problem: Given a 20×20 grid of numbers, find the four adjacent numbers (horizontal, vertical, or diagonal) whose product is largest.

This is a grid-scan problem: check all rows, columns, and diagonals for each position, computing products of four consecutive elements.

Problem Setup:

grid_str = """08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 95 65 53 87 06 16 91 19 35 68 76 74 20 73 02 29 23
...
"""

grid = []
for line in grid_str.strip().split('\n'):
    grid.append([int(x) for x in line.split()])

print(f"Grid dimensions: {len(grid)} rows × {len(grid[0])} columns")

Brute Force Solution:

def largest_product_in_grid_bruteforce(grid: list[list[int]]) -> int:
    """O(n²): check all positions, all directions."""
    rows, cols = len(grid), len(grid[0])
    max_product = 0

    directions = [
        (0, 1),   # Right
        (1, 0),   # Down
        (1, 1),   # Diagonal down-right
        (1, -1),  # Diagonal down-left
    ]

    for r in range(rows):
        for c in range(cols):
            for dr, dc in directions:
                # Check if 4 elements fit in this direction
                r_end, c_end = r + 3 * dr, c + 3 * dc
                if 0 <= r_end < rows and 0 <= c_end < cols:
                    product = 1
                    for i in range(4):
                        product *= grid[r + i * dr][c + i * dc]
                    max_product = max(max_product, product)

    return max_product

Time: O(rows × cols × 4 directions × 4 elements) = O(n²), where n=20. Space: O(1).

Optimized Solution (Same Complexity, Better Constants):

The complexity is already optimal (you must examine all positions). The optimization is in constant factors: avoid redundant multiplication, use efficient loops.

def largest_product_in_grid_optimized(grid: list[list[int]]) -> int:
    """O(n²): optimized grid scan."""
    rows, cols = len(grid), len(grid[0])
    max_product = 0

    # Right
    for r in range(rows):
        for c in range(cols - 3):
            product = grid[r][c] * grid[r][c+1] * grid[r][c+2] * grid[r][c+3]
            max_product = max(max_product, product)

    # Down
    for r in range(rows - 3):
        for c in range(cols):
            product = grid[r][c] * grid[r+1][c] * grid[r+2][c] * grid[r+3][c]
            max_product = max(max_product, product)

    # Diagonal down-right
    for r in range(rows - 3):
        for c in range(cols - 3):
            product = grid[r][c] * grid[r+1][c+1] * grid[r+2][c+2] * grid[r+3][c+3]
            max_product = max(max_product, product)

    # Diagonal down-left
    for r in range(rows - 3):
        for c in range(3, cols):
            product = grid[r][c] * grid[r+1][c-1] * grid[r+2][c-2] * grid[r+3][c-3]
            max_product = max(max_product, product)

    return max_product

Complexity: Both O(n²). The second is faster in practice due to simpler loop structure and no direction vector lookup overhead.

---

Problem 12: Highest Divisible Triangular Number

The Problem: A triangular number is the sum of the first n natural numbers: T(n) = 1+2+...+n = n(n+1)/2. Find the first triangular number with over 500 divisors.

This requires two optimizations: (1) efficient triangular number generation, (2) fast divisor counting.

Brute Force Solution:

def count_divisors_bruteforce(n: int) -> int:
    """O(n): count divisors by trial division."""
    count = 0
    for i in range(1, n + 1):
        if n % i == 0:
            count += 1
    return count

def triangular_number_bruteforce(divisor_target: int) -> int:
    """O(T(n) * T(n)): brute force triangular + divisor count."""
    n = 1
    while True:
        triangular = n * (n + 1) // 2
        if count_divisors_bruteforce(triangular) > divisor_target:
            return triangular
        n += 1

Time: Very slow. For T(n)~100M, counting divisors naively takes √100M ≈ 10K operations per number.

Optimized Solution (Divisor Counting via Prime Factorization):

Key insight: if n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ, then the divisor count is (a₁+1)(a₂+1)...(aₖ+1).

def count_divisors_optimized(n: int) -> int:
    """O(sqrt(n)): count divisors via prime factorization."""
    count = 1
    factor = 2

    while factor * factor <= n:
        exponent = 0
        while n % factor == 0:
            exponent += 1
            n //= factor
        count *= (exponent + 1)
        factor += 1

    # Remaining n (if > 1) is a prime factor
    if n > 1:
        count *= 2

    return count

def triangular_number_optimized(divisor_target: int) -> int:
    """O(sqrt(T(n))): use optimized divisor counting."""
    n = 1
    while True:
        triangular = n * (n + 1) // 2
        if count_divisors_optimized(triangular) > divisor_target:
            return triangular
        n += 1

Further optimization: T(n) = n(n+1)/2. If gcd(n, n+1) = 1 (always true for consecutive integers), then divisor_count(T(n)) = divisor_count(n) × divisor_count(n+1).

def triangular_number_highly_optimized(divisor_target: int) -> int:
    """O(sqrt(n)): use multiplicative property of T(n)."""
    n = 1
    div_n = count_divisors_optimized(1)  # divisors of 1

    while True:
        # T(n+1) = (n+1)(n+2)/2, but more efficiently:
        # divisors(T(n)) = divisors(n) * divisors(n+1) when gcd(n,n+1)=1
        n += 1
        if n % 2 == 0:
            div_n_plus_1 = count_divisors_optimized(n + 1)
            div_next = (count_divisors_optimized(n // 2) * div_n_plus_1)
        else:
            div_n_plus_1 = count_divisors_optimized((n + 1) // 2)
            div_next = (count_divisors_optimized(n) * div_n_plus_1)

        if div_next > divisor_target:
            triangular = n * (n + 1) // 2
            return triangular
        div_n = div_n_plus_1

Complexity: Optimized is O(√T(n) × √n) ≈ O(n) amortized. Brute force is O(T(n) × √T(n)) ≈ O(n²). For target=500, optimized finds the answer in ~1 second; brute force takes hours.

---

Problem 13: Large Sum

The Problem: You're given 100 fifty-digit numbers. Find the first 10 digits of their sum.

Python handles arbitrary-precision integers natively, so this is trivial: add the numbers, convert to string, take the first 10 characters.

Solution:

def large_sum_first_digits() -> str:
    """Compute sum of 100 50-digit numbers, return first 10 digits."""
    numbers = [
        37107287533902102798797998220837590246910760607252868541
        ...  # 99 more lines
    ]

    total = sum(numbers)
    return str(total)[:10]

# Or, if reading from a file/string:
def large_sum_from_string(numbers_str: str) -> str:
    """Parse numbers and return first 10 digits of sum."""
    numbers = [int(line.strip()) for line in numbers_str.strip().split('\n')]
    total = sum(numbers)
    return str(total)[:10]

The Catch: In languages without arbitrary-precision integers (C++, Java), you'd need to implement big integer addition or use a dedicated library. Python trivializes this problem—but the lesson is important: know your language's capabilities.

Complexity: O(n × k) where n=100, k=50 (digits). Addition is O(k), summing 100 numbers is O(n). Total: O(nk) = O(5000), negligible.

---

Problem 14: Longest Collatz Sequence

The Problem: The Collatz conjecture states that for any positive integer, repeatedly applying these rules eventually reaches 1:

• If n is even: n → n/2
• If n is odd: n → 3n+1

Find which starting number under 1 million produces the longest sequence (chain length).

Brute Force Solution:

def collatz_length_bruteforce(n: int) -> int:
    """O(unknown): compute chain length for a given n."""
    length = 1
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        length += 1
    return length

def longest_collatz_bruteforce(limit: int) -> int:
    """O(limit × chain_length): check all starts."""
    max_length = 0
    longest_start = 0

    for start in range(1, limit):
        length = collatz_length_bruteforce(start)
        if length > max_length:
            max_length = length
            longest_start = start

    return longest_start

Time: O(limit × avg_chain_length). For limit=1M, this is slow (~tens of millions of iterations).

Optimized Solution (Memoization):

Key insight: if we've already computed the chain length for some number, reuse it. For example, the chain from 10 is 10→5→16→8→4→2→1. When computing the chain from 5, we can stop early and add the known remainder.

from functools import lru_cache

@lru_cache(maxsize=None)
def collatz_length_memoized(n: int) -> int:
    """O(log n) with memoization."""
    if n == 1:
        return 1
    if n % 2 == 0:
        return 1 + collatz_length_memoized(n // 2)
    else:
        return 1 + collatz_length_memoized(3 * n + 1)

def longest_collatz_optimized(limit: int) -> int:
    """O(limit) with memoization."""
    max_length = 0
    longest_start = 0

    for start in range(1, limit):
        length = collatz_length_memoized(start)
        if length > max_length:
            max_length = length
            longest_start = start

    return longest_start

Complexity: With memoization, the same chain is computed once and reused for all starting numbers that share part of the chain. Amortized O(limit), vs O(limit × chain_length) brute force. Speedup: 5-10x.

---

Problem 15: Lattice Paths

The Problem: In a 20×20 grid, you start at the top-left and can only move right or down. How many distinct paths are there to reach the bottom-right?

This is a classic combinatorics problem: you need to make 20 right moves and 20 down moves (40 moves total), choosing which 20 are right (the rest are down). This is C(40, 20) = 40! / (20! × 20!).

Brute Force Solution (Recursion):

def lattice_paths_bruteforce(x: int, y: int) -> int:
    """O(2^(x+y)): recursive enumeration of all paths."""
    if x == 0 or y == 0:
        return 1  # Only one path: straight line
    return lattice_paths_bruteforce(x-1, y) + lattice_paths_bruteforce(x, y-1)

result = lattice_paths_bruteforce(20, 20)
# Extremely slow: 2^40 ≈ 1 trillion recursive calls

Time: O(2^n), exponential. For n=20, this is 1 trillion calls—impractical.

Optimized Solution 1 (Dynamic Programming):

Use a 2D table to store path counts. dp[i][j] = number of paths to position (i,j).

def lattice_paths_dp(x: int, y: int) -> int:
    """O(xy): bottom-up DP."""
    dp = [[1] * (y + 1) for _ in range(x + 1)]

    for i in range(1, x + 1):
        for j in range(1, y + 1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[x][y]

result = lattice_paths_dp(20, 20)
print(result)  # 137846528820

Time: O(xy), Space: O(xy). For x=y=20, this is 400 operations and 400 memory cells—negligible.

Optimized Solution 2 (Combinatorics):

Directly compute C(40, 20):

from math import comb

def lattice_paths_combinatorial(x: int, y: int) -> int:
    """O(min(x,y)): use combinatorial formula."""
    return comb(x + y, x)

result = lattice_paths_combinatorial(20, 20)
print(result)  # 137846528820

Time: O(1) with built-in math library, or O(min(x, y)) if implementing factorial manually. Space: O(1).

Optimized Solution 3 (Space-Efficient DP):

If you don't need the full table, use a single row that updates in place:

def lattice_paths_dp_optimized(x: int, y: int) -> int:
    """O(x*y) time, O(min(x,y)) space."""
    row = [1] * (y + 1)
    for _ in range(1, x + 1):
        for j in range(1, y + 1):
            row[j] += row[j - 1]
    return row[y]

result = lattice_paths_dp_optimized(20, 20)
print(result)  # 137846528820

Time: O(xy), Space: O(y) instead of O(xy). For large grids, memory is the bottleneck.

Complexity Comparison:

• Brute force: O(2^(x+y)) = O(2^40) ≈ 1 trillion calls. Do not use.
• DP (2D table): O(xy) time, O(xy) space. Clear and straightforward.
• Combinatorics: O(1) or O(min(x,y)) time, O(1) space. Most elegant.
• DP (1D table): O(xy) time, O(min(x,y)) space. Best balance for large grids.

---

Key Takeaways

1. Grid traversal (Problem 11): Simple iteration is optimal; focus on clean code and avoiding off-by-one errors.
2. Divisor counting (Problem 12): Prime factorization beats trial division. Multiplicative properties unlock further speedups.
3. Big integers (Problem 13): Know your language. Python's arbitrary precision trivializes this; other languages require workarounds.
4. Memoization (Problem 14): Trade memory for speed. Recursive definitions with memoization are powerful.
5. Dynamic programming (Problem 15): Bottom-up DP beats exponential recursion. Recognize the structure: overlapping subproblems + optimal substructure.

These five problems teach the transition from naive to sophisticated problem-solving. Problems 11-15 mark the boundary where brute force becomes genuinely impractical, forcing you to think algorithmically.

Conclusion

Project Euler problems 11-15 are where the "hard" problems start. Grid manipulation, divisor enumeration, memoization, and dynamic programming are tools you'll use for decades. Understanding why 2^40 is infeasible but C(40,20) is trivial—that's the mindset shift these problems cultivate. Work through them, feel the slowness of brute force, and appreciate the elegance of optimized solutions.