Project Euler Problem 149

Solution

Answer: 52852124

We are given a $2000 \times 2000$ grid filled with pseudo-random integers generated by a Lagged Fibonacci Generator (LFG), and we must find the maximum sum of adjacent entries in any of the four directions:

• horizontal,
• vertical,
• main diagonal,
• anti-diagonal.

The key challenge is efficiency: brute force over all possible subarrays in all directions would be far too slow.

---

Mathematical Analysis

1. The sequence generation

The sequence $s_k$ is defined by:

For $1 \le k \le 55$,

$$s_k = (100003 - 200003k + 300007k^3) \bmod 1000000 - 500000$$

For $56 \le k \le 4{,}000{,}000$,

$$s_k = (s_{k-24} + s_{k-55} + 1000000)\bmod 1000000 - 500000$$

These values lie in the interval

$$[-500000, 499999]$$

The $4{,}000{,}000$ terms are written row-by-row into a $2000 \times 2000$ matrix.

---

2. Maximum subarray problem

Suppose we have a 1D array:

$$[a_1,a_2,\dots,a_n]$$

We need the maximum sum of a contiguous block.

This is exactly the classical maximum subarray problem, solved optimally by Kadane’s algorithm in linear time.

---

Kadane’s algorithm

Define:

• $best$ = best sum seen so far,
• $current$ = best sum ending at current position.

For each value $x$:

$$current = \max(x, current+x)$$

$$best = \max(best, current)$$

This works because every optimal subarray ending at position $i$ either:

• starts fresh at $i$, or
• extends the optimal subarray ending at $i-1$.

Time complexity:

$$O(n)$$

---

3. Applying Kadane in 2D directions

We must run Kadane on every:

• row,
• column,
• diagonal,
• anti-diagonal.

Each line has length at most 2000.

Total elements examined is proportional to the total number of grid entries:

$$O(2000^2)$$

which is completely feasible.

---

Python Implementation

def generate_sequence():
    n = 4_000_000
    s = [0] * n

    # First 55 terms
    for k in range(1, 56):
        val = (100003 - 200003 * k + 300007 * k**3) % 1_000_000
        s[k - 1] = val - 500000

    # Remaining terms
    for k in range(55, n):
        val = (s[k - 24] + s[k - 55] + 1_000_000) % 1_000_000
        s[k] = val - 500000

    return s

def kadane(arr):
    best = arr[0]
    current = arr[0]

    for x in arr[1:]:
        current = max(x, current + x)
        best = max(best, current)

    return best

def solve():
    SIZE = 2000

    # Generate sequence
    seq = generate_sequence()

    # Build grid
    grid = [seq[i * SIZE:(i + 1) * SIZE] for i in range(SIZE)]

    ans = -10**18

    # -------------------------------------------------
    # Horizontal
    # -------------------------------------------------
    for row in grid:
        ans = max(ans, kadane(row))

    # -------------------------------------------------
    # Vertical
    # -------------------------------------------------
    for c in range(SIZE):
        col = [grid[r][c] for r in range(SIZE)]
        ans = max(ans, kadane(col))

    # -------------------------------------------------
    # Main diagonals
    # -------------------------------------------------
    # Start from top row
    for start_col in range(SIZE):
        diag = []
        r, c = 0, start_col

        while r < SIZE and c < SIZE:
            diag.append(grid[r][c])
            r += 1
            c += 1

        ans = max(ans, kadane(diag))

    # Start from left column (excluding top-left)
    for start_row in range(1, SIZE):
        diag = []
        r, c = start_row, 0

        while r < SIZE and c < SIZE:
            diag.append(grid[r][c])
            r += 1
            c += 1

        ans = max(ans, kadane(diag))

    # -------------------------------------------------
    # Anti-diagonals
    # -------------------------------------------------
    # Start from top row
    for start_col in range(SIZE):
        diag = []
        r, c = 0, start_col

        while r < SIZE and c >= 0:
            diag.append(grid[r][c])
            r += 1
            c -= 1

        ans = max(ans, kadane(diag))

    # Start from right column (excluding top-right)
    for start_row in range(1, SIZE):
        diag = []
        r, c = start_row, SIZE - 1

        while r < SIZE and c >= 0:
            diag.append(grid[r][c])
            r += 1
            c -= 1

        ans = max(ans, kadane(diag))

    return ans

print(solve())

---

Code Walkthrough

Sequence generation

s = [0] * n

Allocates space for all 4 million values.

---

First 55 values

val = (100003 - 200003 * k + 300007 * k**3) % 1_000_000

Implements the exact formula from the statement.

Then:

s[k - 1] = val - 500000

shifts the range to negative/positive integers.

---

Recursive generation

val = (s[k - 24] + s[k - 55] + 1_000_000) % 1_000_000

implements the Lagged Fibonacci recurrence.

---

Kadane’s algorithm

current = max(x, current + x)

Either:

• extend the previous segment,
• or begin a new one at $x$.

---

Direction scans

Horizontal

Each row is already a list.

---

Vertical

col = [grid[r][c] for r in range(SIZE)]

extracts a column.

---

Diagonals

We traverse all diagonals starting from:

• top row,
• left column.

Similarly for anti-diagonals.

This guarantees every possible contiguous directional line is checked exactly once.

---

Verification on the small example

For the $4 \times 4$ sample:

$$\begin{matrix} -2 & 5 & 3 & 2 \ 9 & -6 & 5 & 1 \ 3 & 2 & 7 & 3 \ -1 & 8 & -4 & 8 \end{matrix}$$

Kadane correctly finds:

$$8 + 7 + 1 = 16$$

matching the problem statement.

---

Final Verification

• The algorithm runs in essentially linear time over the grid.
• Memory usage is reasonable.
• The computed Project Euler value is known and consistent with independent implementations.

Answer: 52852124