Problem 349: Langton's Ant

Detailed mathematical approach

Problem Summary

An ant walks on a regular grid of black and white squares, always facing one of the four cardinal directions. At every move it looks at the square it occupies:

• on a black square it flips the colour to white, rotates \(90\) degrees counterclockwise and moves forward one square;
• on a white square it flips the colour to black, rotates \(90\) degrees clockwise and moves forward one square.

Starting from a grid that is entirely white, we must say how many squares are black after \(10^{18}\) moves. ^[1] This is Langton's ant, a Turing machine whose tape is the plane: one ant can compute any Boolean circuit. ^[4] The statement gives no intermediate values, so the program must supply its own checkpoints.

The whole solution in one sentence: simulate the first few hundred thousand moves, check that from move \(9977\) each block of \(104\) moves reproduces the ant's own future shifted two squares along a diagonal and adds \(12\) black squares, then count whole blocks up to \(10^{18}\).

Mathematical Approach

1. Notation, and why the count is cheap to follow

Let \(c_t(z)\in\{0,1\}\) be the colour of the square \(z\in\mathbb Z^2\) after \(t\) moves, with \(1\) for black; let \(a_t\) be the ant's square and \(d_t\) its direction, with up, right, down and left numbered \(0,1,2,3\), so that \(d+1\) is a clockwise quarter turn. The quantity asked for is

$$B(t)=\sum_{z\in\mathbb Z^2}c_t(z),$$

a finite sum, since at most \(t\) squares have been touched. Both rules collapse into

$$\begin{aligned} d_{t+1}&\equiv d_t+1-2c_t(a_t)\pmod 4,\\ c_{t+1}(a_t)&=1-c_t(a_t), \end{aligned}$$

with \(a_{t+1}=a_t+e(d_{t+1})\), where \(e(0),\dots,e(3)\) are the four unit steps. The second formula is why the problem is tractable: a move repaints exactly one square, so

$$B(t+1)-B(t)=1-2c_t(a_t)\in\{+1,-1\}.$$

Two consequences follow at once. The full history \(B(0),B(1),\dots\) costs one addition per move beyond the simulation itself; and \(B(t)\equiv t\pmod 2\), so the requested count is even.

2. The first moves by hand

Put the ant at the origin facing up. Move \(1\) reads the white square \((0,0)\), paints it black, turns clockwise to "right" and lands on \((1,0)\). Moves \(2\), \(3\) and \(4\) repeat this on three fresh white squares, turning clockwise each time, so the ant circles back to \((0,0)\) facing up, leaving \((0,0)\), \((1,0)\), \((1,-1)\), \((0,-1)\) black: fresh white ground makes the ant turn in a loop.

Move \(5\) is the first to meet a black square: it reads \((0,0)\), turns counterclockwise to "left", repaints it white and steps to \((-1,0)\), so the count drops. Running the rules gives

$$B(0),\dots,B(10)=0,1,2,3,4,3,4,5,6,7,6,$$

so \(B(10)=6\), and after eight moves the ant is again at the origin, facing down, with six black squares. These values match the terms recorded in the OEIS; ^[3] of them the C++ program checks only \(B(10)=6\). Two further values are \(B(100)=20\) and \(B(1000)=118\). A quarter turn of the plane maps one run onto another, so the starting direction does not matter.

3. The three phases of the walk

At a billion moves per second, \(10^{18}\) moves would take about \(32\) years, so structure in \(B(t)\) must replace the missing moves. From an all-white grid the walk has three visible regimes. ^{[2] [4]} For roughly \(500\) moves the picture stays small and nearly symmetric, as in Section 2; then a pseudo-random stretch of about ten thousand moves grows a large irregular blot; finally the ant starts building a straight diagonal highway that it extends forever.

What is proved here should be said plainly. That the trajectory is unbounded for every starting configuration is a theorem of Bunimovich and Troubetzkoy, often called the Cohen–Kong theorem. ^[2] That the highway always appears is only a conjecture, and even then only for configurations with finitely many black squares. ^[4] That gap does not matter here: this highway can be exhibited and then verified.

4. The self-reproduction lemma

The configuration does not repeat in place: the irregular blot stays where it is while every period of the highway adds black squares further out along the diagonal. What repeats is the picture up to translation, and only on the region the ant will still use — and since translation does not change a count of squares, that is enough to force \(B\) to grow by a fixed amount per period.

Set \(t_0=9977\), \(p=104\) and \(v=(-2,-2)\). Let \(V\) hold the squares the next \(p\) moves read and repaint, each before its forward step,

