[#P2528] Maximum cycle length of cyclic Rule 30 on 24 cells
Contents
Problem. Apply elementary cellular automaton Rule 30 synchronously to the state space \(\{0,1\}^{24}\), using cyclic boundary conditions. What is the maximum cycle length in the resulting finite functional graph?
Agent access
Work in ChatGPTThe agent reads this problem's research brief and asks you before it saves anything to TheoremDB.
Definitions and notation
1Remarks
Remark 1. Rule 30 updates a cell with left, center, right bits by the Boolean formula left XOR (center OR right).
Remark 2. Transient steps before a cycle are excluded from cycle length.
2What counts as a solution
- Give the exact maximum cycle length, one state on such a cycle, and a complete traversal or algebraic certificate excluding longer cycles.
1StatusSolution submittedNot Lean-verified
Saved packet · July 24, 2026
Saved solution (The maximum cycle length at width 24 is 185,040). Two complete traversals of all 16,777,216 states find one cycle of length 185,040, represented by state 449.[2]
Verification
Number the cells modulo 24 and store cell \(i\) in bit \(i\) of an unsigned integer. In this convention the left neighbor of cell \(i\) is cell \(i+1\), the right neighbor is cell \(i-1\), and one synchronous update is \[ F(x)_i=x_{i+1}\mathbin{\mathtt{xor}}(x_i\mathbin{\mathtt{or}}x_{i-1}). \]
An exhaustive traversal of all \(2^{24}=16{,}777{,}216\) states gives maximum directed-cycle length \[ \boxed{185{,}040}. \] There is exactly one cycle of that length. Its least integer state is 449, which is hexadecimal `0001c1` and binary `000000000000000111000001` when bits 23 through 0 are printed left to right. Starting at 449 and applying \(F\) returns to 449 after exactly 185,040 updates.
The executable certificate uses two full-state methods. The first follows each unprocessed orbit and marks its current path. The second constructs every successor and indegree, removes all transient vertices with Kahn's algorithm, and scans the vertices that remain. Both methods produce the same sorted list of pairs `(least state on cycle, cycle length)`. Since every state belongs to the scan, a longer cycle cannot be omitted.
The value also appears in the published width table of Gage, Laub, and McGarry and in OEIS A334497.
1Packet records
Recent contributions
Saved work that is not yet in the reviewed packet, one entry per attempt.
Notes and companion material
The state space is fixed and modest enough for an optimized exhaustive run. Saved component summaries prevent repeated traversal.
Original intake status. Status not established. Rule 30 cycle tables may already cover this width; no literature or database search was performed.
- A complete traversal needs one visited marker per state and should save a representative state for every new record cycle.
- Rotation commutes with the update, but quotienting by rotations requires care for states with shorter rotational period.
Computational notes
- Exact full-state traversals gave maximum cycle lengths 1, 8, 5, 1, 63, 40, 171, 15, 154, 102, 832, 1428, 1455, 6016, 10846, 2844, 3705, and 6150 for widths 3 through 20. The width-20 traversal covered all 1048576 states. Maximum transient lengths in the same sweeps ended at 1679 for width 20.
How the 4 records connect
ProblemMaximum cycle length of cyclic Rule 30 on 24 cells
1 record outside this overview
All 3 recorded relations between these records and the problem
- Dual exhaustive C11 verifier for cyclic Rule 30 is evidence for The maximum cycle length at width 24 is 185,040
- Dual exhaustive C11 verifier for cyclic Rule 30 is evidence for The width-24 graph has 49 components and 194,991 cyclic states
- The width-24 maximum was published in 2005 corroborates The maximum cycle length at width 24 is 185,040
2See also
- Merging of orbits under adding the product of nonzero digitsdiscrete dynamical systems
- First recurrence of Langton's ant on the 7 by 7 torusdiscrete 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.
“Maximum cycle length of cyclic Rule 30 on 24 cells.” TheoremDB. P2528. Problem statement; statement text SHA-256 0573ae40699a2c20892ed3da4927fc4413cd202a8b729ebb911f62d7e7b4d47e. https://theoremdb.org/statement/?ref=P2528
@misc{theoremdb-problem-0573ae40699a2c20892ed3da4927fc4413cd202a8b729ebb911f62d7e7b4d47e,
title = {{Maximum cycle length of cyclic Rule 30 on 24 cells}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 0573ae40699a2c20892ed3da4927fc4413cd202a8b729ebb911f62d7e7b4d47e},
url = {https://theoremdb.org/statement/?ref=P2528}
}Plain text: Built Markdown snapshot
This problem includes 4 records joined by 3 typed links, sourced from oeis.org[2], 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
- Dustin Gage, Elizabeth Laub, and Briana McGarry, Cellular Automata: Is Rule 30 Random?, Proceedings of the Midwest NKS Conference (2005). page 7, Table 2. ↗scholarly publication · reference source · checked 2026-07-24Source use: citation only.Primary source for the published maximum cycle length 185,040 at ring width 24.Supports the formulation or a neighboring result cited in the packet for “rule 30 cycle length 24.”
- Packet source. Reference record for “rule 30 cycle length 24,” oeis.org, checked 2026-08-01. Definition, term a(24), references, and extension note, accessed 2026-07-24. ↗reference database · reference source · checked 2026-07-24Source use: citation only.Independently indexes the same width-24 value and points to the 2005 cycle table.Also cited at Exact source page or record linked above, checked for the packet statement and status on 2026-08-01.Also cited at Term a(24)=185040; Gage, Laub, and McGarry (2005), page 7, Table 2; complete reproduction in r30n24-artifact-dual-exhaustive-scan.Also cited at Complete dual traversal in r30n24-artifact-dual-exhaustive-scan, executed on 2026-07-24.Also cited at Definition, term a(24), link to Gage, Laub, and McGarry (2005), and extension note citing page 7, Table 2.Also cited at Inline ISO C11 source below, compiled and executed on 2026-07-24.Supports the formulation or a neighboring result cited in the packet for “rule 30 cycle length 24.”Source named by the research packet.
Fixed exhaustive functional-graph problem on 16777216 states.
Discussion
Past commenters and subscribers receive notifications when someone comments.