Donald Knuth’s 30-Year Problem — Solved by an AI

Something remarkable just happened in mathematics.

Donald Knuth — the legendary author of The Art of Computer Programming — recently described how a problem he had been thinking about for decades was finally solved.

Not by a graduate student.
Not by a research group.
Not by a math department.

But by an AI system.

The story appears in Knuth’s short note titled “Claude’s Cycles.”

And it is one of the clearest examples yet that machine reasoning systems are beginning to participate in actual mathematical discovery.

---

The Problem

The problem comes from combinatorics and graph theory.

Consider a directed graph with (m^3) vertices labeled (i,j,k) where each coordinate runs from (0) to (m-1).

From every vertex there are exactly three possible moves:

• increment (i)

• increment (j)

• increment (k)

(all modulo (m)).

The challenge is deceptively simple to state:

Can we decompose all edges of this graph into three Hamiltonian cycles?

A Hamiltonian cycle is a path that visits every vertex exactly once before returning to the start.

Knuth had already solved the case (m=3) and suspected that solutions should exist more generally. But finding a general construction turned out to be surprisingly difficult.

The question lingered for years.

---

Enter Claude

Recently, Knuth’s colleague Filip Stappers asked Claude Opus 4.6, Anthropic’s reasoning model, to investigate the problem.

What followed looked less like a chatbot session and more like a research notebook.

The model proceeded through a sequence of explorations:

1. Reformulating the problem in algebraic terms.

2. Testing linear and quadratic constructions.

3. Attempting brute-force depth-first search.

4. Discovering a “serpentine” cycle pattern.

5. Analyzing the graph using fiber decompositions.

6. Running simulated annealing searches.

Most attempts failed.

But the exploration gradually revealed structural regularities in the graph.

Eventually the model discovered a surprisingly simple rule that generates three Hamiltonian cycles.

The construction works for all odd values of (m).

---

The Algorithmic Insight

The solution depends on the quantity

\(s = (i + j + k) \bmod m.\)

Depending on the value of (s) and whether coordinates equal (0) or (m-1), the algorithm decides which coordinate to increment next.

This rule produces a cycle that visits all (m^3) vertices exactly once.

Two related rules produce the other cycles.

Together they partition all edges of the graph into three Hamiltonian cycles — exactly what Knuth had been looking for.

---

Verification

The construction was tested computationally.

For odd values of (m) up to 101, the decomposition works perfectly.

Knuth then supplied the mathematical proof explaining why the cycle structure covers every vertex.

---

Knuth’s Reaction

Knuth’s response to the discovery was refreshingly enthusiastic.

He wrote:

“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.”

When someone who wrote The Art of Computer Programming says that, it is worth paying attention.

---

Not the End of the Story

The result solves the problem for all odd values of (m).

But the even case remains mysterious.

The model reportedly found isolated solutions for (m=4,6,8), but no general rule.

So the full problem is still open.

Which means mathematicians — human or machine — still have work to do.

---

A Glimpse of the Future

This episode matters for a deeper reason.

For decades, computers have helped mathematicians with:

• symbolic manipulation

• brute-force search

• proof verification

But here we see something different.

The system explored hypotheses, recognized patterns, rejected dead ends, and ultimately discovered a construction that led to a proof.

In other words, it behaved less like a calculator and more like a research collaborator.

We are entering an era where mathematical discovery may increasingly become a human-AI partnership.

And if Donald Knuth himself is impressed, that should tell you something.