【New Zhìyuán Report】
Just now, Claude independently solved an unsolved graph theory conjecture problem using only 31 steps.
Donald Knuth, the computer science pioneer who wrote "The Art of Computer Programming," exclaimed: "I have to reassess the role of generative AI in mathematical research."
On Stanford's official website, he personally published an original paper. The first two words are "Shock! Shock!"
Paper link: https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
Who is Donald Knuth?
He is the Turing Award winner who wrote "The Art of Computer Programming" (TAOCP) and invented TeX, considered the founding father of algorithms.
"The Art of Computer Programming" is Knuth's life's most important work. His purpose in writing this book was "to organize and summarize the known knowledge about computer methods, and to lay a solid mathematical and historical foundation."
When someone who has written algorithms books for 50 years begins to seriously consider AI's mathematical capabilities, it means: AI is entering the most core intellectual domain of humanity.
The Problem That Stumped the Algorithm Pioneer Was Solved by Opus 4.6
At the beginning of the paper, Knuth recounts:
I learned yesterday that an unsolved problem I had spent weeks studying was just solved by Claude Opus 4.6—the hybrid reasoning model released by Anthropic three weeks ago!
He frankly stated:
It seems I will eventually have to re-examine my views on "GenAI." It is truly a joy to discover that my conjecture not only has an elegant solution, but also to witness this dramatic progress in automatic reasoning and creative problem solving.
The story goes like this: The "The Art of Computer Programming" series has been in writing since the 1960s, and five volumes have now been published.
At the age of 88, this algorithm pioneer is still continuing to write this series.
In the book, he prepared a problem about directed Hamiltonian cycles. He and his friends proved a special solution to this problem, but when trying to generalize it to the general case, they couldn't solve it.
As a result, this problem was solved by Claude Opus 4.6.
More precisely, the AI found an elegant construction method, and Knuth subsequently provided a rigorous mathematical proof.
This paper thus becomes a landmark event—generative AI is, for the first time, being seriously recorded in the story of mathematical research.
What Does the Problem Look Like?
This problem is a graph theory problem that looks simple but is actually very complex.
First, imagine a three-dimensional grid space, such as an m×m×m cube.
Each point can be represented by three coordinates (i, j, k), where each coordinate ranges from 0 to m-1. So, there are m³ points in the entire space.
Next, we specify that from each point, we can move in three directions: i increases by 1, j increases by 1, k increases by 1. If the value exceeds m−1, it restarts from 0. This forms a toroidal space.
According to Knuth's formal definition in the paper, each vertex has three directed edges pointing to the "next" vertex in each of the three directions.
Therefore, the entire graph has m³ vertices and 3m³ directed edges.
A Hamiltonian cycle is a path that visits all vertices, each vertex exactly once, and finally returns to the starting point. This is a classic graph theory problem.
Knuth's proposed problem is even harder: not finding one route, but finding three routes, where each is a Hamiltonian cycle, each of length m³, and the three cycles exactly cover all edges.
In other words: each edge can only belong to one of the cycles.
Originally, Knuth was preparing to write this problem into a new chapter of "The Art of Computer Programming."
Why is this problem so difficult? The reason is that each point has three outgoing edges. To form a Hamiltonian cycle, one must be chosen. So at each point, a choice needs to be made.
Therefore, the problem size reaches 3^(m³)! This is almost impossible to complete through brute force search, so some regular construction method must be found.
Previously, Knuth had solved the case for m=3, and his friend Filip Stappers experimentally found solutions for 4≤m≤16.
This indicates: the answer likely exists!
So, can a general formula be found?
Multiple Attempts: Claude Doing Research
Filip handed the problem to Claude Opus 4.6 and established a strict rule—after each program run, the exploration progress must be recorded.
Interestingly, Claude didn't have a sudden flash of insight, but went through 31 explorations, a process very similar to a graduate student doing research.
In the first step, it tried simple functions, attempting to use a function g(i,j,k) to determine the direction at each point. But it soon found that simple linear functions didn't work.
In the second step, it started a brute force search, trying depth-first search (DFS), but the search space was too large and the efficiency too low.
In the third step, it was two-dimensional analysis. Claude found that if looking only at the two-dimensional case, a "snake path" could be found. So, it tried to extend the two-dimensional approach to three dimensions.
Subsequently, it constructed a three-dimensional snake path similar to Gray code, but after deleting the first path, the remaining structure was difficult to decompose.
In the next dozen or so explorations, Claude was basically constantly trial-and-error.
Key Breakthrough: Fiber Decomposition
In the 15th exploration, Claude proposed a key idea: fiber decomposition.
It noticed that if defining s = (i + j + k) mod m, then all edges move vertices from s to s+1, which means: the entire graph can be divided into layer structures by s.
Thus, each layer is like a two-dimensional grid, which greatly simplifies the problem.
Claude subsequently tried random search, simulated annealing, and backtracking search. These methods could find some solutions, but still didn't discover a general pattern.
So Claude concluded—pure mathematical structure is needed.
31st Exploration: Claude Found the Rule
In the 31st exploration, Claude finally proposed a simple set of rules, the core still being s = (i + j + k) mod m.
Then, based on the values of s, i, and j, decide whether to increment i, increment j, or increment k. The paper calls this the "bump" rule.
The rules are roughly as follows: if s=0, decide the movement direction based on the value of j. If 0
This generates a complete path.
Claude verified with programs: for m=3,5,7,9,11, the paths all hold. And all three paths are Hamiltonian cycles, all edges are used.
Of course, Claude only proposed the construction method; mathematically, rigorous proof is still needed.
Subsequently, Knuth proved that this path indeed visits all m² vertices with the same i value, then sequentially covers all i, finally forming a complete cycle of length m³.
Similar proofs also apply to the other two cycles, thus the entire problem was solved.
Moreover, Knuth discovered through further research that Claude's finding is not the only solution.
Actually, there are 760 similar decomposition methods; these solutions all satisfy the same structure. Claude just found one of them.
Additionally, Claude only solved the case where m is odd.
If m is even, the problem still has no general solution. Even m=2 has been proven impossible, so this research is still not completely finished.
The Greatest Significance Lies Not in Problem Solving
If there's a truly meaningful aspect to this event, it's not just solving the problem, but the way AI solved the problem.
In this process, Claude didn't guess the answer, but reformulated the problem, wrote programs, and discovered patterns. This process is very close to human research!
For decades, it was widely believed that mathematical proof was the most difficult field for AI to enter.
But this paper shows: AI has begun participating in genuine mathematical exploration.
In the future, a new research model may emerge—humans propose questions, AI explores structures, humans complete proofs.
And this "Claude's Cycles" paper may be regarded as a starting point.
Knuth has been writing "The Art of Computer Programming" for over half a century. This series records the development of human algorithmic thought.
And now, AI has been written into the papers of the algorithm master himself. This may just be a beginning.
Who is Donald Knuth? More Than the Godfather of Computer Science
Donald Knuth, originally named Donald Ervin Knuth, was born on January 10, 1938, in Milwaukee, USA.
Donald Knuth, American computer scientist, Professor Emeritus at Stanford University.
Knuth is recognized as the "founding father" of algorithm analysis, a pioneer of modern computer science, and has made foundational contributions to several branches of theoretical computer science.
For his major contributions to algorithm analysis and programming language design, he won the 1974 Turing Award (the "Nobel Prize" of computer science).
At that time, he was only 36 years old, a record that no other recipient has broken.
The award citation specifically emphasized his outstanding contributions to the art of computer programming through his book series "The Art of Computer Programming" (TAOCP).
In late 1999, this book was listed by the journal "American Scientist" as one of the 12 best academic monographs of the 20th century, alongside important works in the history of science such as Einstein's "Theory of Relativity" and Russell and Whitehead's "Principia Mathematica."
The first volume was published in 1968, and by 1976, over one million copies had been sold.
Bill Gates once评价d this book series:
If you really think you're a good programmer, go read "The Art of Computer Programming." If you finish this series, you must send me your resume.
In 1977, to make the book's printing more beautiful, he decided to develop a typesetting system. Eight years later, he returned with TeX.
TeX is the undisputed choice for academic typesetting worldwide, especially for handling complex mathematical symbols.
As of 2025, the published volumes include volumes 1, 2, 3, 4A, and 4B, with more volumes expected to be released in the future.
Volumes 1 through 5 aim to explain the core content of computer programming applicable to sequential machines; volumes 6 and 7 have more specialized but still important topics.
By the way, his Chinese name "Gao Denai" was given to him in 1977 before his visit to China by his friend Yao Chizong (wife of Andrew Yao, the father of Tsinghua's Yao Class).
Knuth is known for his wit. For example, he rewards anyone who finds any error in his works with $2.56, because "256 pennies is one hexadecimal dollar."
Pioneering the Concept of Vibe Coding
For Knuth, programming is not just technology or science, but also art.
Daily life is probably like programming. If you love something, you can incorporate beauty into it.
The TeX typesetting system inspired his concept of "literate programming"—
The literate programming paradigm differs from the traditional way and sequence of writing programs imposed by computers, replacing it with letting programmers develop programs in the order required by their own thinking's internal logic and flow.
For him, "literate programming is indeed the most important thing derived from the TeX project."
Later, Knuth recalled:
It not only allowed me to write and maintain more reliable programs faster than ever before, but also became my greatest source of joy since the 1980s—it is sometimes actually indispensable.
Some other large programs I've done, like the MMIX meta-simulator, could not have been written using any other methodology I've seen. Their complexity would have daunted my limited intelligence.
Without literate programming, my entire career plan would have collapsed. ... Literate programming is a necessary tool for you to reach the next level.
It can be said that Vibe Coding and literate programming come from the same lineage. I don't know if the old master has experienced true Vibe Coding himself.
From Child Prodigy to Computer Science Polymath
From childhood, Knuth was "extraordinarily bright"—
When he was 8 years old, a candy company held a puzzle competition for elementary students, asking them to use letters from "Ziegler's Giant Bar" (the candy factory and candy bar name) to spell as many words as possible.
Young Knuth pretended to have a stomachache and stayed home for two weeks, using a large dictionary to list 4,500 words, while the judges only had 2,000 words!
This not only won his class the championship (the prize was a TV and a Giant Bar for each student), but he also personally won a sled.
His mathematics research performance at Case Institute of Technology was so outstanding that when he completed his undergraduate studies, the university awarded him a master's degree in mathematics.
In 1963, he received his Ph.D. in mathematics from the California Institute of Technology.
From 1963-1968, he served as assistant professor and associate professor at Caltech.
From 1968-1992, he held a series of professor and named professor positions at Stanford University.
Since 1993, he has served as Professor Emeritus of "The Art of Computer Programming" at Stanford University.
According to statistics, Knuth has received over 100 honors throughout his life, including:
References
https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
https://valeman.substack.com/p/donald-knuths-30-year-problem-solved
https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