Monday, 20 October 2014

Level n numbers tend to 1 in 2(3^n)/3 of the outputs produced by the 'pqr function'

An attempt at a geometrical proof  that the proportion of level n Collatz numbers in a very large region tends to 1 in 2(3^n)/3 of the outputs produced by the 'pqr function'

This is what I am calling the 'pqr function' (for want of a better name)

  •  Any odd number p can be expressed as 2^n – q where 2^n is the first power of 2 higher than p.
  •  Express q as a series of powers of 2 in ascending order. For instance, where p = 475 (and 2^n = 512), q = 37 = 1 +  4 + 32
  • Restrict the inputs to this function to numbers q < 2^n/8
  • Multiply each term in this series by a power of 3 with the power descending by one for each term (ending with 3^0).
  • So in this case 1*9 + 4*3 + 32*1 = 53. We’ll call this number q(3).
  • Subtract q(3) from 2^n and divide by the next highest power of 3. So in this case (512 – 53)/27 = 17. We will call this result r.
  • Here are two more simple examples of this function.

15 = 16 – 1
q(3) = 1
(16 – 1)/3 = 5
So r = 5

1897 = (2048 – 1 – 2 – 4 – 16 – 128)
q(3) = 81 + 2*27 + 4*9 + 3*16 + 128 = 347
(2048 – 347)/243 = 7

The examples above result in positive integer solutions. However, most instances of this function result in fractional or negative solutions.

For instance:

49 = 64 – 1 – 2 – 4 – 8
q(3) = 27 + 9*2 + 4*3 + 8 = 65
(64 – 65)/81 = -1/81

27 = 32 – 1 – 4
q(3) = 3+4 = 7
(32 – 7)/9 = 25/9

Where this function produces a positive integer, it can be used to uniquely identify a Collatz chain from that integer to 1.

For instance take the first example above

475 = 512 – 1 – 4 – 32
q(3) = 9 + 3*4 + 32 = 53
(512 – 53)/27 = 17

What this tells us is that from 17 there are three tripling steps in the Collatz chain to 1.

If there are n steps from an integer to a power of 2, we will call that integer a Level n number.

Here is why this function doesn't produce duplicate outputs. Every integer that has a level n solution also has a solution for all higher levels. For instance 5 = (16-1)/3 = (64-3-16)/9 = (256-9-48-64)/27 etc. However after the first solution, the additional solutions all have q > 2^n/4 so these do not get output when we restrict inputs to q < 2^n/8

First I'm going to show how Level 1 and Level 2 integer outputs from the function tend to limits of 1 in 2 and 1 in 6, then I want to extrapolate from this to higher levels.

1. Level 1
Level 1 inputs to the pqr function are 2^n-1 where 2^n > 8. The outputs are (2^n-1)/3)
2^n numbers alternate between 1 and 2 mod 3
So 2^n - 1 alternates between 0 and 1 mod 3.
When 2^n-1 = 0 mod 3 the output (2^n-1)/3) is an integer.

The series of outputs is 5, 31/3, 21, 127/3, 85...
So the proportion of integer outputs is 1, 1/2, 2/3, 1/2, 3/5, 1/2, 4/7 ... , which oscillates between 1/2 and the series p/(2p-1) which tends towards 1 in 2.

Therefore the proportion of Level 1 integers output by level 1 inputs tends towards 1 in 2 .

2. Level 2

Level 2 inputs = 2^n - (1 + 2^m) where n > m+3. The outputs are (2^n - (3 + 2^m))/9

First, here is a 6x6 grid of integer outputs from a calculation of this sort (to start with we will ignore the restriction q < 2^n/8).

 2^n increases along the horizontal axis. q increases down the vertical axis.

9 is a power of 3.

