# Does Langton's ant cover every n by 6 gridded torus?

This post follows this other post about times cover by Langton's ant of $n$ by $n$ gridded torus.

For $n$ by $n$ gridded torus, I've checked for $n \le 1000$ that the ant covers all. This fact needs to be proved for every $n$, but this should be not surprising.

Contrariwise, we can easily checked that for the $n$ by $2$ gridded torus and $n \ge 3$, the ant enters into a cycle before covering the torus: Idem for the $n$ by $4$ gridded torus and $n \ge 5$: Now for $n$ by $6$ (with $n \ge 5$) there is a problem.
For $n=50$, it is not yet covered after around $10^4$ steps: and it is not yet covered after around $10^5$ steps: in fact I've checked that it's also not covered after $10^7$ steps.

So there are two possibilities:

• for $n$ by $6$ gridded torus, the covering needs a long time, but finite (checked for $n \in [5, 60]$).
• $\exists n_0$ such that the ant covers $n_0$ by $6$ but not $n$ by $6$ for $n > n_0$.

Question: Does Langton's ant cover every n by 6 gridded torus ($n \ge 5$)?
[If yes, what's the asymptotic of the covering time? Else, what's $n_0$?]

If no: i.e. if the ant enters into a cyclic pattern of width $n_0$ then we need a priori to go at least up to the step $4 \cdot 6 \cdot n_0 \cdot 2^{6 \cdot n_0}$ for checking that, which could become out of computation.

If yes: let $s^m_n$ be the number of steps Langton's ant needs for covering the $n$ by $m$ torus.

$\scriptsize{ \begin{array}{c|c} n &10&20&30&40&50&60&70&80 \newline \hline s^6_n &977&17623&87113&3135267&19563171&331665879&4738404219&44105120036 \newline \hline s^n_6 &240&6708&166542&2027581&32781038&220780386&4820615241&76325278885 \newline \hline n/ln(s^6_n) &1.45&2.04&2.6373&2.6741&2.9781&3.0581&3.1419&3.2639 \newline \hline n/ln(s^n_6) &1.82&2.26&2.4952&2.7543&2.8892&3.1229&3.1395 &3.1925 \end{array} }$

This new data (sage computation) suggests that: $s^6_n \sim s^n_6 \sim e^{n/c}$, with $c \sim 3$.

Remark: we can checked that there is no such a problem for the $n$ by $3$ or $5$ or $7$ $\dots$ gridded torus, but there is the same problem for the $n$ by $8$ or $10$ or $12$ $\dots$ gridded torus (at least up to $18$).

The pictures was computed online on http://www.turnerbohlen.com/langtonsant/

• Where does 4.6 come from (in your upper remark)? $\;$ – user5810 Mar 13 '15 at 7:05
• @RickyDemer: for $n_0$ by $6$ there are $6n_0$ squares and each square can have two states (black or white) so we get $2^{6n_0}$. Next about the position of the ant we have to multiply by $6n_0$, and about its state (up, down, left or right), we have to multiply by $4$. So finally, we get $4.6n_0.2^{6n_0}$. – Sebastien Palcoux Mar 13 '15 at 7:12
• I'm not sure how much this would help, but one could try splitting the grid into congruent pieces and computing a lookup table with [after_colors,exit_edge] for each possible [entry_edge,before_colors]. $\:$ (Such a table could presumably be compressed, and might reveal that some a-priori-possible color configurations of the pieces are not actually possible.) $\;\;\;\;$ – user5810 Mar 13 '15 at 7:40
• Since this torus has a different shape, initial orientation matters. Did you check for both orientations? and are the numbers the same? – The Masked Avenger Mar 13 '15 at 15:51
• Following up on Ricky Demer's suggestion, it seems natural to me to replace the current system with a slightly more complicated one: for n=6, have a six-square ring replaced by a number in [0,63], with 144 combinations possible for entry and exit points, of which only 48 are used. Although this only halves the number of steps, using this representation may allow some number theoretical analysis to show how quickly certain configurations are reached. Gerhard "Also Has Small Transition Table" Paseman, 2015.03.13 – Gerhard Paseman Mar 13 '15 at 18:26