The Collatz Conjecture: The million dollars puzzle
Do you want a quick million dollars? How about a million dollars and overnight fame? Not so fast, here is the catch. What if I told you that it would involve solving one of the most difficult problems in mathematics that has troubled the greatest minds for decades? The problem famously goes by the name Collatz Conjecture.
It is an incredibly easy to state problem but very hard to crack. Paul Erdos, a renowned mathematician of his time famously claimed that, “Mathematics is not yet ripe for such questions.’’
Here’s the problem, even a sixth grader can grasp it. Take any number greater than 0 to start with. If that number is even then divide it by 2, but if the number is odd then multiply it by 3 and add 1. The result you get will be your new number.
Keep repeating the process indefinitely with your new number and you will eventually and hopefully be stuck in a 4-2-1 cycle. In other words, the sequence of numbers will eventually collapse to the number 1. As far as we can tell, this is what has happened to all the numbers that we have tested. Let’s try out an example. Maybe we might find a counterexample and claim the 1 million dollars prize tag in addition to being an overnight sensation. Let’s start out with five. 5 is an odd number , so we are going to multiply it by three then add one. (5x3)+1=16. Sixteen is now our new number. Because 16 is even , we divide it by two and get 8. Eight then becomes our new number. Eight becomes four, four becomes two and two becomes one. We are back at one! What if we continued the process after reaching 1? One is an odd number therefore we multiply it by 3 and add 1 to get 4. Four is an even number therefore we divide it by 2. This gives us 2 which is another even number. If we divide 2 by 2 we get 1. We can't get out of this cycle. This is what the 4-2-1 cycle means.
Does there exist a starting number that will not eventually collapse to 1?
That is the main question of the Collatz Conjecture.
Could there be a starting number whose sequence goes on and on to eternity? Or even more interestingly, could there be a starting number whose sequence gets stuck in a different cycle other than the 4-2-1 cycle? As far as we can tell, no one knows for sure.
Computers have painstakingly checked all the numbers up to 300 quintillion by brute force and they all collapsed to one! One might say, “isn’t that enough already?“ Well, in mathematics nothing is left for assumption. Who knows, maybe the next number after 300 quintillion might be a counterexample.
Different starting numbers take different numbers of steps before collapsing back to one. In our example it took the number 5, five steps to get back to one and the highest point it reached was 16 before collapsing back down to 1. On the other hand, if you experiment with 27 as a starting number then it will take 111 steps! And the highest point reached will be 9232. You can play around with this special calculator and it will detail all the steps for a starting number that you input and it will even draw a graph of how the steps go up and down before collapsing back to one.
One way to prove this problem wrong is to find a number that will get stuck in a different cycle other than the 4-2-1 cycle. If such different cycles are in existence then Eliahou, a mathematician proved in 1993 that such a cycle must contain at least 17,087,915 steps in it. That would require a computer to evaluate!
Another way to prove the problem wrong is to find a starting number that will go on and on without being stuck in a different cycle or coming back to one. Of course that would require a direct proof because you cannot keep computing it indefinitely.
Takeaways:
The problem was named after Lothar Collatz a German mathematician who proposed it in 1937
A Japanese bank offered a prize for the proof of the conjecture of 120 million Yen, equivalent of 923’550.00 USD as of Jan 2023 exchange rate.
The problem is also called the 3n+1 conjecture
“This is an extraordinarily difficult problem, completely out of reach of present day mathematics.” – Jeff Lagarias, 2010
“For about a month everyone at Yale 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.” – Shizuo Kakutani, 1960
A conjecture in math loosely refers to a statement that is rumored to be true or false but has yet to be formally proven. For example if I have never seen any monkey in my city since I was born I might put forward a conjecture that says no monkeys exist in my city. However, this is just a suspicion because I haven't searched everywhere to be certainly sure that there are really no monkeys in existence. However once the statement has been fully proven then it stops being a conjecture and is now called a theorem!
If a proof were to be found for all the even starting numbers, then the whole problem would also automatically be solved for the odds as well. The reason is because if we divide an even number by 2 we will either get another even number or an odd number. In the case that we get an odd number, multiplying an odd number by 3 then adding one will always result in an even number! So if the conjecture is true for all evens then it is true for the odds as well.
The reverse case is also true as well. If a proof is found that the conjecture is true for all the odds then it will automatically be true for all the evens as well. This is because multiplying any odd number by 3 and adding 1 will always result in an even. And dividing an even by two will either give me another even or an odd. So it will always either result in an odd which is already proven true or it will keep resulting in an even as I keep halving it until I get to 1. This will be the case if the starting number was a power of 2. I apologise if this got mind-boggling, but to better visualize it it would be advisable to express an even number as 2n and an odd number as 2n+1 and then algebraically manipulate them to see if they would produce an even or odd.
If you would like to explore the problem further you can watch a video of Professor Terrence Tao giving a lecture on the Collatz Conjecture.
⋆⋆⋆A conjecture so old, it challenged the minds of the bold⋆⋆⋆
Comments