Before we begin the discussion, I’d like to play a little game with you
- Pick any natural number.
- If your number is even, divide it by 2. If it is odd, multiply the number by 3 and add 1 to it. (i.e. for an even number compute and for an odd number , compute . )
- You now have with you a new number. Repeat step 2. Do not stop until you end up with the number .
For no natural number n will this process continue indefinitely. You will get to 1 after some finite number of repetitions. This is the essence of the Collatz Conjecture.
Example I choose the number 21. Since it is odd, I multiply it by 3 to get 63 and add 1 to it to get 64. Since 64 is even, I divide it by 2 to get 32 which gives me 16 which gives me 8, 4, 2 and then finally 1. As desired!
Now this was a pretty easy example but you can try it out for yourselves. Let me tell you that for some numbers, it will take a ridiculously long time until you get to 1. For example for the number 521, it takes 124 steps to get to 1!
Significance of the Conjecture
The Collatz Conjecture was first proposed by German mathematician Luthar Collatz in 1937. The conjecture has many different names but the most amusing of of them is HOTPO which stands for Half Or Triple Plus One. This conjecture may seem rather unimportant and inapplicable. Despite its frivolous nature, the conjecture is seems to be pretty important for number theorists.
According to Greg Muller‘s answer here on Math.SE, “…the Collatz conjecture seems to say that there is some sort of abstract quantity like ‘energy’ which is cannot be arbitrarily increased by adding 1. That is, no matter where you start, and no matter where this weird prime-shuffling action of adding 1 takes you, eventually the act of pulling out 2s takes enough energy out of the system that you reach 1. I think it is for reasons like this that mathematicians suspect that a solution of the Collatz conjecture will open new horizons and develop new and important techniques in number theory.”
My take on this conjecture
The Collatz conjecture is probably one of the first conjectures I encountered. Since it was pretty easy to understand I thought that maybe I could prove it without any help (at that point, I did not know what a conjecture was!) I tried for a few weeks and then finally decided to look it up on the internet for a hint. It was then that I found out that it was yet to be solved!
This is how I tried to tackle this problem back then
Any power of 2 will certainly get to 1. Infact, this is the only way to get to 1. The sequence obtained for any number (called the hailstone sequence) should always “enter” the series (powers of 2) if it is to eventually get to 1. Even more so, the hailstone sequence will only enter the series from even powers of 2 only (like 16 or 64). This is pretty easy to prove
Consider a number that is not a power of 2 but will be one on the next iteration (like $latex 5$; since . Note that has to be odd because if it were even then would have to be a power of hence it would have already entered the series of powers of .
So since is odd the next number in line would be . This should be a power of . OR such that,
What is required is that be proved even.
Proof The fact that implies . This follows from. We now find the solution set for the equation or .
We begin by noting . Since , it follows that . This means that the quantity is divisible by iff is even. It follows from this that if a quantity equals some power of , then has to be even. As desired.
Obviously, not every odd number n will result in a power of . For instance, is not a power of but is a power of . Is there some pattern to it? As it turns out, there is; and it is pretty easy to spot it too. For this we go back to :
The odd number has to satisfy this relation. So to find new s, ll we need to do id plug in even numbers into the equation. We see that the series of x’s obtained follow a certain pattern.
To make things easier, define a function . The domain of the function is the set of even numbers.
For even number , if we look at the difference , we see that it is $2^n$. So, difference between the odd number that results in in the next iteration and the other odd number that results in differs by .
Example The number 5 results to 16 which is and the number 21 results to 64 which is . The difference between 5 and 21 is 16; which is .
While these things hardly have anything to do with proving the conjecture itself, these are the observations that I made on the hailstone sequence. I thought I could prove it then, but these observations is as far as I got.
I actually had many other things to post about but none of them involved my own observations. So I decided to flip the pages of my scrap book and post it here.
Please do comment and share this post. Any constructive feedback is welcome!