Select any whole number greater than zero then perform the following operation:
If the number is even, divide it by 2.
If the number is odd, multiply it by 3 and add 1.
It’s said that if you continue to repeatedly apply the process, you’d always end up at 1. This is the premise of the Collatz conjecture, also known as the 3x + 1 Problem. The conjecture was named after German mathematician Lothar Collatz, who first suggested it in 1937.
Until now, no one knows whether the conjecture is correct. As of 2017, the conjecture has been tested using computers for all numbers up to 87 × 260. The result indicated that the conjecture is valid for all the numbers checked. Even if it took several steps for some numbers, gradually, they all ended in (4, 2, 1) cycle.
Here are the numbers that take the longest to converge to 1 (For 101 to 1010):
less than 10 is 9, which has 19 steps,
less than 100 is 97, which has 118 steps,
less than 1,000 is 871, which has 178 steps,
less than 10,000 is 6,171, which has 261 steps,
less than 100,000 is 77,031, which has 350 steps,
less than 1 million is 837,799, which has 524 steps,
less than 10 million is 8,400,511, which has 685 steps,
less than 100 million is 63,728,127, which has 949 steps,
less than 1 billion is 670,617,279, which has 986 steps,
less than 10 billion is 9,780,657,630, which has 1132 steps, and
less than 100 billion is 75,128,138,247, which has 1228 steps.
The experiment may look convincing but we cannot conclude that the conjecture is true based on this. It only takes a counterexample to prove the conjecture wrong. This was what happened to the Mertens conjecture, Pólya conjecture, and Skewes’ number when they were debunked with a large counterexample.
But proving this innocent looking and seemingly simple conjecture is not simple at all. Many have tried to prove or disprove it but failed. When Paul Erdős learned of this problem, he remarked, “Mathematics is not yet ready for such confusing, troubling, and hard problems.” Erdős believed that we still do not possess the knowledge and tools powerful enough to solve this problem. He then offered $500 to anyone who can solve it
Nowadays, many mathematicians believe that the conjecture is true due to probabilistic heuristics. Nonetheless, until a proof of the validity of the Collatz conjecture is found, the conjecture will remain a conjecture.