Collatz Conjecture

Problem:

Pick a  natural number n, if it is odd multiply by 3 and add 1. If it is even divide it by 2. Repeat the process
indefinitely. The conjecture says no matter what number you pick it will eventually reach 1.

This conjecture hasn't been proven yet.

Here are two things that you would want to prove that would help with the overall proof.

1) Prove that there is no cycle other than the 1 -2 - 4 cycle. If there was to be a cycle then it would not converge to 1 but loop indefinitely. That would prove that this conjecture is wrong.

2) The next thing worth proving is that there are no such sequence such that its odd and even numbers alternate indefinitely i.e odd - even - odd - even.... . If that happens then since on odd we are multiplying each time by 3 and in even we are dividing by 2. The sequence diverges instead of converging (shrinking) to 1.


I think if we know that there are no cycles and no indefinite alternating sequence such as odd - even -odd- even then we can prove that any number you pick will converge down to 1. In order to converge to 1,  the sequence has to finally hit a power of 2 i.e 1,2,4,8,16.... I think you can see why that is so. The only way to get 1 is through the sequence of power of 2.

I visualize this as a barren tree i.e a tree without leaves.

 We can consider the stem as the sequence of power of 2 and each branch as some arbitrary sequence which finally meets the sequence of power of 2 at some point.

Below is the tree structure with some numbers. You can see all the branches finally meeting the stem sequence and hence converging down to 1.

I can see the difficulty involved in proving something such as this. We are basically trying to see if this infinite tree contains all the natural numbers there are. Since the branches branch out from its own branches and the sequence is very random, it is very hard to see what the behaviors of large numbers are. Its like trying to find patterns in the sequence of prime numbers.