At first glance, the problem seems ridiculously simple. And yet experts have been searching for a solution in vain for decades. According to mathematician Jeffrey Lagarias, number theorist Shizuo Kakutani told him that during the cold war, “for about a month everybody at Yale [University] worked on it, with no result. A similar phenomenon happened when I mentioned it at the University of Chicago. A joke was made that this problem was part of a conspiracy to slow down mathematical research in the U.S.”
The Collatz conjecture—the vexing puzzle Kakutani described—is one of those supposedly simple problems that people tend to get lost in. For this reason, experienced professors often warn their ambitious students not to get bogged down in it and lose sight of their actual research.
The conjecture itself can be formulated so simply that even primary school students understand it. Take a natural number. If it is odd, multiply it by 3 and add 1; if it is even, divide it by 2. Proceed in the same way with the result x: if x is odd, you calculate 3x + 1; otherwise calculate x / 2. Repeat these instructions as many times as possible, and, according to the conjecture, you will always end up with the number 1.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
For example: If you start with 5, you have to calculate 5 x 3 + 1, which results in 16. Because 16 is an even number, you have to halve it, which gives you 8. Then 8 / 2 = 4, which, when divided by 2, is 2—and 2 / 2 = 1. The process of iterative calculation brings you to the end after five steps.
Of course, you can also continue calculating with 1, which gives you 4, then 2 and then 1 again. The calculation rule leads you into an inescapable loop. Therefore 1 is seen as the end point of the procedure.
Following iterative calculations, you can begin with any of the numbers above and will ultimately reach 1.
It’s really fun to go through the iterative calculation rule for different numbers and look at the resulting sequences. If you start with 6: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Or 42: 42 → 21 → 64 → 32 → 16 → 8 → 4 → 2 → 1. No matter which number you start with, you always seem to end up with 1. There are some numbers, such as 27, where it takes quite a long time (27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → ...), but so far the result has always been 1. (Admittedly, you have to be patient with the starting number 27, which requires 111 steps.)
But strangely there is still no mathematical proof that the Collatz conjecture is true. And that absence has mystified mathematicians for years.
The origin of the Collatz conjecture is uncertain, which is why this hypothesis is known by many different names. Experts speak of the Syracuse problem, the Ulam problem, the 3n + 1 conjecture, the Hasse algorithm or the Kakutani problem.
German mathematician Lothar Collatz became interested in iterative functions during his mathematics studies and investigated them. In the early 1930s he also published specialist articles on the subject, but the explicit calculation rule for the problem named after him was not among them. In the 1950s and 1960s the Collatz conjecture finally gained notoriety when mathematicians Helmut Hasse and Shizuo Kakutani, among others, disseminated it to various universities, including Syracuse University.
Like a siren song, this seemingly simple conjecture captivated the experts. For decades they have been looking for proof that after repeating the Collatz procedure a finite number of times, you end up with 1. The reason for this persistence is not just the simplicity of the problem: the Collatz conjecture is related to other important questions in mathematics. For example, such iterative functions appear in dynamic systems, such as models that describe the orbits of planets. The conjecture is also related to the Riemann conjecture, one of the oldest problems in number theory.
Empirical Evidence for the Collatz Conjecture
In 2019 and 2020 researchers checked all numbers below 268, or about 3 x 1020 numbers in the sequence, in a collaborative computer science project. All numbers in that set fulfill the Collatz conjecture as initial values. But that doesn’t mean that there isn’t an outlier somewhere. There could be a starting value that, after repeated Collatz procedures, yields ever larger values that eventually rise to infinity. This scenario seems unlikely, however, if the problem is examined statistically.
An odd number n is increased to 3n + 1 after the first step of the iteration, but the result is inevitably even and is therefore halved in the following step. In half of all cases, the halving produces an odd number, which must therefore be increased to 3n + 1 again, whereupon an even result is obtained again. If the result of the second step is even again, however, you have to divide the new number by 2 twice in every fourth case. In every eighth case, you must divide it by 2 three times, and so on.
In order to evaluate the long-term behavior of this sequence of numbers, Lagarias calculated the geometric mean from these considerations in 1985 and obtained the following result: (3/2)1/2 x (3⁄4)1/4 x (3⁄8)1/8 · ... = 3⁄4. This shows that the sequence elements shrink by an average factor of 3⁄4 at each step of the iterative calculation rule. It is therefore extremely unlikely that there is a starting value that grows to infinity as a result of the procedure.
There could be a starting value, however, that ends in a loop that is not 4 → 2 → 1. That loop could include significantly more numbers, such that 1 would never be reached.
Such “nontrivial” loops can be found, for example, if you also allow negative integers for the Collatz conjecture: in this case, the iterative calculation rule can end not only at –2 → –1 → –2 → ... but also at –5 → –14 → –7 → –20 → –10 → –5 → ... or –17 → –50 → ... → –17 →.... If we restrict ourselves to natural numbers, no nontrivial loops are known to date—which does not mean that they do not exist. Experts have now been able to show that such a loop in the Collatz problem, however, would have to consist of at least 186 billion numbers.
The length of the Collatz sequences for all numbers from 1 to 9,999 varies greatly.
Even if that sounds unlikely, it doesn’t have to be. In mathematics there are many examples where certain laws only break down after many iterations are considered. For instance,the prime number theorem overestimates the number of primes for only about 10316 numbers. After that point, the prime number set underestimates the actual number of primes.
Something similar could occur with the Collatz conjecture: perhaps there is a huge number hidden deep in the number line that breaks the pattern observed so far.
A Proof for Almost All Numbers
Mathematicians have been searching for a conclusive proof for decades. The greatest progress was made in 2019 by Fields Medalist Terence Tao of the University of California, Los Angeles, when he proved that almost all starting values of natural numbers eventually end up at a value close to 1.
“Almost all” has a precise mathematical meaning: if you randomly select a natural number as a starting value, it has a 100 percent probability of ending up at 1. (A zero-probability event, however, is not necessarily an impossible one.) That’s “about as close as one can get to the Collatz conjecture without actually solving it,” Tao said in a talk he gave in 2020. Unfortunately, Tao’s method cannot generalize to all figures because it is based on statistical considerations.
All other approaches have led to a dead end as well. Perhaps that means the Collatz conjecture is wrong. “Maybe we should be spending more energy looking for counterexamples than we’re currently spending,” said mathematician Alex Kontorovich of Rutgers University in a video on the Veritasium YouTube channel.
Perhaps the Collatz conjecture will be determined true or false in the coming years. But there is another possibility: perhaps it truly is a problem that cannot be proven with available mathematical tools. In fact, in 1987 the late mathematician John Horton Conway investigated a generalization of the Collatz conjecture and found that iterative functions have properties that are unprovable. Perhaps this also applies to the Collatz conjecture. As simple as it may seem, it could be doomed to remain unsolved forever.
This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.