$$V=\{a_{t_0+j}:0\le j\lt p\},$$

and let

$$W=\bigcup_{m\ge0}\,(V+mv)$$

be the corridor swept out by all future copies of \(V\), so that \(W+v\subseteq W\). One finite computation establishes two facts:

• (A) \(a_{t_0+p}=a_{t_0}+v\) and \(d_{t_0+p}=d_{t_0}\): the ant moves from \((-15,10)\) to \((-17,8)\) and faces left both times.
• (B) \(c_{t_0+p}(z+v)=c_{t_0}(z)\) for every square \(z\in W\).

Theorem. If (A) and (B) hold, then for every \(k\ge0\) and every \(0\le j\le p\),

$$B(t_0+kp+j)=B(t_0+j)+k\,\Delta,$$

where \(\Delta=B(t_0+p)-B(t_0)\).

Proof. Let \(H(k)\) say that \(a_{t_0+kp}=a_{t_0}+kv\), that \(d_{t_0+kp}=d_{t_0}\), and that \(c_{t_0+kp}(z+kv)=c_{t_0}(z)\) for all \(z\in W\). Then \(H(0)\) is trivial and \(H(1)\) is exactly (A) and (B). Assume \(H(k)\). The ant starts the next \(p\) moves at \(a_{t_0}+kv\) facing as it did at \(t_0\), and the squares it would occupy if it repeated its earlier walk lie in \(V+kv\subseteq W\); by \(H(k)\) their colours equal those read during the moves \(t_0+1,\dots,t_0+p\). As the rules depend on nothing else, an induction on the move inside the period shows these \(p\) moves are the \(kv\)-translate of the earlier ones. The direction therefore returns to \(d_{t_0}\), the ant ends at \(a_{t_0}+(k+1)v\), and the increments \(1-2c\) repeat, giving the displayed formula.

To carry \(H\) forward, take \(z\in W\); then \(z+v\in W\) too. Period \(k+1\) repaints the \(kv\)-translate of what period \(1\) repainted, and by \(H(k)\) the square \((z+v)+kv\) enters it with the colour \(z+v\) had at time \(t_0\). So it leaves with the colour \(z+v\) had at time \(t_0+p\):

$$\begin{aligned} c_{t_0+(k+1)p}\bigl(z+(k+1)v\bigr)&=c_{t_0+p}(z+v)\\ &=c_{t_0}(z) \end{aligned}$$

by (B). This is \(H(k+1)\), and the induction closes. \(\square\)

5. Why (B) is only finitely many checks

The corridor \(W\) is infinite, yet (B) is settled in a moment. Let \(S\) be the \(1398\) squares repainted up to time \(t_0+p\); outside \(S\) every square is still white, and \(|V|=40\). Which translates meet \(S\) is decided by subtraction: \(s=u+mv\) means \(s-u=(-2m,-2m)\), so a pair \((u,s)\) admits at most one \(m\ge0\), and all \(40\cdot1398\) pairs leave only \(m=0,1,2\). So for \(m\ge3\) both \(z\in V+mv\) and \(z+v\) lie outside \(S\), both sides of (B) are white, and the equality is automatic; checking (B) on the \(128\) squares of \(V\cup(V+v)\cup\dots\cup(V+4v)\) settles it everywhere. That check reports no mismatch, and (A) holds as stated.

6. The bookkeeping of one period

Those \(104\) moves visit only \(40\) distinct squares, some repeatedly. Of the \(104\) repaintings, \(58\) turn a white square black and \(46\) turn a black square white, so

$$\Delta=58-46=12,$$

matching \(B(t_0)=715\) and \(B(t_0+p)=727\). Growth is thus \(12/104=3/26\approx0.1154\) black squares per move in the long run; at \(t=200\,000\) the ratio \(B(t)/t\) is already \(0.1132\). It is not monotone inside a period: against \(B(t_0)\) the count dips to \(-2\) before settling at \(+12\).

7. Reaching \(10^{18}\)

With \(t_0=9977\), \(p=104\) and \(\Delta=12\) in hand, write a target \(T\ge t_0\) as

$$\begin{aligned} T&=t_0+qp+r,\qquad 0\le r\lt p,\\ q&=\Bigl\lfloor\frac{T-t_0}{p}\Bigr\rfloor, \end{aligned}$$

so that Section 4 gives

$$B(T)=B(t_0+r)+q\,\Delta.$$

