Langton's ant is a cellular automaton running as follows:

Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to the rules below:

- At a white square, turn 90° right, flip the color of the square, move forward one unit
- At a black square, turn 90° left, flip the color of the square, move forward one unit

We consider Langton's ant on a torus $n$ by $n$ gridded such that all the squares are white.

**Preliminary question**: Is it true that Langton's ant will visit every square, for all $n$?

*Remark*: I've checked it's true for $n \le 1000$. In fact Langton's ant could enter into a local cycle without having visiting every square (see here), so the fact that such phenomena can't appear must be proved.

If so, let $s_n$ be the number of steps Langton's ant needs for visiting all the squares.

**Question**: what's the asymptotic of $s_n$?

$\small{ \begin{array}{c|c} n &2&3& 4& 5& 6& 7& 8& 9& 10& 50 & 100 & 500 \newline \hline s_n &3&12&41&62&166&113&318&281&692&57672 & 225905 & 12740527 \end{array} } $

*Remark*: Following the table above, this asymptotic seems to be $\frac{4}{\pi}(nln(n))^2$, as for the random walk.

$\small{ \begin{array}{c|c} n &1000&2000 & 5000 &6000& 10000& 11000 & 12000 & 13000 & 14000 \newline \hline \frac{4(nln(n))^2}{s_n} &2.919&2.196&2.177&1.770&1.506&2.067&1.734&1.502&1.911 \end{array} } $

*Remark*: This new data suggests that there is no asymptotic, because for $n$ large $\frac{4(nln(n))^2}{s_n}$ seems bounded in $[1,4]$ but not convergent.

For $n=50$ and the ant starting "up" at position $(25,25)$, the grid looks as follows at step $s_n$:

Now by encoding square's color by how many times it was visited (no effect on the rules) we get:

And for $n=500$ at step $s_n = 12740527$:

These pictures was computed online at http://www.turnerbohlen.com/langtonsant/

And for $n=5000$ at step $s_n = 3331448985$:

For comparison, this last picture was generated from a *uniform random walk* for $n=5000$ (covered after $2410514205$ steps):

These two last pictures were computed by Sage, with this code.

8more comments