# Thread: Help with Collatz Conjecture

1. ## Help with Collatz Conjecture

I need help in seeing if I can turn an idea into a proof, or if I am merely ruining Math with my attempt at solving this. I recently watched a youtube video on the Collatz Conjecture. The Conjecture is simple enough:
Start with a positive number n and repeatedly apply these simple rules:

1. If n = 1, stop.
2. If n is even, divide n by 2.
3. If n is odd, multiply n by 3 and add 1.

Now the way I approached the matter was first by switching n into binary format. So lets say we start out with 59 I turn it into 111011. So following the rules you would multiply by 3 or 11.

00111011
x 11
_____________
00111011
+01110110
_____________
10110001
or 177

Then you add 1 and get 10110010 or 178.
Next since it is even you would divide by 2 and get 89 or 1011001.

Long story short, repeating this you end up with 1.

So here comes the part where I need help getting this to the proof stage. But the basic concept is this, no matter what number n you start out with it can always be represented in binary, and no matter how large the first number of the string will be a 1, and if it is odd it ends with a 1, even it is a 0. The division by 2 in binary of an even number is simply truncation of the string. So you end up with the first 1 and the last 1. This causes the string to be multiplied by 3. This multiplication causes the shifting of the string to the left and keeps a 1 at its right end, thus the addition of 1 comes in and frees up the string to be truncated by the division by 2. Ultimately the end result of the odd rule and 3n will yield a string that is nothing but 1s and thus the addition of 1 will give a string with 1 and the rest 0, which is then truncated down to just 1.

To further show that this holds true, you can change the Odd rule to 3n +/- m where m is any odd number less than 3n. The end result of this change of rules will still yield 1, as the first part of the string is 1 and the last will be 0 due to adding an odd number.

Sorry that this is a bit rambling. Like I said, I kinda need help getting this into a way that is much easier to understand. It all makes sense to me, but maybe I'm not seeing a flaw in this understanding.

2. ## Re: Help with Collatz Conjecture

Hey Angreifen.

For the proof stage I'd recommend thinking about it in terms of the number of bits and showing that it will always reduce in the number given so many steps and that the last step is always 1.

For the last step you will have to consider two cases - n is even and 2 meaning that you divide by two and get 1 and n is odd meaning you multiply n by 3 and then add 1 (which won't lead to a 1).

If you can show that the number of bits will tend to reduce and that you can end up with a two (from certain cases where the number of bits is in that range) then you have proven the algorithm.

Note that when you divide by two you take a bit away and when you multiply by 3 you always add a bit (and sometimes add two of them).

3. ## Re: Help with Collatz Conjecture

chiro, thank you for the hint, sorry it took so long to reply.

I've been thinking about figuring out how many steps it would take to get to 1. So far I know what he absolute minimum is for any number n, and that would be m or the number of bits minus 1, and that would be evident when n = 2^m where m = number of bits -1.

4. ## Re: Help with Collatz Conjecture

I think you should try and find the number of steps it takes to reduce one bit and then go from there on in.