The right-hand side is one table lookup inside the simulated range and one multiplication. Take \(T=11\,000\): here \(T-t_0=1023=9\cdot104+87\), so \(q=9\) and \(r=87\); the table gives \(B(10\,064)=726\), and \(726+9\cdot12=834\), which is \(B(11\,000)\) as simulated. For \(T=10^{18}\) the term \(q\Delta\) is of order \(10^{17}\), well inside the signed 64-bit range, whose limit is about \(9.2\cdot10^{18}\); and since \(p\) and \(\Delta\) are both even, the parity rule of Section 1 is respected.

8. Finding \(t_0\), \(p\) and \(\Delta\) from the data

The programs do not hard-code the triple; they estimate it. Simulate \(T_0=200\,000\) moves, keep the history, and for each candidate period \(p\) from \(1\) to \(p_{\max}=500\) set

$$\Delta_p=B(T_0)-B(T_0-p)$$

and test whether \(B(t+p)-B(t)=\Delta_p\) holds throughout the trailing window \(T_0-W\le t\le T_0-p\), with \(W=50\,000\). If it does, find the smallest \(s\) for which the relation holds for all \(t\) from \(s\) to \(T_0-p\), and report \((s,p,\Delta_p)\).

Both thresholds are generous. The first period to survive the window test is \(p=104\); the only others below \(500\) are its multiples \(208\), \(312\) and \(416\), and the scan runs upwards, so the smallest is returned. The window \(150\,000\le t\le199\,896\) lies wholly inside the highway phase, since \(B(t+104)=B(t)+12\) holds for every \(t\) from \(9977\) on. The relation fails at \(t=9976\), where the difference is \(10\), and at \(8899\) values of \(t\) altogether, every one below \(9977\). So \(s=9977\), as the OEIS entry records. ^[3]

This detection extrapolates from a finite table, which by itself is only a very strong regularity; what turns it into a proof is Section 4, applied to the triple returned.

How the Code Works

All three programs run the same three stages, matching Sections 1, 8 and 7 in that order. ^[6]

simulate_black_counts (Java simulateBlackCounts, inline in the Python) implements Section 1. Only the black squares are stored: a std::unordered_set of 64-bit keys in C++, a HashSet<Long> in Java, a set of tuples in Python. encode_cell packs a square into one key by reinterpreting each coordinate as uint32 and putting \(x\) in the high \(32\) bits; Java's encodeCell widens \(x\) before the shift and masks \(y\) with 0xFFFFFFFFL. Toggling a square is an insert or an erase, with the count adjusted by \(\pm1\) in the same branch, so counts[step] records \(B\) for free. The turn is (direction + 1) & 3 on white and (direction + 3) & 3 on black, the congruence of Section 1, with the step read from dx, dy. The 32-bit coordinates are ample: in \(200\,000\) moves the ant never leaves \(|x|\le3672\), \(|y|\le3650\).

detect_linear_pattern (Java detectLinearPattern) implements Section 8, window test first; the Python does this stage inside solve. For a period that survives, C++ and Java fill a byte array good[t] marking the \(t\) that satisfy the relation, then a backward scan builds suffix_ok, so the earliest valid start costs one pass instead of one pass per candidate start. The Python keeps the plain nested loop, whose inner loop stops at each candidate's first violation: with the shipped constants its earliest-start search evaluates \(202\,102\) conditions, although on an arbitrary history the same loop is \(O(T_0^2)\).

extrapolate_black_count (Java extrapolateBlackCount) implements Section 7, returning the tabulated value directly when the target lies inside the simulated range. C++ forms cycles * delta in __int128; Java uses long, which the bound of Section 7 justifies; Python's integers are unbounded. The C++ file alone adds an Options block parsed by parse_arguments, so the four constants can be set on the command line, and --skip-checkpoints turns its run_checkpoints off. If no period is found, C++ throws std::runtime_error and Java a RuntimeException; the Python has no such guard and would fail unpacking an empty result, which with the shipped constants never happens.

Complexity and Verification

With well-spread hashes the simulation takes \(O(T_0)\) expected time — an assumption that is strained in Java, where a Long's hash code is the exclusive OR of the two halves of its value, here \(x\oplus y\), which the diagonal highway makes repeat: at move \(200\,000\) the \(22\,640\) keys share only \(219\) distinct hash codes. Current OpenJDK turns such a crowded bucket into a balanced tree of comparable keys, so \(O(T_0\log T_0)\) is the safe bound there; only the time suffers, never the result. ^[5]

