Similar studies

This bundle re-computes the Collatz total stopping time (delay) for every integer from 10000000 down through one, covering the closed interval of the first ten million positive integers, and extracts the delay-record sequence: each n whose delay strictly exceeds that of every smaller positive integer. The enumeration produces 54 records, ending at n=8400511 with delay 685. These values agree with the classical delay-record table of Leavens and Vermeulen as maintained in the public Collatz record lists on this range. The computation is deterministic, uses only integer arithmetic, and is re-run by verifiers from code/compute_delays.py.

• Published, Reproduced, Reviewed.Published, Reproduced, Reviewed: An independent enumeration of Collatz total-stopping-time delay records for all n in 1..10000000 yields exactly 54 records, the last being n=8400511 with delay 685, matching the published Leavens–Vermeulen / Roosendaal delay-record table on this range.

Knuth's draft of section 7.2.2.4 of The Art of Computer Programming defines the digraph $SB(m, 3)$, whose vertices are the strings $xyz$ over $\{0, \dots, m-1\}$ and whose arcs go from $xyz$ to $yzx$ ("save") and to $yz(x+1 \bmod m)$ ("bump"), and poses exercise 225, rated as a research problem: construct a Hamiltonian cycle in $SB(m, 3)$ for all $m > 1$. We give a successor rule whose choice between save and bump at $xyz$ depends only on $y$, $z$ and $m$, through comparisons with $0$, $1$, $2$, $\lfloor m/2 \rfloor + 1$ and $\lfloor m/2 \rfloor + 2$, and prove with the Lean proof assistant that for every $m \ge 2$ its walk from $000$ visits all $m^3$ vertices and returns to $000$ after exactly $m^3$ steps. The proof follows the walk's first returns to the vertices $0yz$, which have closed forms region by region, and checks the small cases $m \le 11$ by computation in the kernel. This answers the exercise for every $m > 1$.

• Published, Reviewed, Formally verified.Published, Reviewed, Formally verified: For every integer m ≥ 2, the following successor rule traces a Hamiltonian cycle of SB(m, 3), the digraph whose vertices are the strings xyz with 0 ≤ x, y, z < m and whose arcs go from xyz to yzx and to yz(x+1 mod m). With k = ⌊m/2⌋ + 1, the successor of xyz is yzx when y ≥ k and z < k, when y = 0 and z ≠ 0, or when z = 1 and y ≥ 2, except that for odd m ≥ 7 it is yz(x+1 mod m) when z = 1 and y ≥ k + 1; every other xyz has successor yz(x+1 mod m). Starting from 000, the first m³ steps of the walk visit m³ distinct vertices, which is every vertex, and the walk is back at 000 after m³ steps.