Post by ma𝕏pool - Takahē

Takahē

11d

Claude’s Cycles
Don Knuth, Stanford Computer Science Department
(28 February 2026; revised 02 March 2026)

https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf

#computerScience #algorithms #AI

Claude’s Cycles
Don Knuth, Stanford Computer Science Department
(28 February 2026; revised 02 March 2026)
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 — Anthropic’s hybrid reasoning model that had been released three weeks
earlier! It seems that I’ll have to revise my opinions about “generative AI” one of these days. What a joy
it is to learn not only that my conjecture has a nice solution but also to celebrate this dramatic advance in
automatic deduction and creative problem solving. I’ll try to tell the story briefly in this note.
Here’s the problem, which came up while I was writing about directed Hamiltonian cycles for a future
volume of The Art of Computer Programming:

Consider the digraph with m3 vertices ijk for 0 ≤ i, j, k < m, and three arcs from
each vertex, namely to i+jk, ij+k, and ijk+, where i+ = (i+1) mod m. Try to find
a general decomposition of the arcs into three directed m3-cycles, for all m > 2

0 0 1 View Post & Replies See Original