TheoremDB
All problems

[#P2530] First recurrence of Langton's ant on the 7 by 7 torus

Qualification pending

This question is undergoing qualification review.

Not Lean-verified
View the submitted solution
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 accessWork in ChatGPT

The 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.

1Status

Saved packet · July 24, 2026

What counts as a solution

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

3 records

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
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemFirst recurrence of Langton's ant on the 7 by 7 torus

All 3 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“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
BibTeX
@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}
}

This problem includes 3 records joined by 3 typed links, sourced from math.stackexchange.com[1], current as of July 24, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once 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

  1. 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.
  2. 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.”
  3. 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

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.