The Collatz Conjecture is one of the unsolved problems in mathematics. The concept is so simple that even a primary school student can understand it, yet experts haven’t been able to prove it. Why can’t this problem be solved? How far have we gotten with it? What makes it so difficult? To answer these questions, I’m going to introduce various approaches to proving the Collatz Conjecture. And hey, if you have a lightbulb moment with the proof discussed in this article, you could bag yourself a cool million bucks!
What is the Collatz Conjecture?
First off, let’s talk about what the Collatz Conjecture is. It claims that if you repeat the following steps, any positive integer will eventually reach 1:
- If the number is even, you halve it.
- If the number is odd, you triple it and add one.
Let’s run through the Collatz Conjecture using 11 as an example:
11 (odd) ⇒ 11×3+1=34
34 (even) ⇒ 34/2=17
17 (odd) ⇒ 17×3+1=52
52 (even) ⇒ 52/2=26
26 (even) ⇒ 26/2=13
13 (odd) ⇒ 13×3+1=40
40 (even) ⇒ 40/2=20
20 (even) ⇒ 20/2=10
10 (even) ⇒ 10/2=5
5 (odd) ⇒ 5×3+1=16
16 (even) ⇒ 16/2=8
8 (even) ⇒ 8/2=4
4 (even) ⇒ 4/2=2
2 (even) ⇒ 2/2=1
We’ve arrived at 1, so we can see that the Collatz Conjecture holds true for 11. Even though it spiked to 52 at one point, it eventually settled down to 1.
How to Solve the Collatz Conjecture
Solving the Collatz Conjecture means proving whether it’s correct or incorrect. In other words, you have to prove that by continually following the rules of the Collatz Conjecture, all positive integers will indeed end up at 1, or you need to find a number that doesn’t end up at 1, despite following the conjecture’s operations.
As of 2021, computers have proven that the Collatz Conjecture holds true for all positive integers up to 5.76 x 10^18. That’s why it’s widely believed that the Collatz Conjecture is probably true.
Current Progress
Supercomputers have crunched the numbers and confirmed that all integers up to 5.76 x 10^18 do end up at 1. Furthermore, in 2019, a Chinese mathematician named Terence Tao published a paper suggesting that “almost all positive integers will reach 1 when considering logarithmic density.” Note that he said almost all, not all, so it doesn’t completely solve the Collatz Conjecture. It seems like cracking this nut is still pretty tough.
An Approach from Probability
First up, I want to share how we can tackle the Collatz Conjecture using probability. The idea is that if the probability of the number decreasing is higher than it increasing, then the number should gradually get smaller and eventually hit 1.
If the number we’re dealing with is even, we halve it, and if it’s odd, we triple it and add one. Let’s call the number we’re operating on \(m\). The probability of \(m\) being even is the same as it being odd, so we’ll consider both scenarios.
If \(m\) is even, since it’s even, we can say \(m=2n\).
\(2n\) ⇒ \(\displaystyle \frac{2n}{2}=n\)
Since we can’t tell if \(n\) is even or odd, we can’t proceed with any further operations.
If \(m\) is odd, since it’s odd, we can say \(m=2n+1\).
\(2n+1\) ⇒ \(\displaystyle 3(2n+1)+1=6n+4=2(3n+2)\)
Since \(2(3n+2\ ) is even, we can operate on it once more.
Again, since we can’t tell if \(3n+2\) is even or odd, we can’t go any further.
From this reasoning, we can gather that “when operating on an even number, it’s uncertain whether the result will be even or odd,” and “when operating on an odd number, the result will definitely be even. I’ve put this into a table.”
| Start | 1st Operation | 2nd Operation |
|---|---|---|
| Even | Even | Even |
| Odd | ||
| Odd | Even | |
| Even | ||
| Odd | Even | Even |
| Odd | ||
| Even | Even | |
| Odd |
Next, I’ve made a table of the ratios of even to odd outcomes.
| Start | 1st Operation | 2nd Operation | |
|---|---|---|---|
| Even | 50％ | 75％ | 62.5% |
| Odd | 50％ | 25％ | 37.5% |
Looking at this table, it’s apparent that there seems to be a higher probability of getting an even number (thereby reducing the number).
Let’s now consider what happens to the ratio of even and odd numbers when we take the number of trials to infinity. We’ll convert the principle that operating on an even number results in either an even or an odd number with equal probability, and that operating on an odd number always results in an even number, into equations. Let’s denote the probability of obtaining an even number after \(a\) trials as \(K_a\).
When the number of trials is 1 (starting point):
\(K_1=0.5\)
When the number of trials is 2:
\(\displaystyle K_2=\frac{K_1}{2}+(1-K_1)=\frac{0.5}{2}+(1-0.5)=0.75\)
When the number of trials is 3:
\(\displaystyle K_3=\frac{K_2}{2}+(1-K_2)=\frac{0.75}{2}+(1-0.75)=0.625\)
When the number of trials is \(a\):
\(\displaystyle K_a=\frac{K_{a-1}}{2}+(1-K_{a-1})=1-\frac{K_{a-1}}{2}\) …①
We’ll find the general term for when the number of trials is \(a\).
We define the characteristic equation as follows:
\(\displaystyle c=1-\frac{c}{2}\) …②
The solution to this characteristic equation is:
\(\displaystyle c=\frac{2}{3}\) …③
Subtracting equation ② from equation ① gives us:
\(\displaystyle K_a-c=1-\frac{K_{a-1}}{2}-(1-\frac{c}{2})\)
\(\displaystyle K_a-c=-\frac{1}{2}(K_{a-1}-c)\)
Now we substitute ③ into the equation:
\(\displaystyle K_a-\frac{2}{3}=-\frac{1}{2}(K_{a-1}-\frac{2}{3})\)
Since we know that \(\displaystyle K_a-\frac{2}{3}\) has a first term of \(\displaystyle K_1-\frac{2}{3}\) and a common ratio of \(\displaystyle -\frac{1}{2}\), the general term for \(\displaystyle -\frac{1}{2}\) is as follows:
Now that we have the general term, we can find the value of \(K_a\) as \(a\) approaches infinity:
\( \displaystyle \lim_{a \to \infty} (-\frac{1}{6})(-\frac{1}{2})^{a-1}+\frac{2}{3}=\frac{2}{3}\)
It turns out that the probability of obtaining an even number after operating on some number is 2/3.
Let’s calculate the expected value for one operation. In one operation, the number \(x\) will halve with a probability of 2/3 if it becomes even, and it will triple and increase by one with a probability of 1/3 if it becomes odd, which gives us the following equation:
\( \displaystyle (\frac{1}{2})(\frac{2}{3})+(3+1)(\frac{1}{3})=\frac{5}{3}\)
\(\displaystyle 1＜\frac{5}{3}\)
Since the expected value per operation is greater than 1, the result suggests that the number will keep increasing with repeated operations. This is a failed proof. The diverging result contradicts the content of the Collatz Conjecture, so there might be something wrong with our approach.
Since the process ends once it passes through 1 even once, could the idea of operating indefinitely be wrong? If that’s the case, instead of converging numbers, maybe it would be better to seek the distribution of results from repeated operations. Moreover, when approaching from probability, we need to prove not only that the values decrease but also that they don’t enter a loop.
An Approach Using Mathematical Induction
Now let’s attempt to prove using mathematical induction. The Collatz conjecture holds for the integer 1. Furthermore, if we assume that it holds for all positive integers up to \(n\) and can prove that it also holds for \(n+1\) then we can prove the conjecture for all positive integers.
Let \(f_t(x)\) be the function that represents performing the Collatz conjecture operation \(t\) times. If \(f_t(x)\) is less than \(f_t(x+1)\), then any number will gradually decrease and eventually reach 1. Therefore, we need to demonstrate the following relationship to complete the proof:
\(n+1>f_t(n+1)\)
Let’s check whether the above relationship holds. Since we do not know whether \(n+1\) is even or odd, we need to consider both cases.
If \(n+1\) is even, we set \(n+1=2m\). Then the following equation holds:
\(2m\) ⇒ \(\displaystyle \frac{2m}{2}=m\)
\(2m＞f_1(2m)=m\)
We can see that when \(n+1\) is even, operating on it makes it smaller than its original value.
Next, if \(n+1\) is odd, we set \(n+1=2m+1\).
\(2n+1\) ⇒ \(\displaystyle 3(2n+1)+1=6n+4=2(3n+2)\)
Since \(2(3m+2)\) is even, we operate on it again:
\(2(3n+2)\) ⇒ \(\displaystyle \frac{2(3n+2)}{2}=3n+2\)
Since \(2m+1＜f_2(2m+1)=3m+2\), we need to operate again. However, we cannot determine whether \(3m+2\) is even or odd, so we cannot operate further. We could make further progress with additional case division, but as we learned from the probabilistic approach, repeated operations tend to increase the value. Thus, this approach also reaches a limit. It seems that the $1 million will not be so easily won.
Proof Using Binary Representation and General Term of Difference Sequences
A research paper proposing a proof of the Collatz conjecture using binary representation and difference sequences has been published. The author of the paper commented, “I believe it can be understood with simple mathematics, which should be encouraging for high school students.” The paper is available for free download via the provided link, so please take the opportunity to read it.
