On February 28, 2026, Donald Knuth, professor emeritus at Stanford University and author of the landmark work The Art of Computer Programming, published a note titled “Claude’s Cycles” describing how Anthropic’s Claude Opus 4.6 model solved an open problem in combinatorial mathematics that he had been working on for weeks. The announcement marks a significant milestone at the intersection of mathematical research and artificial intelligence.
The Problem: Decomposing Directed Hamiltonian Cycles
The problem concerns a directed graph (digraph) with m3 vertices, where each vertex ijk (0 ≤ i,j,k < m) connects to three edges. Knuth sought a general decomposition of these edges into three directed Hamiltonian cycles of length m3, for every m > 2. He had solved the case m = 3, while his collaborator Filip Stappers had empirically found solutions for m = 4 through 16, making it plausible that such decompositions exist for all m > 2.
Claude’s Methodology: From Brute Force to Mathematical Construction
Stappers submitted the problem to Claude Opus 4.6 using Knuth’s exact wording, while requiring systematic documentation of each step. The model’s approach was remarkable. It first reformulated the problem in group-theoretic terms, recognizing the graph as a Cayley digraph. It attempted linear and quadratic functions, depth-first search (DFS), two-dimensional analysis with serpentine patterns, and a fiber decomposition technique where each vertex is mapped to “layers” based on the sum i+j+k mod m.
After 31 successive explorations over approximately one hour of computation, Claude arrived at an explicit construction in the form of a Python program that produced valid decompositions for every odd m from 3 to 101. This was not a chance discovery. The model combined simulated annealing with algebraic analysis, identified structural patterns in earlier solutions, and generalized them into a closed-form construction.
Formal Proof and Verification
Knuth subsequently constructed a formal mathematical proof that Claude’s construction is correct for all odd m. The proof rests on analyzing the vertex sequence per fiber and demonstrating that each cycle contains exactly m2 vertices for each value of the first coordinate. Within days, Kim Morrison from the Lean community completed a machine-verified formalization of the proof, further strengthening confidence in the result.
Why It Matters
This result is significant for at least three reasons. First, it demonstrates that modern language models can function as tools for creative mathematical discovery, not merely coding assistants. Second, Claude’s methodology, which included successive reformulations, failed experiments, and eventual synthesis, structurally resembles the process a human researcher follows. Third, the subsequent extension of the problem to even numbers, achieved through collaboration between humans and multiple models (Claude and GPT), signals a new form of human-machine mathematical collaboration.
As Knuth observes: “We are living in very interesting times indeed.” The solution of Claude’s Cycles does not replace mathematical thinking, but highlights the capacity of AI models to participate meaningfully in the research process, opening new paths for combinatorial mathematics and beyond.
References
Knuth, D.E. (2026). “Claude’s Cycles.” A note by Donald Knuth documenting how Claude Opus 4.6 solved an open problem on directed Hamiltonian cycle decomposition. https://cs.stanford.edu/~knuth/papers/claude-cycles.pdf
Morrison, K. (2026). KnuthClaudeLean. Lean formalization verifying the correctness of Claude’s Hamiltonian cycle construction for odd m. https://github.com/kim-em/KnuthClaudeLean/
Knuth, D.E. (2011). The Art of Computer Programming, Volume 4A. Reference to the modular m-ary Gray code (p. 299) related to the serpentine pattern identified by Claude. Upper Saddle River, NJ: Addison-Wesley. https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming
Aquino-Michaels, K. (2026). “Completing Claude’s Cycles: Multi-agent structured exploration on an open combinatorial problem.” Analysis of multi-agent AI collaboration for solving the decomposition problem for even m. https://github.com/no-way-labs/residue