A binary representation of the Collatz conjecture

Here is a restatement of the Collatz conjecture expressed in binary numbers. It is a compression and extension of recent posts on this subject which I think gives a bit more clarity.

First I’ll explain the method, then I’ll explain why it works.

I.                    Starting from any odd number N, write it down in binary, but turn the final 1 into a 0 (in other words write down the even number N – 1.

II.                  Next, add 2N – which is just N with an extra zero on the end.

III.                Now, mark the final 0 of the resulting number with an X so you don’t ‘use it again’ next time (but continue to treat it as a zero). Also ignore any 1s to the immediate left of that number. The remnant of the binary number will be a new even number. This is the active part of the number. For instance, if you have 1100111X – the even number is 1100.

IV.                Change the zero at the end of this even number to a 1 and add a zero at the end -> 1010. Then add as many zeros as there are 1s and Xs at the end of the previous number you reached, then add the result to the previous number. For instance, to 1100111X, add 110100000

V.                  Repeat steps III and IV. Keep doing this until you have no zeros left – this will give you the Collatz chain for N (I’ll explain how after the example).

So the Collatz conjecture can be restated thus – repeating this process will always lead to a number with no remaining zeros.

I’ll run an example for N = 7

N-1 = 110

2N = 1110 (=2x7)

110

+ 1110

10100

Mark last zero X  ->  1010X

Add 101100 (note that 1011 = 11)

1010X

+ 101100

100000X

Mark last zero as X  ->  10000XX

Add 10001000 (note that 10001 = 17)

10000XX

+ 10001000

110010XX

Mark last zero as X  ->  11001XXX

Add 110100000 (note that 1101 = 13)

11001XXX

 + 110100000

1001101XXX

Mark last zero as X  ->  10011X1XXX

 Add 10100000000 (note that 101 = 5)

10011X1XXX

+ 10100000000

111011X1XXX

Mark last zero as X  -> 111X11X1XXX

No zeroes remaining

OK, so what is happening here? I’ve mentioned before that we can do two things to a Collatz chain. First, if you ignore the halving, you can express the chain thus:

(3^n x X) + 3^(n-1) + [2^a x 3^(n-2)] + [2^b x 3^(n-3)] …. + [2^c x 3]+ 2^d = 2^e

The calculation can be of any length (as indicated by the dots) but must fit two requirements:

1)      The power of 3 falls by one in each term, until we reach 2^n x 3 in the penultimate term.

2)      The power of 2 increases in each term but can rise by more than 1 at a time – so in the example above e>d>c>b>a.

For instance, the chain for 7 would be

7*243 + (1x81) + (2x27) + (4x9) + (16*3) + (128x1)  = 2048

Secondly we can find an equivalent chain that uses the same powers of 2 – but not multiplied by powers of 3 - to reach the same total.

For instance the equivalent for the above chain is

1897 + 1  + 2 + 4 + 16 + 128 = 2048

I have previously explained that to find this equivalent chain, we can use the system below:

A+1
B+1+2^p
C+1+2^p+2^q
D+1+2^p+2^q+2^r (where r > q > p)

p, q, r are defined by the power of 2 you need to add to reach a multiple of the highest power of 2 possible. For instance, from 36, adding 2 gets you to 19 x 2, adding 4 gets you to 5 x 8, adding 8 gets you to 4 x 11, adding 16 gets you to 4 x 13 and so on – so you need to add 4.

To get from A to B etc, you add the first term to twice the full equation. For instance:

A + 2(A) = B

B + 2(B+1) = C

C + 2(C+1+2^p) = D

Etc. Here is the worked example.

7

21+1=22 (=11*2)
21+(2*22)=65
65+1+2 = 68 (=17*4)
65+(2*68)=201
201+1+2+4=208 (=13*16)
201+(2*208)= 617
617+1+2+4+16 = 640 (=5*128)
617+(2*640)=1897
1897+1+2+4+16+128 = 2048

Now, the binary method given above is simply a cleaner way of doing the exact same thing. At each step we add the next number in the Collatz chain x 2^n.

In the chain above we ended up with 111X11X1XXX

11101101000 = 1896 – or if we replace the last digit with a 1 it is 1897.

There is a reason for this apparent ambiguity. If instead of starting from 6 we had started from 7 and tripled it, then followed the rest of the path above, then we would have replicated the method above. However, if we had reached 7 from a precursor in a Collatz chain, we would have reached a number where the active digits were 110. For instance, if we start at 9 and use the binary method above:

9 = 1001

N-1 = 1000

2N = 10010 (=2x9)

1000

+ 10010

11010

Mark last zero X  ->  1101X

The active part of this number is 110..

                                                                                   

If we continue the process we will reach the same number 11101101000 but with an extra 1X on the end (the last 2 digits of 1101X). And the equivalent number for any chain that passes through 7 on the way to 1 will also start with 11101101000.

This is a number to which we need to add 1 + 2 + 4 + 16 + 128 to reach a number without zeroes. (each of the zeroes or Xs mark a power of 2 we would need to add to reach this)

A number without zeroes is one less than a power of 2. If we then add 1 more (because in fact the chain started with N, not N – 1) we reach a power of 2. This is why a number with no zeroes marks the end of the chain, the point at which a normal Collatz chain reaches 1.

I'll make a few observations on what this method shows us in another post.