Whilst fooling around with Haskell, I came across the Collatz Conjecture …
The Collatz function f is defined by
f(n) = n/2 if n is even
f(n) = 2n+1 if n is odd
n is any positive integer. The conjecture is that for any starting value n0, a repeated application of f will reduce to 1. i.e. given n0 there exists a j such that f^j(n0) =1.
I thought it would be fun to experiment with it, but I don’t think it’s worthwhile me spending much time on it, as it has been unsolved for a long time. It is therefore the province of krank mathematicians, like squaring the circle.
But I thought I’d chip in my morning coffee thoughts on the problem …
It is certainly true that if f^j(n0) = 2^a for some a, then f^(j+a)(n0) = 1. It seems that all sequences must conform to 2^a eventually, although this is unproven. What I did notice is that if you have a number of the form: F1: 2 ^(2m) + 2^(2m-1) + … + 1 for any m,
then the next number in the sequence has the form 2^a. I haven’t proved that, yet, though.
Now, given any number n, it is trivial to establish that it has the form: F2: n = 2^m0 + 2^m1 + … 2^mj
for some j such that 0 < m1 < … < mj
We can then, in effect, write any number in as a binary vector: F3: b = [b0, b1, …, bj]
where bi is either 0 or 1 for 0<=i<=j
When b0 =0, it is true that
f(b) = [b1, …, bj]
So the interesting cases are when b0 = 1.
What the next questions to answer would be as to how bit patterns propagate under the odd case, and whether there is some metric on the length of the vector that determines its “compexity”. Let me call that metric, the “Hamming length”, for a want of a better phrase. Let me denote it by H.
I’m thinking out loud here, but suppose we have a number of the form, m = 2^a .
Then H(m) = 1, perhaps. In other words, although the number is large, it is effectively reducable to the number 1. Now let’s take another number of the form: m = 2^a +1.
This time H(m) = a, because you would need quite a lot of vector space to write the number. Now, m is odd. Note now that f(m) = 2^(a+1) + 2^a + 4 = 4*(1+ 2^(a-2) + 2^(a-1))
aha. Now in this case H(f(m)) = a-1. So the Hamming length is reduced by an application of f.
*IF* we could convince ourself that the Hamming length is always reduced (and I’m not sure that it is), then we are effectively on the home straight, because any number for which H(m) = 1 will be trivially reducable.
Anyway, just some ideas, it’s prolly all nonsense.
Update 22-Mar-2015: Oh, the vanity. After further mucking around, I discovered that what I’ve said is almost entirely nonsense. Looking at the binary numbers that are generated are interesting, though. What seems to happen is that the Hamming length does get longer, but it also tends to propagate 0’s towards the least significant bits. This then leads to making big reductions. So I think cycles can be arbitrarily long. Each application of f can make the Hamming length longer. So maybe it’s a case of working out an upper bound on the Hamming length before a dequence of repeated applications, and then seeing how that compares to the Hamming length when you get a string of 0s. Is the Hamming length necessarily shorter? I wonder what the bit pattern for a “maximal cycle” for integers less than 2^a would look like. Are they even unique? No doubt thousands of thousands of people and real mathematicians have been working on this problem, so perhaps it is unlikely in the extreme that a few methods of attacks that have come to my mind haven’t been thought of before. Hey ho.