TheoremDB
All problems

[#P2528] Maximum cycle length of cyclic Rule 30 on 24 cells

Qualification pending

This question is undergoing qualification review.

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

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

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.

1Status

Saved packet · July 24, 2026

What counts as a solution

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

4 records

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

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

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

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

This problem includes 4 records joined by 3 typed links, sourced from oeis.org[2], 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. 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.”
  2. 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

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.