Claude Opus 4.6 solves an open Hamiltonian-cycle problem, Donald Knuth reports
Result confirmed
Importance: major (4 of 5)Status
- Claim
Result confirmed
- Our reporting
- High confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 29 September 2026
Your AI and this story
- GPT-6 AstraIn its training data
- Claude Opus 5.5In its training data
- Gemini 4 HydrogenIn its training data
- Grok 4.7In its training data
It happened before the cutoffs of all four assistants, so it can be in their training data.
Key facts
- Note dated 28 Feb 2026, revised 4 Mar 2026
- Graph: vertices (i,j,k) mod m, arcs increment one coordinate; goal: split all arcs into 3 directed Hamiltonian cycles
- Claude found the odd-m construction in 31 guided explorations over about an hour; the even case remains largely open
- Knuth wrote the proof; the result was later formalised in Lean (kim-em/KnuthClaudeLean)
What happened
Knuth posed a Hamiltonian-cycle decomposition problem he planned for TAOCP. Working through it with Claude Opus 4.6 over dozens of explorations, a collaborator got a pattern that works for every odd m. Knuth then proved it and wrote up the story.
Why it matters
Coming from one of computing’s most respected and AI-sceptical elders, the note became a cultural marker that frontier LLMs could contribute original mathematical constructions.
Sources
3 sources from 3 sites. Numbers match the chips in the text.
3 sources: 2 primary, 1 press
Primary
- Donald Knuth: Claude’s Cycles (PDF)www-cs-faculty.stanford.edu, paper
- GitHub: kim-em/KnuthClaudeLean (Lean formalisation)github.com, code
Press
- Adafruit blog: Don Knuth wrote a paper thanking Claudeblog.adafruit.com, press
Changes
- Filed