## Friday, 4 May 2012

### Collatz Conjecture - a few observations

Here are a few thoughts on Collatz sequences (by which I mean the sequence of numbers you get by applying the rule "halve an even number, multiply an odd number by 3 and add 1") and why they seem to always reach 1. This isn't especially rigorous, just a few thoughts about patterns.

1) You can't have an infinite sequence of "upward steps"

If we start from an odd number, we can tell how many upward steps the sequence will take before a downward step. (An upward step is one where (3n+1)/2 is an odd number, for instance 15, 46, 23 where 23>15. A downward step is one where (3n+1)/2 is an even number, for instance, 17, 52, 26, 13 and 13<17).

If the starting number is X, we can calculate how many upward steps the sequence will take before a downward step by factoring (X+1). For each time 2 is a factor of (X+1), we will get one upward step. For instance, for 7, X+1 is 2^3 so we get three upward steps - 7, 22, 11, 34, 17, 52, 26. For 15 we get 4 upward steps (15, 46, 23, 70, 35, 106, 53, 160, 80).

Note that for the odd numbers in these sequences, the power of 2 in the factorisation of X+1 gradually decreases by 1 each time, and each factor of 2 is replaced by a factor of 3 in the next X+1 - 16 = 2^4, 24 = 2^3*3, 36 = 2^2*3^2, 54 = 2* 3^3, 81 = 3^4 - this process continues until all the factors of 2 have been replaced by a factor of 3 and we reach an odd number (meaning X is even).

This shows that you can't have an infinite sequence of upward steps without intervening downward steps.(I would say it proves it but I think it would need a more rigorous exposition of the reasons for this pattern to call it a proof).

2)You can't have an infinite sequence of downward steps

This is way too obvious to even mention, but of course the number of downward steps from the even number Y also depends on the power of 2 in the factorisation of Y. Each time you halve you lose one of the powers of 2. The only way you can get into a closed loop of numbers which are all pure powers of 2 is when you get to 4, 2, 1, 4, 2, 1 (seeing as how 1 = 2^0).

So we will always be alternating between sequences of upward and downward steps and the number of steps each way is determined by the power of 2 (of X+1 for odd numbers and in Y for evens).

OK, so that's all fun stuff, but unfortunately it doesn't rule out two ways in which you could have a Collatz sequence that never reaches 1 - A) an infinite loop which keeps passing through the same number Z (where Z isn't 1, 2, or 4). B) an infinite run of upward and downward steps which keeps climbing overall.

I think it must be especially hard to prove that the second of those two options isn't possible.