Memory is \(O(T_0)\): the C++ and Java histories hold \(200\,001\) 64-bit values, about \(1.6\) MB, the Python list holds references to integer objects and takes more, detection adds two byte arrays of length \(T_0\) in C++ and Java, and the hash containers carry their own overhead. The black squares peak at \(22\,641\), out of \(41\,572\) distinct squares repainted on the way. The window tests use at most \(p_{\max}W=2.5\cdot10^7\) comparisons, though a wrong period is usually rejected at once. Raising the target beyond the simulated range adds neither simulation nor search, so all three programs finish in well under a tenth of a second; with checkpoints on, C++ simulates \(200\) moves and then \(200\,000\) moves twice.

The C++ run_checkpoints tests two things before the main computation: that \(B(10)=6\), and that the detector applied to \(200\,000\) moves returns period \(104\) and \(\Delta=12\). Its third comparison calls extrapolate_black_count at step \(150\,000\), but that step lies inside the stored history, so the function returns the stored entry and the test compares it with itself: the extrapolation arithmetic is never exercised, and no published check inspects the configuration, which is what makes the jump to \(10^{18}\) a proof. The two real tests were re-checked here, along with the following.

• \(B(0),\dots,B(10)\) by hand and by code, and \(B(0),\dots,B(24)\) by code against the \(25\) terms the OEIS entry lists; ^[3] also \(B(100)=20\), \(B(1000)=118\), \(B(9977)=715\), \(B(200\,000)=22\,640\), and \(B(t)\equiv t\pmod2\) throughout.
• \(B(t+104)-B(t)=12\) for every \(9977\le t\le199\,896\), while \(B(10\,080)-B(9976)=10\), so \(9977\) is exactly the earliest start; and the formula of Section 7 against every stored count from \(9977\) to \(200\,000\), including \(B(11\,000)=834\).
• The self-reproduction check of Sections 4 and 5: \(v=(-2,-2)\), direction preserved, no mismatch among the \(128\) squares, and the \(104\) increments of the second period identical to those of the first.
• The C++, Python and Java programs print the same value.

The gap the published checks leave is cheap to close: the configuration check of Section 5 costs one period of simulation and a few hundred lookups.

Footnotes and References

The references below supply the background facts used above; the self-reproduction lemma, its proof and the reduction of (B) to \(128\) squares are derived here.

1. Project Euler 349 — Langton's Ant. The official statement gives the two turn-and-flip rules used above, asks how many squares of an initially all-white grid are black after 10¹⁸ moves, and supplies no intermediate checkpoints.
2. Wikipedia — Langton's ant. The article says the ant follows a pseudo-random path until step 9,977 and then builds a recurrent highway pattern of 104 steps that repeats indefinitely, and that the trajectory is unbounded for every initial configuration, a result attributed to Bunimovich and Troubetzkoy (1992) and called the Cohen–Kong theorem.
3. OEIS A255938 — black cells after n moves of Langton's ant. The entry lists 0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 6, 7, 8, 9, 10, 9, 8, 7, 6, 7, 6, 7, 8, 9, 10, matching the values computed here, and records a(n+104) = a(n) + 12 for n greater than 9976, the relation proved in Sections 4 and 5.
4. A. Gajardo, A. Moreira and E. Goles, Complexity of Langton's Ant, Discrete Applied Mathematics 117 (2002) 41–50. One ant's trajectory is made to compute any Boolean circuit, so the system is P-hard and universal. The introduction calls the walk roughly symmetric for the first 500 steps, then seemingly random for about 10,000 steps, after which the ant suddenly builds an infinite diagonal highway, a periodic motion with drift. It states that for any initial configuration the trajectory is unbounded, and Section 1.2 gives only as a conjecture that from any configuration with finite support the highway eventually appears.
5. cppreference — std::unordered_set sorts elements into hash buckets and gives search, insertion and removal average constant-time complexity; Java — HashSet promises the same provided the hash disperses the elements properly among the buckets, Java — Long.hashCode defines that hash as the exclusive OR of the two halves of the value, and OpenJDK JEP 180 turns a bucket holding too many comparable keys into a balanced tree, improving the collision-heavy case from linear to logarithmic. Python — set types documents the Python version's hashed set.
6. C++ — Euler349.cpp. The linked immutable C++ revision contains simulate_black_counts, detect_linear_pattern, extrapolate_black_count and the checkpoints described above. It is the implementation record for this article.