Claude Opus 4.6 Solves Open Combinatorics Problem That Stumped Knuth for Weeks

Anthropic's Claude Opus 4.6 solved an open problem in combinatorics that Donald Knuth had been working on for several weeks, the Stanford computer scientist announced on February 28. The problem involves decomposing the arcs of a directed graph into three Hamiltonian cycles, a challenge from Knuth's ongoing work on a future volume of The Art of Computer Programming, the series that has defined computer science for six decades. He revised his note through March 6.

"Shock! Shock!" Knuth wrote. "It seems that I'll have to revise my opinions about 'generative AI' one of these days."

The problem Claude cracked

Take a directed graph with m-cubed vertices. Each one connects to three others through modular arithmetic. Now split all the arcs into exactly three cycles that visit every vertex once. Knuth had cracked the smallest nontrivial case, m equals 3, and posed the general version as an exercise for his upcoming volume.

His friend Filip Stappers copied Knuth's exact wording into Claude, then sat with the model through a structured exploration. Thirty-one separate investigations in roughly one hour. Brute-force search. Too slow. Serpentine patterns borrowed from Gray codes. Partial progress. Simulated annealing. Solutions appeared but refused to generalize.

At exploration 30, Claude caught something in its own earlier output. A solution found by simulated annealing had hidden structure. The routing decision at each vertex depended on just a single coordinate. One exploration later, Claude had a working construction for all odd values of m. Stappers tested it for every odd number from 3 to 101. Perfect decompositions, every time.

From construction to proof

Working is not the same as proven. Knuth worked through the proof by hand. He traced how coordinates advance through the graph, showed that because m is odd, every possible vertex triple gets visited before the cycle closes. The math held.

Kim Morrison, part of the Lean proof assistant community, formalized the proof and posted it on GitHub by March 4. Days after the note appeared. "That's good to know," Knuth wrote, "because I've been getting more errorprone lately."

Knuth went further. He analyzed the full space of solutions. Of 11,502 Hamiltonian cycles for the base case, 996 generalize to all odd m. Exactly 760 valid decompositions sit within Claude's structural class. Claude landed on one of them.

The race to close the even case

Even values of m stayed open. The case m equals 2 was proved impossible in 1982. Claude found solutions for m equals 4, 6, and 8 during its original session but could not generalize. Stappers put the model back to work for four more hours. It degraded. "In the end, it was not even able to write and run explore programs correctly anymore," Stappers reported.

Others jumped in. Ho Boon Suan in Singapore pointed GPT-5.3-codex at the problem and got a construction for all even m of 8 or greater. He tested it for values up to 2,000. The graph at that scale contains 8 billion vertices. It held. GPT-5.4 Pro then produced what Knuth called "a beautifully formatted and apparently flawless 14-page paper" proving the construction correct. No human editing involved.

Maximilian Reitbauer found a simpler construction for odd m by passing text between GPT 5.4 and Claude 4.6 Sonnet. His solution uses the identity permutation at almost every step. Knuth admitted he would have found it himself had he examined all 760 valid decompositions. It was number 369 on the list.

The endorsement mathematicians can't ignore

Knuth does not hand out praise. Ask anyone who has tried to get one from him. Sixty years into writing The Art of Computer Programming, he still will not publish a result he has not verified down to the last line. When he writes "Hats off to Claude," mathematicians notice. Some feel emboldened. Others, nervous.

Claude did not regurgitate known results. It explored. Failed. Backtracked. Then found structure buried in its own earlier output. A skilled researcher might spend weeks doing the same thing. Claude took an hour. But Knuth documented the friction too. Stappers restarted sessions after random errors. He reminded the model "again and again" to document its own progress. That's the tell.

Multiple humans and AI systems, working across different model versions, closed out both halves of the problem within days. Keston Aquino-Michaels wrote up the multi-agent collaboration. His conclusion: it carries "potentially significant implications for how new problems can be tackled." You can read Knuth's full note, proof, and C code on his Stanford page.

He closed it with a request: stop writing to him about this. He has a book to finish.

Related stories

Google Doubled Gemini's Reasoning in Three Months. The Score Isn't the Story.

Last Tuesday, Google pushed an update to Gemini 3 Deep Think. Today, one week later, those same reasoning capabilities went live in Gemini 3.1 Pro, the production flagship available to every developer

The Implicator

DeepMind's AlphaEvolve scales mathematical search. Proofs still need people.

A flashy claim met sober reality: Google DeepMind says it can industrialize mathematical discovery, and the early record backs parts of that up. Fields Medalist Terence Tao has already built new work

The Implicator

🧠 AI Thinks Less When It Should Think More

Good Morning from San Francisco, Apple researchers just shattered AI's reasoning hype. Those fancy "thinking" models from OpenAI and Anthropic? They break down completely when puzzles get complex. T

The Implicator