The Collatz Conjecture is one tough nut to crack. Also called the 3n + 1 Conjecture, it is a deceptively simple unsolved problem in mathematics. The conjecture claims that for any positive whole number, you will always reach the value 1 if you repeatedly divide by two if the number is even and multiply by 3 and add 1 if the number is odd.
Let me explain with an example; suppose the initial number is n = 5. This number is odd, so the next value would be 3*5 + 1 = 16. This number is even, so the next iteration gives 16 / 2 = 8. This number is even so the next will be 8 / 2 =4, then 4 / 2 = 2, then finally 2 / 2 = 1 and we’ve reached 1. In table form:
|Step Number||Current Value|
So for an initial value of n = 5, the Collatz Conjecture process takes 5 steps to reach 1. It is known that this will work for even very large numbers, but no one has ever been able to prove that this process will always reach the value 1. Here’s a plot showing how many steps it takes to reach 1 using this process for all of the numbers up to one million:
Since there are of course an infinite number of numbers, we can’t just test them all and make sure – we need a mathematical proof to be able to say with certainty this will always work. You might think that since it works all the way up to a big number like 1,000,000 it will probably always work, but mathematics does not admit this type of reasoning and indeed there are famous examples where something seemed to be true for every value people tried, but then someone found a counterexample that was very large. Perhaps the most famous example of this is the Pólya conjecture for which a counterexample was found at n = 906,180,359.
Terrance Tao wrote an excellent post on the Collatz Conjecture on his blog. If you’re interested in taking a shot at this problem or just playing around with it a bit, that would be a good place to start learning about it.