## Monday, 7 October 2013

### Collatz - one more little bit...

I just want to explain a bit about how it works when powers are skipped. I gave this example in the last post (the start of a much longer sequence):
55
165+1
497+1+2
1497+1+2+4
4505+1+2+4+32
Here's one way of seeing what happens at the next stage, we compare the mod values of the next two powers - if they are different we don't skip, if they are the same, we skip:

55 (1 mod 2, 3 mod 4, don't skip 2)
165+1 (1 mod 4, 5 mod 8, don't skip 4)
497+1+2 (1 mod 8, 1 mod 16, skip 8)
1497+1+2+4 (At this stage it is more complicated - by adding 1+2+4 we reach a multiple of 32 so can skip 16 as well.)

Here's a slightly better way I found to look at this:

55 = 56-1
Now, we get to the next number by multiplying the first term by 1.5 and doubling the second, then subtracting the next power of 2:
(84x2)-1-2 = 165
And again
(126x4)-1-2-4 = 497
And again
(189x8)-1-2-4-8 =1497
However, because 189 is odd, we can also express this as
(95x16)-1-2-4-16
Or as
(48x32)-1-2-4-32
But we can't skip 32 because 48 is even.
48x32 = 1536

The first terms above are actually one more than the Collatz chain 55, 83, 125, 47. To find out what happens next, we can look at 1497 - this is 64n-39, but also 128n-39, 256n-39, and 512n-39. This means that after 32 we will be adding 64, 128 and 256 before we can skip 512. Honest, this does work, though it's a pain to try and explain why without writing a pamphlet.

4505+1+2+4+32 = 71 x 64
13593+1+2+4+32+64 = 107 x 128
40985+1+2+4+32+64+128 = 161 x 256
123417+1+2+4+32+64+128+256 = 121 x 1024
371225+1+2+4+32+64+128+256+1024 = 4192 x 91

Obviously the numbers involved get unwieldy and large very quickly, but it is the logic of how these chains work that interests me.

Edit:

One more thing worth a quick look - what happens when we reach a power of 2? Well, the chain looked at this way keeps climbing, but we skip a power of 2 each time. So:

5
15+1= 16
15+16+16=47
47+1+16=64
47+64+64=175
175+1+16+64=256
175+256+256=687
687+1+16+64+256=1024
And so on

It's interesting to note that the sequence tends down towards 2/3 of the power of 2 that the equation reaches. For instance

47/64 = 0.734
175/256 =  0.684
687/1024 = 0.671
This ratio will converge down towards 0.666.