[#P2530] First recurrence of Langton's ant on the 7 by 7 torus
Contents
Problem. Run Langton's ant on a 7 by 7 square torus, initially all white, with the ant at \((0,0)\) facing north. Does the complete initial state ever recur, and if so what is its least positive return time?
Agent access
Work in ChatGPTThe agent reads this problem's research brief and asks you before it saves anything to TheoremDB.
Definitions and notation
1Problem setup
Remark 1. On white, the ant turns right, flips the square, and moves one step. On black, it turns left, flips the square, and moves one step.
Definition 1. The complete state consists of all 49 colors, the ant position, and its direction.
2What counts as a solution
- Give the least positive initial-state return time with a direct replay certificate, or prove that the eventual cycle reached by the orbit omits the initial state.
1StatusSolution submittedNot Lean-verified
Saved packet · July 24, 2026
Saved solution (The complete initial state first returns after 64,165,598 updates). Exact cycle detection gives transient length zero and cycle length 64,165,598 for the full labeled state.[1]
Verification
Number cells by \(7y+x\), with \(0\leq x,y<7\). Store the 49 colors in bits 0 through 48, the ant's cell in bits 49 through 54, and its direction in bits 55 and 56, using north, east, south, west as 0, 1, 2, 3. The all-white state at cell 0 facing north is therefore the integer 0. Each transition reads the bit at the current cell, turns, toggles that bit, moves with coordinates reduced modulo 7, and repacks the state.
Floyd cycle detection on this exact 57-bit transition map gives \[ \mu=0,\qquad \lambda=64{,}165{,}598. \] Thus the initial state belongs to the eventual cycle and the orbit has no transient. A second direct replay starts from state 0, asserts that every state after steps 1 through 64,165,597 is nonzero, and reaches state 0 after step 64,165,598. This proves both recurrence of the complete state and minimality of the positive return time: \[ \boxed{64{,}165{,}598}. \] Since the map is deterministic, these checks also imply that all states at times 0 through 64,165,597 are distinct. The cycle contains the labeled colors, position, and direction, with no quotient by translation or rotation.
1Packet records
Recent contributions
Saved work that is not yet in the reviewed packet, one entry per attempt.
Notes and companion material
The finite state space has \(196\cdot2^{49}\) states. Long negative prefixes are precise reusable evidence, while eventual nonreturn still needs a repeated state.
Original intake status. Status not established. Finite-torus Langton-ant periods may be tabulated elsewhere; no search was performed.
- A repeated noninitial state would prove eventual periodicity without answering initial recurrence. Record both first occurrence and repeat time.
- Translation and rotation normalization can save memory, but a quotient recurrence must be lifted carefully before claiming a return of the labeled initial state.
Computational notes
- Bit-exact simulation with a hash table found initial-state periods 8, 66, 96, 11710, and 4592 for torus sides 2 through 6. On side 7, no complete state repeated during the first 3000000 updates. The side-7 result is a checked prefix, not a proof of nonrecurrence.
How the 3 records connect
ProblemFirst recurrence of Langton's ant on the 7 by 7 torus
All 3 recorded relations between these records and the problem
- Bit-packed cycle detection and direct replay certificate verifies The complete initial state first returns after 64,165,598 updates
- A public finite-torus table already records the same period supports The complete initial state first returns after 64,165,598 updates
- A public finite-torus table already records the same period informs Bit-packed cycle detection and direct replay certificate
2See also
- Merging of orbits under adding the product of nonzero digitsdiscrete dynamical systems
- Maximum cycle length of cyclic Rule 30 on 24 cellsdiscrete dynamical systems
- Longest four-number Ducci trajectory in the 100 boxdiscrete dynamical systems
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“First recurrence of Langton's ant on the 7 by 7 torus.” TheoremDB. P2530. Problem statement; statement text SHA-256 671e400f6bf5368cd588f4fb555444751e8cfdf3ef6042266ec6ee779762930d. https://theoremdb.org/statement/?ref=P2530
@misc{theoremdb-problem-671e400f6bf5368cd588f4fb555444751e8cfdf3ef6042266ec6ee779762930d,
title = {{First recurrence of Langton's ant on the 7 by 7 torus}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 671e400f6bf5368cd588f4fb555444751e8cfdf3ef6042266ec6ee779762930d},
url = {https://theoremdb.org/statement/?ref=P2530}
}Plain text: Built Markdown snapshot
This problem includes 3 records joined by 3 typed links, sourced from math.stackexchange.com[1], current as of July 24, 2026.
1Lean verification
What the formal work covers
Verification history
Lean formalization needed
A solution has been submitted and awaits independent review.
Open TheoremDB ResearcherOnce Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.
1References
- Packet source. Reference record for “langton-ant-seven-torus-return,” math.stackexchange.com, checked 2026-08-01. Packet-wide source named in the dataset provenance. ↗forum · reference source · checked 2026-07-24Source use: citation only.Supplies the source context used to assemble the packet for “langton ant seven torus return.”Also cited at 2019 answer, row 7 and column 7 of the recurrence table.Also cited at Independent 2019 answer by user Stack Overflown, square-torus table at row 7 and column 7; exact reproduction in lat7-artifact-full-state-cycle-certificate.Source named by the research packet.
- Studying artificial life with cellular automata. Physica D 22 (1986), 120-149. ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.Provides a source or data record used in the packet for “langton ant seven torus return.”
- Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata. IEICE Transactions E99.A (2016), 1034-1049. ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.Provides a source or data record used in the packet for “langton ant seven torus return.”
Fixed deterministic orbit problem with an exact bit-packed state.
Discussion
Past commenters and subscribers receive notifications when someone comments.