Claude Just Solved an Open Math Problem That Had Stumped Researchers for Weeks

Don Knuth just published a paper with an unusual opening line: “Shock! Shock! I learned yesterday that an open problem I’d been working on for several weeks had just been solved by Claude Opus 4.6.”

That’s not the kind of sentence you expect from the author of The Art of Computer Programming. And the problem wasn’t a toy. It was an unsolved combinatorics question about directed Hamiltonian cycles that Knuth had been building toward for a future TAOCP volume. Claude found a working construction for all odd values of m in about one hour.

• 31 explorations in a single session, guided by Filip Stappers, who prompted Claude to document progress after every run
• Construction verified correct for all odd m from 3 to 101 by Stappers, and proven correct by Knuth via hand proof
• 760 valid “Claude-like” decompositions exist for all odd m, according to exhaustive analysis of the m=3 case
• The proof was formally verified in Lean by Kim Morrison on March 4, two days after Knuth finished it
• Even m remains open (m=2 is impossible; m=4 through 200+ has been solved computationally but not by a general closed-form construction)
• Knuth, who has been openly skeptical of generative AI, called it “a dramatic advance in automatic deduction and creative problem solving”

The Problem

The question came from Knuth’s ongoing work on Hamiltonian cycles for a future TAOCP volume. The setup is a 3D digraph:

• Take all m^3 triples ijk where 0 ≤ i, j, k are less than m
• From each vertex, draw three arcs: to the vertex where i increases by 1 mod m, to the vertex where j increases, and to the vertex where k increases
• Find a way to split all three arcs from every vertex into exactly three directed cycles, each visiting all m^3 vertices exactly once (three directed Hamiltonian cycles)

Knuth had solved it for m=3 himself. His friend Filip Stappers found solutions empirically for m=4 through 16 using a computer. But a general construction that works for all m was unknown.

How Claude Found It

Stappers posed the problem verbatim to Claude and added one key instruction: document progress in a plan.md file after every single exploration run, no exceptions.

Claude’s 31 explorations read like a compressed research sprint:

Explorations 1-5: Setup and dead ends. Claude reformulated the problem as assigning a permutation of 2 at each vertex to govern which direction each cycle takes. It tried linear functions, depth-first search (too slow), and a “2D serpentine pattern” that it independently recognized as a Cayley digraph. The 3D version of that serpentine pattern turned out to be a classical modular Gray code, but deleting it left a “rigid residual structure making decomposition difficult.”

Explorations 6-14: More dead ends. Several approaches based on symmetry and hyperplane constraints failed. None generalized.

Exploration 15: The key reframe. Claude introduced what it called a “fiber decomposition”: the digraph is naturally layered by the sum s = (i+j+k) mod m, since every arc moves a vertex from fiber s to fiber s+1. This reduced the problem to choosing permutations within each layer independently.

Explorations 16-25: Simulated annealing. Claude implemented the fiber framework and found solutions for m=3 (0.1 seconds, via exhaustive backtracking) and m=4 (via simulated annealing). Pattern search across layers found no general formula. Conclusion after exploration 25: “SA can find solutions but cannot give a general construction. Need pure math.”

Explorations 26-30: Near misses and geometry. Exploration 27 found a construction using cyclic coordinate rotation that produced individually valid Hamiltonian cycles, but with conflicts at 3(m-1) vertices on the hyperplane where i+j+k = m-1 mod m. Exploration 29 proved those conflicts couldn’t be patched. Then exploration 30 looked back at the simulated annealing solution from exploration 20 and noticed something: the permutation at each fiber depends on only a single coordinate.

Exploration 31: Working construction. Using that observation, Claude built a concrete Python program. The permutation d at each vertex depends only on whether the fiber index s is 0, m-1, or something in between, and whether a single coordinate hits a boundary. Stappers tested it for all odd m from 3 to 101: every decomposition was valid.

What Was Proved

The construction Claude found is elegant in retrospect. For the first of the three cycles, the rule reduces to:

• Compute s = (i+j+k) mod m
• If s = 0: increment i if j = m-1, otherwise increment k
• If 0 is less than s and s is less than m-1: increment k if i = m-1, otherwise increment j
• If s = m-1: increment k if i = 0, otherwise increment j

(“Increment” means add 1, mod m.)

Knuth proved this cycle visits all m^3 vertices by showing that the vertices for each fixed value of i appear consecutively, and that the local rules force i to cycle through all values exactly once, covering all m^2 triples for each i along the way. The proof for the other two cycles is similar but the case analysis is messier. Knuth included the full proof in the paper and it was Lean-verified within two days.

The broader result: Knuth showed there are exactly 11,502 Hamiltonian cycles for the m=3 case, of which exactly 996 generalize to all odd m. These 996 can be used to build valid three-cycle decompositions, and exactly 760 of those decompositions use only generalizable cycles. Claude happened to find one of those 760.

A simpler construction was later found by Maximilian Reitbauer, using only the fiber index s and the coordinate j, with the identity permutation at almost every vertex. He found the proof by alternating between GPT and Claude.

Caveats and What’s Left

The result covers odd m only, and Claude knew it. During exploration 24, it reported finding solutions for m=4, 6, and 8 but saw no generalizing pattern. After the odd case succeeded, Stappers ran a separate session for even m. After about four hours, Claude got stuck and stopped producing working code.

Even m was later cracked computationally: Ho Boon Suan wrote a C program (generated with GPT-5.4-codex) that produces valid decompositions for all even m from 8 to 200+. A 14-page proof of that program’s correctness was then produced entirely by GPT-5.4 Pro. The case m=2 was proved impossible in 1982; m=4 and m=6 remain unresolved by any general construction.

The collaboration scaffolding mattered too. Knuth’s paper notes that Claude made multiple errors requiring restarts, and that Stappers had to repeatedly remind it to document progress before starting the next run. The guidance prompt (“update plan.md after EVERY run, no exceptions”) was necessary to keep the session coherent. Without structured checkpointing, useful intermediate results from early explorations would have been lost.

Knuth closes with: “We are living in very interesting times indeed.” Coming from someone who has spent decades skeptical of AI’s mathematical abilities, that reads as a considered verdict, not a throwaway line.

The paper and associated code are at cs.stanford.edu/~knuth/papers/claude-cycles.pdf.