Collatz Conjecture
The Collatz Conjecture is a conjecture named after Lothar Collatz, who introduced it is 1937. It is also known as the “3n+1 problem” or “3n+1 Conjecture”
A conjecture is a mathematical statement that is yet to be rigorously proved. Conjectures arise when a certain pattern is noticed for many cases. But, that does not necessarily mean it will hold true for all cases. There needs to be a rigorous proof in place to confirm that the statement holds true for all cases
The Collatz conjecture might look as simple as a class exercise in school, but has far reaching implications (including the fact that it is yet to have a conclusive proof)
Take any positive number
If it is an even number, divide by 2
If it is an odd number, multiply by 3 & add 1
If you repeat this process. You will eventually reach a certain number. Once you reach that number, you will keep coming back to that number. That number is 1. You can try it out for yourself.
The below comic from xkcd defines it better
The Collatz conjecture states that this process will eventually reach 1. Whichever number you take.
A few examples are listed below:
As you can see from the above examples, it is possible to reach 1 starting from “almost” any number. This “almost” is the reason why Collatz statement still remains a conjecture. Though it is evident that “almost” all numbers reach 1, there is yet no conclusive proof that “all” numbers follow this
How Long Does It Take?
Starting from any number, how many steps does it take to reach 1? There is no fixed formula/pattern here.
The number 4 reaches 1 in 2 steps (4->2->1), 12 & 13 take 9 steps each (as shown above) whereas 15 takes 18 steps and a larger number like 160 takes only 11 steps.
Who Travels The Longest?
Something that would be of interest would be to see which number travels the longest i.e Which number takes the largest number of steps to reach 1?
Among single digit numbers, 9 takes the longest with 19 steps
Among double digit numbers, 97 takes the longest with 118 steps
Among 3-digit numbers, 871 takes the longest with 178 steps
Among 4-digit numbers, 6171 takes the longest with 261 steps
Among 5-digit numbers, 77031 takes the longest with 350 steps
All the above are only odd numbers. Co-incidence? I think not
The Interesting Case Of 27
The number 27 seems to be a pretty harmless number right? If you think so, try applying Collatz’s conjecture to it. While you are it, I am pretty sure your mother would finish cooking your lunch. Yes. That is how long it is going to take!!!
The number 27 takes 111 steps to reach 1, going all the way up till 9232 (as seen in the graph below)
As you see, a seemingly innocent number like 27 takes 111 steps to reach 1. The Collatz conjecture is a highly unpredictable one and one that has baffled mathematicians. Why is it that numbers converge to one instead of ballooning off to higher numbers? Why is it that some numbers take a longer time?
The Collatz Conjecture has been proven till numbers as large as 10^18.
It is no wonder that the famous mathematician Paul Erdos himself commented that “Mathematics may not be ready for such problems”
Thank you for reading!!!
References
Collatz Conjecture – Wikipedia page