Every prime power (except powers of 2) has a primitive root; thus the multiplicative group of integers modulo 3n is cyclic. (I've quoted this - I hope it is the right terminology - in this case what I mean is that as we double from 1 mod 9 we will pass through each residue class mod 9 other than multiples of 3 before returning to 1).

The series of 3+2^m values (the q(3) column in the grid) is congruent to this cycle - with values of 5, 7, 2, 1, 8, 4 mod 9

When we subtract these values from a particular value of 2^n we get either a cycle through the 0 and 1 mod 3 numbers or a cycle through the 0 and 2 mod 3 numbers.

Therefore 1 and only 1 number in each column in a 6x6 grid  =  0 mod 9.

The horizontal series of 2^ n numbers is also congruent to the same cycle (in this case, 5, 1, 2, 4, 8, 7)

Therefore when we subtract any given (3+2^m) from the 2^n series we also get either a cycle through the 0 and 1 mod 3 numbers or a cycle through the 0 and 2 mod 3 numbers.

Therefore 1 and only 1 number in each row in a 6x6 grid =  0 mod 9.

Therefore a square 6x6 grid of this sort will always contain 6 in 36 (=1 in 6) integer outputs.

However, the grid above contains numbers that aren't permissible inputs, since our function is restricted to inputs where q < 2^n/8. So now we need to consider only this triangle (the numbers that aren't crossed out:

In this area we only have 4/21 (= 1 in 5.25) integer outputs. (The 'worst case scenario' would be 1/21, with one integer output in the top right corner and the rest in the 'restricted zone - while the 'best case scenario' would be 6 in 21 down the central diagonal).

However, when we continue to develop the pattern we get this:

The square has 6 in 36, each triangle has 4 in 21 - total proportion, 14 in 78 = 1 in 5.57

Then we get:

 = 3 squares (6 in 36) and 3 triangles (4 in 21) = 30 in 171 = 1 in 5.7

And eventually we get a pattern more like this:

It's obvious from looking at this that the area in which the proportion of the area filled by squares rather than triangles is increasing as it is similar to the way that calculus uses rectangles under a curve to approximate area.And the squares have a ratio of 1 in 6 integer results, so the ratio for the whole triangle tends up towards 1 in 6.

Level 3.

At level 3 (and subsequent levels) we get a similar pattern in 3 (and higher) dimensions. We can visualise the initial level 3 pattern as a tetrahedron constructed from a series of triangles that fit together

The pattern is built up thus:

2^n = 64
q = 1+2+4, q(3) = 9+6+4

2^n =128
q = 1+2+4, q(3) = 9+6+4
q = 1+2+8, q(3) = 9+6+8
q = 1+4+8, q(3) = 9+12+8

q = 1+2+4, q(3) = 9+6+4
q = 1+2+8, q(3) = 9+6+8
q = 1+4+8, q(3) = 9+12+8
q = 1+2+16, q(3) = 9+6+16
q = 1+4+16, q(3) = 9+12+16
q = 1+8+16, q(3) = 9+24+16

q = 1+2+4, q(3) = 9+6+4
q = 1+2+8, q(3) = 9+6+8
q = 1+4+8, q(3) = 9+12+8
q = 1+2+16, q(3) = 9+6+16
q = 1+4+16, q(3) = 9+12+16
q = 1+8+16, q(3) = 9+24+16
q = 1+2+32, q(3) = 9+6+32
q = 1+4+32, q(3) = 9+12+32
q = 1+8+32, q(3) = 9+24+32
q = 1+16+32, q(3) = 9+48+32

When these are arrayed in a series of triangles we get:


9+6+4  9+6+8

9+6+4    9+6+8      9+6+16
9+12+8  9+12+16

9+6+4      9+6+8       9+6+16    9+6+32
9+12+8    9+12+16  9+12+32
9+24+16  9+24+32

Once again the vertical and horizontal rows and columns (as well as the series 2^n - q(3) for each value of q) must be cyclic, this time through the values of 27 (excluding multiples of 3). So 1 in 18 in each row and column must be an integer output.

And as we expand the pattern beyond the 18th power of 2 we get a series of cubes within which the 18x18x18 grid must contain exactly 18x18 integer solutions: just as in this badly drawn diagram.

As the overall shape grows larger, we can fill more of the volume with cubes and less with pyramids:

So again, the proportion of integer outputs will either tend up towards 1 in 18 or down towards 1 in 18 depending on whether the initial pyramid pattern has more or less than 1 in 18.

Level 4 and beyond:

We can visualise larger versions of the pattern by projecting a series of the level 3 pattern, then a series of series etc: Here is what the level 4 pattern will look like:

Again, there is an initial 'triangular' pattern in which we can have more or less than 1 in 54 integer solutions. And again, because doubling mod 81 is also cyclic, we can fill an increasing proportion of the space with 54x54x54x54 cuboids (with exactly 1 in 54x54x54 integer solutions) as the pattern develops.

And we can extrapolate a similar pattern for any level n. Level 5 could be depicted by a growing series of the diagram above. Level 6 could be depicted by a growing series of the Level 5 diagram. And so on. In each case the volume can be filled by an increasing proportion of n-dimensional cuboids.

Therefore the proportion of level n Collatz numbers in a large region tends towards 1 in 2(3^n)/3 of the outputs produced by the function.

Final thoughts

Clearly if we are trying to exactly 'count' all integer outputs, then an error term of even 1 in a trillion is too high. Though if the proportions do tend to 1 in 2, 1 in 6 etc, it might at least help support a statistical argument and I think there may be strategies for using this method that don't strictly rely on counting.

I can explain more about this latter train of thought, but I want to keep this post as simple as possible for now.

Thursday, 24 October 2013

A binary representation of the Collatz conjecture part 2

We can make several probabilistic observations from this method. And also there are a few things that we can note about the way the patterns develop (I’ve mentioned these in previous posts, but I think using binary gives more clarity).

I will summarise these quickly here but will give more detail on some of these thoughts later. I think a lot of this stuff would also apply to any binary attempt at Collatz, so suspect it isn't too groundbreaking, just interesting to see how it works.

1. If the active part of the number ends 111110 (any number of 1s) then these digits will end up as 000000. So 10 -> 00, 110 -> 000 etc.
2. If the active part of the number ends 01010100 (any number of 01s) then these digits will end up as 11111110
3. If the active part of the number ends 0000000 (any number of 0s) then these digits will end up as 0101010
4. At each stage we mark one digit with an X, reducing the active part of the chain by 1 digit. We may also skip any number of 1s to reach the next 0 – this further reduces the active part of the chain by however many 1s we skipped.
5. At each stage the whole binary number is extended by 1 or 2 digits (for an infinite chain we would need this to stay below about 1.6)
6. Any 1s that remain in the non-active part of the chain represent a skipped 1. However long the initial chain, the last zero will ‘catch up’ with the start of the chain if the number of skipped 1s is more than the amount by which the extra digits exceed 1 per step. So, say we start from a 20 digit number. After 100 steps we will have reach (approximately) a 180 digit number, and we will have 100 Xs. If we have in addition skipped a one 80 times, then we must have reached a number without any zeroes.
7. So if this chain doesn’t reach 1 (eg is a counterexample to the conjecture) we need to have a number that has more zeroes than 1s in the non-active part – in fact we need the proportion of 1s to stay below about 40%.
8. This isn’t actually very surprising since it is equivalent to a well known probabilistic result – on average we would expect each step in a Collatz chain to halve twice (since the average number of factors of 2 among all even numbers is 2). A binary number with 50% 1s and 50% 0s is equivalent to a chain with an average of two halvings per step. This is also equivalent to a chain that is falling in value and thus one that must eventually reach 1.
9. The final thing which I find really interesting is that if we isolate any number within the binary chain, that set of digits will behave the same way as if we started from that number, as long as they remain active. (for instance if we have a number 10100110 then the last 3 digits will behave the same as the last three digits of the chain for 7 given in the previous post). This gives us a rather stronger probabilistic approach – since all ‘small numbers’ eventually lead to 1, we can probably assume that an average section of their hailstone sequence is downward. The binary representation of a very large number contains a large number of smaller numbers if we isolate these. The digits for these numbers will behave the same way as a section of their own hailstone sequence, so this gives us a fairly strong reason to expect the overall sequence to contain the same proportion of 1s and zeroes as the smaller numbers, which would mean it also has to reach 1 eventually. Of course, as with any probabilistic approach this can’t rule out the numbers ‘conspiring’ in such a way as to produce a counterexample. So to get from here to a proof would involve more than just probabilistic speculation.
10. One possible approach might consist of running this binary addition backwards. This can be done, for instance you can show that 100X can only be reached from 11X + 10 (though it’s a bit fiddly for bigger numbers…) But one would need to prove that starting from a chain of 1s you can reach any even number. Which is probably no easier (or different to) the original conjecture so not sure it helps.

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)
+ 1110
Mark last zero X  ->  1010X
Add 101100 (note that 1011 = 11)
+ 101100
Mark last zero as X  ->  10000XX
Add 10001000 (note that 10001 = 17)
+ 10001000
Mark last zero as X  ->  11001XXX
Add 110100000 (note that 1101 = 13)
 + 110100000
Mark last zero as X  ->  10011X1XXX
 Add 10100000000 (note that 101 = 5)
+ 10100000000
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:

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.

21+1=22 (=11*2)
65+1+2 = 68 (=17*4)
201+1+2+4=208 (=13*16)
201+(2*208)= 617
617+1+2+4+16 = 640 (=5*128)
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)
+ 10010
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.