The 3n + 1 problem
Can the Collatz conjecture be solved?
Open since 1937
Nobody knows yet. The rule is simple: if a number is even, halve it; if it is odd, triple it and add 1; repeat. Every starting number below about 271, more than two billion trillion, has been checked by computer and every one falls to 1, but no one has proved that all of them do. In 2019 Terence Tao proved that almost all of them come close, and experts still say a full proof is out of reach of today’s mathematics.
Steps to 1
111
Highest point
9,232
Why it is hard
Easy to check, impossible so far to prove
A rough argument says it should be true. Follow only the odd numbers in a sequence, and on average each one is about three quarters of the one before, so sequences tend to shrink. But an average is not a proof. One number with a sequence that climbs forever, or one loop that never touches 1, would break the conjecture, and nothing yet rules either out.
Checking cannot finish the job. David Barina’s project at Brno University of Technology has verified every start below 2075 × 260, about 271, as of January 2025. There are infinitely many numbers left.
Close relatives are provably unsolvable. In 1972 John Horton Conway showed that a natural generalization of the Collatz problem is undecidable: no method can settle every case. That does not mean the original is unprovable, but it shows how little room there is to work in.
Paul Erdős put it bluntly: “Mathematics is not yet ready for such problems.” Jeffrey Lagarias, who has catalogued the research for decades, called it in 2010 “an extraordinarily difficult problem, completely out of reach of present day mathematics.”
History
A problem with five names
Lothar Collatz (1910 to 1990) introduced the idea in 1937, two years after finishing his doctorate. It picked up names along the way: the Syracuse problem, a name Helmut Hasse proposed on a visit to Syracuse University in the 1950s, Kakutani’s problem, Hasse’s algorithm and Ulam’s problem. Shizuo Kakutani recalled that “for about a month everybody at Yale worked on it, with no result,” and that people joked it was “a conspiracy to slow down mathematical research in the U.S.”
Prizes followed. H. S. M. Coxeter offered $50 in 1970 and Erdős $500. In July 2021 the Tokyo company Bakuage announced 120 million yen, about 1.08 million dollars, for a proof.
What Tao proved in 2019
In September 2019 Terence Tao posted a paper showing that almost all starting numbers, in a precise statistical sense, eventually fall below any bound you like, however slowly it grows. Quanta Magazine called it a “huge result.” Tao himself was clear about the limit: “You can get as close as you want to the Collatz conjecture, but it’s still out of reach.” His method is not expected to reach a full proof.
3n − 1 gets trapped
Change the plus to a minus and the answer is no. Under 3n − 1, the number 5 runs 5, 14, 7, 20, 10 and back to 5, and 17 falls into a loop of 18 numbers. Those two loops, plus 1 and 2, are the only ones anyone has found. Running 3n − 1 on positive numbers is the same as running 3n + 1 on negative numbers, and whether there are other loops is just as open. Press 3n − 1 in the plotter and try 5 or 17.
Real vs legend
Collatz, sorted
| Claim | Status |
|---|---|
| Every number checked so far reaches 1. | Real · past 271 |
| The Collatz conjecture has been proved. | No · still open |
| Terence Tao solved it in 2019. | Partly · almost all, not all |
| There is a million dollar prize. | Real · 120 million yen |
| AI has solved the Collatz conjecture. | No · no such result |
| It might be impossible to prove. | Unknown · relatives are undecidable |
Questions
The Collatz conjecture
Can the Collatz conjecture be solved?
It has not been solved, and nobody knows whether it can be. Every start below about 271 reaches 1, but that is a check, not a proof. Terence Tao said in 2019 that it is “still out of reach,” and Jeffrey Lagarias called it “completely out of reach of present day mathematics.”
Is there a prize for solving the Collatz conjecture?
Yes. In July 2021 the Japanese company Bakuage offered 120 million yen, about 1.08 million dollars, for a proof. Earlier, H. S. M. Coxeter offered $50 and Paul Erdős $500.
Will AI solve the Collatz conjecture?
No one knows. AI systems have produced real results on other problems since 2025, but none on Collatz. A widely shared headline about an OpenAI model “solving” it turned out to be about a different problem, the Erdős unit distance conjecture.
Will 3n − 1 ever be solved?
It is just as open. 3n − 1 on positive numbers is the same as 3n + 1 on negative numbers. Three loops are known, through 1, 5 and 17, and nobody has proved there are no others.
Which number takes the longest to reach 1?
Under 100 it is 97, with 118 steps and a peak of 9,232. The famous one is 27: 111 steps, climbing to 9,232 before it falls. Under a million, 837,799 takes the longest, 524 steps.
Why is the Collatz conjecture so hard?
The averaging argument points the right way but proves nothing. John Horton Conway proved in 1972 that a close generalization is undecidable. Paul Erdős said mathematics “is not yet ready for such problems.”
Sources
Where this comes from
- Collatz conjecture, history, heuristics, Conway 1972, verification limit: Wikipedia.
- Jeffrey C. Lagarias, “The 3x+1 Problem and its Generalizations,” American Mathematical Monthly, 1985, names, Kakutani, Erdős and early prizes: HTML edition.
- Terence Tao, “Almost all orbits of the Collatz map attain almost bounded values,” 2019: arXiv.
- Kevin Hartnett, “Mathematician Proves Huge Result on ‘Dangerous’ Problem,” Quanta Magazine, 11 December 2019: quantamagazine.org.
- David Barina, convergence verification of the Collatz problem: Brno University of Technology.
- Bakuage prize announcement, 7 July 2021: PR Newswire.
- Jeffrey C. Lagarias, “The 3x+1 problem: An annotated bibliography”: arXiv.
- Mathematical discoveries by AI, none on Collatz: Wikipedia.
Share
An image of your number's flight. Copy link reopens it.
Poster
The flight of 27, all 111 steps, on one print.