Collatz’ Conjecture

So apart from wondering about whether the English language accepts z’s as a plural or not, this ‘problem’ is intrinsically interesting and very easy to understand:
Start with any natural number (a positive whole number) – I’m going to start with 7 – and  
If your number is odd, multiply it by 3 and add 1. If it is even, divide it by 2.
So as 7 is odd, we multiply it by 3 and add 1, getting 22.
Now we repeat indefinitely, using the new number.
22 is even, so we get 11, odd so 34, 17, 52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4,2,1….
As you’ll notice, starting with 7, you eventually reach the endless cycle 4,2,1.
Collatz’ conjecture states that for any natural number, by repeating these operations, you will eventually reach the number 1.
It is a conjecture as it has not yet been proven! It is however quite a fun problem to play with. There are a few applications of it, I haven’t read up on it in too much detail, but you can do your own reading on the wiki page (here) or just googling “collatz conjecture” (here).
After playing with it for a bit, you start to notice some patterns:
The first thing you may notice is that the end sequence is always 16,8,4,2,1 , so long as you don’t start with one of those numbers (if you do, it’s a fairly straightforward sequence). Now, why are these numbers so special?
The generator (the function that produces the next number) either takes the previous number and divides it by 2, or multiples it by 3 and adds 1. thus we can find the previous number by reversing this process, so if we want to find what number leads to 7 we would either multiply it 2 (reverse of dividing it by 2) or minus 1 and divide that by 3 (the reverse of multiplying by 3 and adding 1). From this, we can see that the only numbers that lead to 7 are
2 (3*2+1=7)
 14 (14/2=7)
However, we only multiply by 3 and add 1 if the number is odd, thus if we had the number 2 we would not then get 7 but rather 1. From this, we can see that the only number that leads to 7 is 14.
We can use this same process on the number 1 and follow it to see which numbers reach 1 (on the wiki page, I think this is called a recursive build or something).
So: to get to 1 we either divide by 2 or multiply by 3 add 1, so we need to solve
We can see that the only numbers that lead to 1 are
 2 (2/2=1)
0 (3*0+1=1),
 but 0 is even, hence it will just keep repeating itself. For this reason, when dealing with the Collatz Conjecture, we define 0 to not be a member of the natural numbers. (if it were, then Collatz conjecture would be false! That’s just an aside. As 0 would merely repeat itself, it’s not very interesting, and this is why I’m choosing to ignore it!)
So, the only number that leads to 1 is 2. Using the same method, we can determine that only 4 leads to 2. we can then see that 1 and 8 lead to 4, but as the sequence ends at 1, we find that only 8 leads to 4, and only 16 leads to 8.
Thus, the end sequence will always be 16, 8, 4, 2, 1 (if we don’t start with one of those numbers). What else we can notice is that if we reach the number 16, we will reach 1!
16 is obtained by 5 or by 32. What you may notice already is that any number that is a power of 2 will lead to 1. (a power of 2 is any number n=2k, where k is any natural number, so 4=22, 8=23,256=28). So if a sequence ever reaches a power of 2, it will reach 1.
 Now, as stated, 5 leads to 16. If you multiply 5 by a power of 2, that number will eventually become 5, which will become 16, which will then become 1….
Now, 5 can only be reached by 10, which can be reached by 20 or 3. as 20=5*22, we already knew it would lead to 1, so we ignore it for now. But 3 is a ‘new’ number, and the interesting thing is that 3 multiplied by a power of 2 will also eventually lead to 1!
It seems we’re starting to find some patterns. If you sit down with pencil and paper and, starting at 1, work backwards, using arrows to link numbers, you’ll notice that this pattern seems to happen a lot.  (here’s an image of what you can end up with, and here’s a link of what can happen to you if you do it for too long‼‼)
Now it would be great to introduce some definitions, but it will probably prove easier to look at this through an analogy:
Imagine a tree. Let the number 1 represent the roots of the tree, and let the main trunk represent all the natural numbers that are of the form 2k. so it will look like this:

 Now, as stated above, the number 5 leads into 16, so we can view this as a branch with a root of 5, which links into 16. Our tree will now look like this:

This can then be extended out to show the path of the numbers.
Eventually, you can end up with something that looks like this:
Which you can keep growing!
Now, if we look at the main trunk, we have already noted that it is simply all natural numbers 2 k, which is also 2k× 1. If we look at each branch, you will notice that each one can become a new tree of it’s own, with the main trunk having a root number, and then consisting of all natural numbers of the form 2k× the root.
Therefore, each branch has a root number, and consists of all natural numbers of the form 2k× the root, and has branches extending out of it at some points.
To keep things simple, I will keep the definitions similar to the analogy.
As you may notice, it is easy to find the numbers that form the branch once we know the root number, so the root’s are the most important information in the problem.
We can then number the branches (and hence the roots) by how far away they are from the main trunk. We will number the main trunk 1. All branches that lead into it will be numbered 2, all those that lead into those branches will be numbered 3 and so on. Thus we can refer to the set of branches of number p, and know that they are (p-1) branches away from the main sequence.
So, to clarify: we are talking about roots and branches, where the branches consist of all natural numbers of the form 2k× the root. The roots will then be referred to as the pth root, meaning that this root leads into the p-1 branch, and we will define it as root(p). the branches will then be branch(p), so that branch(p) is the sequence of numbers 2k × root(p).
Thus the number 40 is in branch(2) as it is 23× 5, and 5 is a member of root(2).
Before reading on, make sure you understand the above terms!
Now, via this definition, we can then see that root(p) does not refer to a single number, but rather a sequence of numbers. So therefore, numbers that are members of root(2) are 5,  21, 85, 341 etc (multiplying these numbers by 3 then adding 1 gives 16, 64, 256, 1028 etc respectively).
This therefore causes problems, as we are no longer looking for specific numbers, but rather looking for a pattern of numbers based on the distance away from the main trunk.
Bearing these facts and tools in mind, we can then begin to further explore the Collatz conjecture by looking at the root numbers… however, I have not quite completed this step yet! So, I will end this post here, and update it once I have gotten further in my own personal exploration. In the mean time, I encourage you to do your own searching – have fun!

One thought on “Collatz’ Conjecture

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s