3n+1 Simple but Complicated (The Collatz Conjecture)
The Collatz Conjecture, known as the 3n + 1 conjecture or hailstone sequences, is the most famous unsolved problem in mathematics, as well as the most straightforward issue. This simple problem has captivated mathematical ranks since birth in the mathematical world. The history of the Collatz Conjecture dates back to 1937 when the German mathematician Lothar Collatz published the sequence.
How does it work?
Start with any positive integer n.
If n is even, divide it by 2.
If n is odd, multiply it by 3 and add 1.
The conjecture says that no matter what positive integer you start with, this process will eventually reach the number 1.
For example, starting with n = 6:
6 is even, so we divide it by 2, yielding 3.
3 is odd, so we multiply it by 3 and add 1, yielding 10.
10 is even, so we divide it by 2, yielding 5.
5 is odd, so we multiply it by 3 and add 1, yielding 16.
16 is even, so we divide it by 2, yielding 8.
8 is even, so we divide it by 2, yielding 4.
4 is even, so we divide it by 2, yielding 2.
2 is even, so we divide it by 2, yielding 1.
And we reach 1. So, for n = 6, the sequence generated is 6, 3, 10, 5, 16, 8, 4, 2, 1.
There are also interesting facts that have been found while testing this sequence:
- The same number will never be repeated in the sequence because if that happened, there would be a loop of the same numbers, and the sequence would never end.
- An odd number is always followed by an even number. This has been proven to be true through simple algebra. For example, you write an odd number as 2m+1 (the 2m makes sure it is even, and adding one makes it odd) and plug it into the equation 3x + 1 is 3(2m + 1) + 1 = 6m + 4 = 2(3m +2) → the 2(3m+2) proves that it is even.
- The numbers 13 and 80 give the same cycle of results.
We can see this if we try to figure out the sequence.
As 13 is odd, we multiply by 3 and add 1 to get 40. As 80 is even, we divide it by two and get 40. Both cycles are now at 40, so if you figure it out further, they must follow the same cycle. 13 and 80 aren’t the only numbers that have the same cycle of results.
Why is it unsolved?
The Collatz conjecture has never been proven true for all numbers despite it being studied by mathematicians around the world. The only way to prove the conjecture is false is to find a counterexample that contradicts the statement. That would be trying to find a number that doesn’t contain or end in 1 or a sequence that is a repeating sequence–then it would never end in 1.
However, using computers, the numbers up to 268 or up to around 2.951020have all been tested. All of those numbers result in the number 1. However, this is not enough proof to say it is true for all numbers because counterexamples were found in large numbers in the Pólya conjecture and the Mertens conjecture.
The closest we have gotten to proof is by an Australian mathematician named Terence Tao, a professor of mathematics at the University of California, Los Angeles. He proved that almost all numbers will reach a point that is low enough to support the conjecture (under n/2, n, and ln n).
Despite the amount of work that has been done on this problem, it still remains a mystery that, hopefully, in the future, will be proven. Many people are still trying to figure out and prove the decade-old problem. Many people agree that this is true for all natural numbers, the debate will only be resolved when it is proved incorrect or correct.
