For such a problem, mathematics is not mature enough
This is what mathematician Paul Erdos said about the problem we are going to discuss. After I have discussed this issue, you may think that such a simple problem can be so complicated. Here we go!
Guess a positive integer x and bring in the following segment function to perform the operation.
If it is an even number, divide by 2; if it is odd, multiply by 3 and add 1, so that it becomes even again, and then divide by 2.
Suppose the number you have in mind is 21. 21 is an odd number. So, (3×21+1) = 64. 64 is an even number, and divide it by 2 to get 32. Similarly, 32 is also an even number, 16 is obtained further. Another even number, and then further get 16/2 = 8. The end result is 1.
Now, 1 is an odd number. So multiply it by 3, add 1, and get (3×1 + 1) = 4. Since 4 is an even number, we get 4→ 2→1.
Now, the problem "gets stuck" in a loop of 4→2→1.
Think of another number, like 7. 7 becomes 22, then 11. Then proceed as follows:
7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
The same goes for starting with 7 and ending up in a loop of 4→2→1.
This is known as the "Collatz Conjecture." Scientists have examined "countless" numbers, or 2^68 numbers to be precise, all following this conjecture.
The conjecture is named after Lothar Collatz. He proposed this conjecture in 1937. It also has many names, such as the 3n+1 problem, the 3n+1 conjecture, the Ulan conjecture (named after Stanisław-Ulan), the Horn valley problem (named after Shizuo Kakutani), the Swaites conjecture (named after Sir Brian Swaites), the Haas algorithm (named after Helmut Haas), and the Syracuse problem.
At first glance, this conjecture may seem to be a "conclusion", but so far it has not been proven, and no counterexample has been found. I reckon anyone will feel "should be simple" and have the urge to prove it! My advice is not to try, it's an abyss that will trap you in and get nothing.
Kolactu
Mathematicians have shown that almost all Korats sequences eventually become a number smaller than the starting number. Tao Zhexuan used partial differential equations to prove that 99% of the number will eventually become a value quite close to 1. Tao Zhexuan is probably one of the greatest mathematicians of the moment, and he is only a little bit close to proving this conjecture.
You can get as close to the Koraz conjecture as you can, but it's still out of reach— Tao Zhexuan
The number obtained with 3x+1 is called a hail number, why? Because if you draw it with graphics, they rise and fall like hail in a thundercloud. But the graph of each number is quite unpredictable.
For example, 26 takes only 10 steps to reach 1. The maximum number before reaching 1 is only 40. It looks like this:
26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
But if we take the number 27 as an example, it takes 111 steps to reach 1. The maximum number before reaching 1 is 9232. This sequence goes like this.
27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Similarly, 28, 29, and 30 only take 18 steps to reach 1. But 31 takes 106 steps to reach 1. The only law mathematicians can find is that there are no rules.
Graphical representation of each step in the Korats sequence of the number 50,000.
Here's a graph of a number (we took 50,000) to reach 1 at each step. If you take the logarithm and remove the linear trend, all you get is a geometric Brownian motion. All fluctuations are random.
According to statistics, 29.94% of the 1 billion numbers starting from 1 start with 1 (the highest digit is 1), 17.47% of the numbers begin with the number 2, 12.09% start with the number 3, and about 60% of the numbers start with the number 1, 2, 3. For larger numbers, such as 4, 5, 6... the percentage will go down. This distribution is called Benford's law. Benford's Law is even used to detect tax fraud and transaction fraud in banks.
Looking back at the Kolats diagram above, if every number follows this conjecture, then every number is a branch of an infinitely expanding tree. Let's do some cool things with this tree.
If you rotate each point on the path based on whether the numbers in the sequence are odd or even, plus some nice colors, you will get a coral-like structure.
The Koraz tree is visually expressed in an artistic way.
In the image above, I represent numbers from 1 to 50,000 in an artistic way, getting a structure that looks organic.
You might think that since we have examined 2^68 numbers, and all of them follow this conjecture, it must be true. But this cannot be taken as proof in mathematics.
The Polya Conjecture was proposed by the Hungarian mathematician Georges Polia in 1919 and proved false by C. Brian Haselgrove in 1958. The value of the counterexample is 1.854×10^361.
This brings us to think that while most mathematicians are struggling to prove this Kolatz conjecture, perhaps it cannot be proved. Like the Polya conjecture, there may be an absurdly large number that does not follow the Kolats conjecture.
We can try to find some more patterns in the conjecture. The figure below shows the first 50,000 numbers and the steps required for each number to reach 1.
The first 50,000 numbers and the steps required for each number to reach 1.
It looks like a "stream" of two strands starting from 0 and converging somewhere between 100-150. We can also see some strange straight horizontal lines. Remember when 28, 29, and 30 all reached 1 in 18 steps? So these three numbers form a straight line in the graph. From the figure, we can see that there are multiple such combinations of numbers, and they reach 1 with exactly the same number of steps.
Let's plot the first 50,000 numbers together with the function log₂(x). Now, for any power of 2, log₂(x) is the number of steps required to reach 1. More simply, the number 2^n reaches 1 in n steps.
We see log₂(x) as the lower bound of the function.
Returning to the proof of conjecture, there are two possibilities. One is that someone has proven the conjecture to be true or false. Or conjecture is an undeterminable problem.
The British mathematician John Conway summed up the problem in 1987. He assumed that there was a mathematical machine, which he named "Fractran". He also assumed that the machine was Turing-complete, meaning it could basically do anything a modern computer could do, but there could also be halting problems.
The problem of downtime is the focal point of logic and the solution to the third mathematical crisis. The essential question is whether, given a Turing machine T and an arbitrary language set S, T will eventually stop at every s∈ S. Its meaning is the same as that of a determinable language. Obviously, arbitrary finite S is determinable, and countable S is also downable — Wikipedia
Therefore, the Koraz conjecture may also be the object of a downtime problem. In this case, we may never be able to prove whether the Korats conjecture is true or false.
The 3x+1 problem shows us how immature mathematics is. This question can be described to a fifth-grader, but still no one has been able to prove or give counterexamples. It can be very frustrating that we can't solve such a simple and understandable problem, but that's the nature of mathematics.