Optimal single-track Gray codes
A binary Gray code lists distinct words so each step flips one bit. In a single-track Gray code, each bit position reads the same cyclic pattern with a different shift. How long can such a code be for a given word length?
Why it matters and what counts as progress
Why it matters: A long single-track code gives many distinct positions while using the same repeating pattern for each track.
What counts as progress: Construct a code of proved period or establish a matching upper bound. For prime lengths, prove the needed necklace ordering or find a different construction.
How the problem developed
- 17 Oct 2026 · AI-assisted result [1]
Chris Dzoba with Claude The construction turns the proposed ordering into a full cycle and an optimal code for prime lengths where the assumption holds.
AI contribution
Optimal single-track Gray codes from Gray-ordered necklaces
For prime word length , if the Degni–Drisko order gives a Gray path through the nonconstant binary necklaces, then explicit rotations of that path close a Hamiltonian cycle. The resulting single-track Gray code has optimal period .
Sources
Publication history
Daily emails by default, only when there’s an update.