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
(=2x

**7**)
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 + (

**1**x81) + (**2**x27) + (**4**x9) + (**16***3) + (**128**x1) = 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)

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

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
(=2x

**9**)
1000

__+ 10010__

11010

Mark last
zero X ->

**110**1X
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.

## No comments:

## Post a Comment