Project Euler Problem 349

Solution

Answer: 115384615384614952

The key to this problem is that although the ant’s motion initially looks chaotic, Langton’s ant eventually enters a perfectly repeating “highway” pattern. Once this happens, the number of black squares grows linearly, allowing us to jump from a few thousand simulated steps all the way to $10^{18}$.

1. Mathematical analysis

Let $B(n)$ be the number of black squares after $n$ moves.

The ant obeys:

On white: flip to black, turn right, move.
On black: flip to white, turn left, move.

The grid starts entirely white.

Step 1: Observe emergent structure

A direct simulation for $10^{18}$ steps is impossible.

However, Langton’s ant is famous for a deep phenomenon:

After a chaotic transient phase, it eventually builds a repeating “highway”.

Empirically (and verifiably by simulation), the ant enters a periodic regime after 9977 moves.

In this regime:

every 104 moves,
the configuration repeats up to translation,
and the number of black squares increases by exactly 12.

So for sufficiently large $n$,

$$B(n+104)=B(n)+12.$$

This gives a linear recurrence.

Step 2: Determine the transition point

Simulating the first few thousand moves shows:

$$B(9977)=715.$$

After that,

$$B(n+104)=B(n)+12.$$

Now write

$$10^{18}-9977 = 104q + r.$$

Compute:

$$q = \left\lfloor \frac{10^{18}-9977}{104}\right\rfloor, \qquad r=(10^{18}-9977)\bmod 104.$$

Then

$$B(10^{18}) = 715 + 12q + \bigl(B(9977+r)-715\bigr).$$

The remainder $r$ is handled by the stored values from the first simulated cycle.

Carrying this out yields:

$$B(10^{18}) = 115384615384614952.$$

2. Python implementation

def solve():
    N = 10**18

    # Directions: up, right, down, left
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    black = set()

    x = y = 0
    direction = 0  # start facing up

    black_counts = []

    # Simulate enough steps to reach stable highway behavior
    LIMIT = 20000

    for step in range(1, LIMIT + 1):

        if (x, y) in black:
            # Black square: flip to white, turn left
            black.remove((x, y))
            direction = (direction - 1) % 4
        else:
            # White square: flip to black, turn right
            black.add((x, y))
            direction = (direction + 1) % 4

        # Move forward
        dx, dy = directions[direction]
        x += dx
        y += dy

        black_counts.append(len(black))

    # Highway begins after 9977 moves
    START = 9977
    PERIOD = 104
    GAIN = 12

    base = black_counts[START - 1]

    q, r = divmod(N - START, PERIOD)

    answer = base + q * GAIN

    if r:
        answer += black_counts[START + r - 1] - base

    return answer

print(solve())

3. Code walkthrough

Simulation

We represent black squares with a set.

If current square is black:
remove from set (turn white),
rotate left.
Otherwise:
add to set (turn black),
rotate right.

Then move one step in the new direction.

We record:

black_counts.append(len(black))

so black_counts[n-1] stores $B(n)$.

Detecting periodicity

By inspection:

from move 9977 onward,
every 104 steps,
black count increases by 12.

Thus:

START = 9977
PERIOD = 104
GAIN = 12

We split the huge number of moves into:

q, r = divmod(N - START, PERIOD)

meaning:

q complete highway cycles,
r leftover moves.

Each cycle contributes +12 black squares.

4. Final verification

Sanity check:

$$\frac{12}{104}=\frac{3}{26}\approx 0.11538$$

So for $10^{18}$ steps we expect roughly

$$0.11538 \times 10^{18} \approx 1.1538\times10^{17},$$

which matches the magnitude of the computed result:

$$115384615384614952.$$

The number is also consistent with the known stable linear growth of Langton’s ant.

Answer: 115384615384614952