Sunday, 31 August 2014

Attempted proof

An attempt at a geometrical proof  that the proportion of level n Collatz numbers in a large region tends to 1 in 2(3^n)/3 of the outputs produced by the function described in my previous post.

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
(To recap, the Level 1 inputs to the function are 2^n-1 where 2^n > 4. 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 7/3, 5, 31/3, 21, 127/3, 85...
So the proportion of integer outputs is 0, 1/2, 1/3, 1/2, 2/5, 1/2, and this continues to alternate between p/(2p+1) and 1/2, with the value of p growing so that p(2p+1) tends towards a limit of 0.5

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

2. Level 2

To recap, level 2 inputs = 2^n - (1 + 2^m) where n > m+2. 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 can ignore the restriction q < 2^n/4).
 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 2, 4, 8, 7, 5, 1 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, 7, 5, 1, 2, 4, 8)

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 we will always contain 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/4. So now we need to consider only this triangle:

In this area we only have 3/21 (= 1 in 7) 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 3 in 21 - total proportion, 12 in 78 = 1 in 6.5.

Then we get:


 = 3 squares (6 in 36) and 3 triangles (3 in 21) = 27 in 171 = 1 in 6.33

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. But just to run through the maths . . .

Bearing in mind that each triangle or square is 6 powers of 2^n wide and tall - in this image there are 17 triangles and (16+15+....2+1) squares = 136 squares (6 in 36) and 51 triangles (3 in 21) = 1 in 6.058

This image is 17 columns wide. The formula for N columns is [N triangles and N(N-1)/2 squares].

The formula for the proportion of integer outputs here is (6 x the number of squares + 3 x the number of triangles) divided by (36 x the number of squares + 21 times the number of triangles) =
 [6N(N-1)/2 + 3N]/[36N(N-1)/2 + 21N] = 3N^2/(18N^2 + 3N) = N^2/(6N^2 + N)

N^2/(6N^2 + N)  tends up towards 1/6.

(For instance, at 1000 columns wide the proportion is 1 in 6.001)

I mentioned the best case scenario for the original triangle being 6 (typo corrected, this said 5) in 21 and the worst case being 1 in 21. In those cases the formulae would be:

(3N^2 + 3N)/(18N^2 + 3N) which tends down towards 1 in 6
(3N^2 - 2N)/(18N^2 + 3N) which tends up towards 1 in 6

So regardless of the pattern in the initial triangle the proportion of integer outputs in this pattern would have to tend 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 (or a cube, dissected by a plane through three of its corners), constructed from a series of triangles that fit together


The pattern is built up thus:

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

2^n =64
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

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+16, q(3) = 9+6+16
q = 1+4+16, q(3) = 9+12+16
q = 1+8+16, q(3) = 9+24+16


2^n=256
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+4  9+6+8
9+12+8

9+6+4    9+6+8      9+6+16
9+12+8  9+12+16
9+24+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
9+48+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 18 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 54 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

I think this demonstrates why this method has an error smaller than a Poisson distribution. However this obviously wouldn't solve all the problems with the method, such as:

1. What happens when q(3) is larger than the 2^n it is being subtracted from? From exploring this, I think that the outputs tend down towards -1 without ever reaching it, which would mean this isn't actually a problem, and that the first integer output from a level must be > 0. I haven't tried to write out a proof for this yet, but it should be easy to do.

2. 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 does at least help support a statistical argument that the Collatz conjecture is 'probably true'.

With regards to a proof, the thing that interested me about this method was that it can perhaps be used thus: we estimate how many levels we would need to test to be certain we can 'fill' a particular region of integers (and we allow sufficient room for error in this estimation). Then we show that we can always double this estimate each time we double the region. That's what I mean by a 'pigeonhole' process - not to prove that we must output each individual integer, but to show that if we assume we don't and that we could search every level without filling some of the regions, that leads to a contradiction. 

I'd like to talk more about that later, but for now I hope the attempted proof above gets us through the question of whether the estimates produced will tend towards a limit?

Tuesday, 26 August 2014

Collatz - a pigeonhole estimation approach.


nb Sept 1st - I'm going to put up an improved version of some of this soon as I think I've come to understand the later stages more clearly.

I’ve been working on the Collatz conjecture for a while – the approach below is an attempt to bring various strands together towards the vague outline of a proof. At the worst I think it works as a statistical approach to showing why the conjecture probably holds. But I wonder if the loose ends can be fixed to turn it into something closer to a proper proof? (I'll highlight the problem areas as I go along.)

I’ll start by describing a function, then explain its purpose.

1.     Any odd number p can be expressed as 2^n – q where 2^n is the first power of 2 higher than p.
2.     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
3.     Multiply each term in this series by a power of 3 with the power descending by one for each term (ending with 3^0).
4.     So in this case 1*9 + 4*3 + 32*1 = 53. We’ll call this number q(3).
5.     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.
6.     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 all 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


  1. Where this function produces a positive integer, it can be used to 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. The pattern of powers of 2 shows us the number of halving steps at each stage – in this case 2 halving steps, then 3.

This is more easily understood by leaving out the halving steps:

Instead of
17 -> 13 –> 5 –> 1
17 -> 52 -> 160 -> 512

(The rule at each step is to multiply by 3 then add the highest power of 2 that is a factor of the current number. So when we multiply 52 x 3 = 156 we add 4 since 156 = 39 * 4). So:

17 * 3 = 51
51+1 = 52 (Ignore the 2 halving steps to 13)
52*3 = 156
156 + 4 = 160 (ignore the 2 + 3 halving steps to 5)
160*3 = 480
480+32 = 512 (Ignore the 2 + 3 + 4 halving steps to 1)

Note that we add 1, then 4 then 32 (the elements of the q series above).

 (I can give more detail on why this works, but hopefully it is obvious).

8.     There are regular patterns of integer solutions for any given value of q.

For instance for q = 1

p = 3, r = 1
p = 7, r = 7/3
p = 15, r = 5
p = 31, r = 31/3
p = 63, r = 21

For q = 1, 1 in 2 values of p produces a positive integer value for r (These are the ‘level 1’ Collatz numbers, meaning the numbers that take one step to reach 1.)

For q = 3
q(3) = 3 + 2 = 5

(We’ll start at 16-3 for reasons I will explain in section 9) 

p = 13, r = 11/9
p = 29, r = 27/9 = 3
p = 61, r = 59/9
p = 125, r = 123/9
p = 253, r = 251/9
p = 509, r = 507/9
p = 1021, r = 1019/9
p = 2045, r = 2043/9 = 227

For numbers with two terms in q, 1 in 6 values of p produce a positive integer value of r, and the result is always a level 2 Collatz number (2 steps to reach 1)

Similarly for q = 9, q(3) = 3 + 8 = 11, we find positive integer values at

p = 119, r = 13
p = 8183, r = 909

As the number of terms in q increases the frequency is multiplied by 1/3 each time, while the Collatz level climbs by 1, eg:

For numbers with three terms in q, 1 in 18 values of p produce a positive integer value of r, and the result is always a level 3 Collatz number (3 steps to reach 1)

For numbers with four terms in q, 1 in 54 values of p produce a positive integer value of r, and the result is always a level 4 Collatz number (4 steps to reach 1)

And so on.

(These frequencies are easy to explain with a bit of modular arithmetic – add two consecutive powers of 2 to any integer and you reach the same value mod 3, add six and you reach the same value mod 9 etc.)

Nb. These rules are only reliable when used with the proviso given in section 9:

9.     The next step is to explore the pattern of positive integer results for all odd values of 2^n - q. However we immediately need to exclude some of these: Where the largest of the powers of 2 in q is 2^(n-2) (in other words a quarter of 2^n) the path identified is a repetition of a chain that can be expressed more simply. For instance:

2^n = 256, q = 81 = 1 + 16 + 64
q(3) = 9 + (3*16) + 64 = 121
(256 – 121)/27 = 5

The path described here is 5 -> 16 -> 64 -> 256
Which is equivalent to the Collatz chain 5 -> 1 -> 1 -> 1

Which can be expressed without the repetitions as
(16 – 1)/3 = 5
5 -> 1

We want to rule out these kinds of repetitions, so that each time we find a positive integer solution, it is the only solution for that particular positive integer.

So we are only going to look at values of 2^n – q  > 3(2^n)/4 (meaning that the largest term of q expressed as a series of powers of 2 is 2^n/8 or smaller.)

So the permissible values of 2^n - q will be:
7
13, 15
25, 27, 29, 31
49, 51, 53, 55, 57, 59,61, 63


etc.

  1. Next we want to sort these values  by the number of steps in the Collatz chain identified.           
To clarify this, the values of r for the numbers above are
7/3
11/9, 5
13/27, 25/9, 3, 31/3
Etc

Note that even the fractional results identify a Collatz chain of sorts (if we amend the rule so that we add one and halve until we reach an odd numerator).

If  we look at 13/27, this is the ‘Collatz chain’:

13/27 * 3 = 13/9

13/9 + 1 = 22/9

22/9 * ½ = 11/9

11/9 * 3 = 11/3

11/3 + 1 = 14/3

14/3 * ½ = 7/3

7/3 * 3 = 7

7 + 1 = 8

Which halves down to 1.

So 13/27 has a level 3 Collatz chain.


  1. Thus every value of r can be said to have a Collatz chain, although we are only really interested in the positive integer values of r. The next thing to note is that we can use Pascal’s triangle to describe the pattern of values of q:

Where 2^n – q is:
7
13, 15
25, 27, 29, 31
49, 51, 53, 55, 57, 59,61, 63

q is:
1
3,1
7, 5, 3, 1
15, 13, 11, 9, 7, 5, 3, 1
Etc

And when we express these as a sum of powers of 2, the number of terms (which is the same as the number of steps in the resulting Collatz chain) is:
1
2, 1
3, 2, 2, 1
4, 3, 3, 2, 3, 2, 2, 1

And the number of steps needed at each level is

1step 2steps 3steps 4steps
1
1          1
1          2            1
1          3            3            1

(For clarity - this means that for 2^n = 8 there is 1 level 1 colution. For 2^n = 16 there is 1 level 1 solution and 1 level 2 solution. For 2^n = 32 there is 1 level 1, 2 level 2, and 1 level 3 solution. For 2^n = 64 there is 1 level 1, 3 level 2, 3 level 3 and 1 level 4 solution etc).

This continues to build into Pascal’s triangle (because at each stage we add the same pattern ‘raised up by one level’).

  1. Next we are going to use values of 2^n – q to come up with an estimate of how many integer solutions there will be under a bound.  The bound is slightly messily defined, but bear with me as I think we can maybe solve the problems this causes.

First, let’s look at the region between 0 and 4.

Any level 1 integer solutions in this region must be generated by 1-step numbers for 2^n < 16 (because 8/3 < 4, but 16/3 > 4 – this is a rough rule of thumb which we will return to later).

If we look at Pascal’s triangle, we can regard the first row as representing integer solutions reached from 2^n – q where 2^n = 8, the second row represents integer solutions where 2^n = 16, the third row where 2^n =32 and so on.

For level 1 solutions in the region below 4, we look at row 1 and multiply by ½ (because 1 in 2 level one solutions are integers).

For level 2 solutions, we look at row 3 (because 32/9 < 4) and we total the number of 2 step solutions (row 1 = 0, row 2 = 1, row 3 = 2, total 3). Then we multiply this by 1/6 (because 1 in 6 level 2 solutions are integers).

We now have ½ + 3/6 = 1 meaning that we can very roughly estimate that there is at least one integer solution in this region and that it is level 1 or level 2. This of course isn’t definite as the numbers could conspire against us so that we haven’t yet reached either a level 1 or a level 2 solution. As it happens the estimate is spot on, because we have one level 2 solution (3). (Bear in mind that the method we are using will never find 1 as a solution, because of the exclusion explained in section 9.).

So, accepting that we have a slightly fuzzy estimation method, let’s move on to integers under 8.

  1. We use the same method but need to go through more levels to find an estimate that is sufficiently high to account for the number of integer solutions we are looking for.

Level 1 numbers (up to row 2 < 16/3) = 2/2
Level 2 numbers ( up to row 4 < 64/9) = 6/6
Level 3 numbers (up to row 5 < 128/27) = 10/18
Level 4 numbers (up to row 7 < 512/81) = 35/54
Level 5 numbers (up to row 8 < 1024/243) = 70/162

I’m going to make an ad hoc adjustment here. 2048/243 is bigger than 8. However for a level 5 number, we will be subtracting at least 81+54+36+24+16= 211 from 2048. And (2048-211)/243 < 8. So we can adjust to:

Level 5 numbers (up to row 9 = 2048/243) = 126/162

(Obviously this ad hoc adjustment reveals the level of fuzziness in our initial method, but bear with me for now).

So our first rough estimate of positive integers under 8 is

2/2 + 6/6 + 10/18 + 35/54 + 126/162 = 3.98

Thus we would expect there to be at least 3 level 1-5 integer solutions < 8. This is again correct – we have 3 (level 2), 5 (level 1) and 7 (level 5).(Note that we didn't actually have to go as far as level 5 to get an estimate > 3 - I'll return to this issue in point 15 below).

14. Before moving on to look at problems with the approximation, let’s look at a result for integers < 16
Level 1 numbers (up to row 3 < 32/3) = 3/2
Level 2 numbers ( up to row 5 < 128/9) = 10/6
Level 3 numbers (up to row 6 < 256/27) = 20/18
Level 4 numbers (up to row 8 < 1024/81) = 70/54
Level 5 numbers (up to row 10 < 4096/243) = 252/162
Level 6 numbers (up to row 11 < 8192/729) = 462/486


This totals to 8.08. Actually there are 7 integer solutions in this region: 3, 5, 7, then 9 (level 6), 11, (level 4), 13 (level 2) and 15 (level 5).

Then for integers < 32

Level 1 numbers (up to row 4 < 64/3) = 4/2
Level 2 numbers ( up to row 6 < 256/9) = 15/6
Level 3 numbers (up to row 7 < 512/27) = 35/18
Level 4 numbers (up to row 9 < 2048/81) = 126/54
Level 5 numbers (up to row 11 < 8192/243) = 462/162
Level 6 numbers (up to row 12 < 16384/729) = 924/486
Level 7 numbers (up to row 14 < 65536/2187) = 3432/1458

Total 15.88

What we actually find in this area is 13 Level 1-7 numbers plus 27 and 31 which are Level 41 and 39 respectively (as below).

Level 1 – 5, 21
Level 2 - 3, 13
Level 3 – 17
Level 4 11, 23
Level 5 - 7, 15, 29
Level 6 – 9, 19
Level 7 – 25
Level 39 – 31
Level 41 – 27

The positive thing to point out here is that the estimates for each level are pretty good. We have slight overestimates for Levels 2, 3, 4, and 7 and slight underestimates for levels 5 and 6, but all are in the right ballpark. I'll talk about the issues raised by 27 and 31 below.

15. It has to be admitted at this point that there are some obvious problems with this method. So let's take these in turn (and I'll admit some of my responses from here onwards are a bit hand-wavey). 

Firstly, the choice of how many levels to include in our estimate is clearly arbitrary. 

I'll defend this by pointing out that we are looking for the point at which this estimation method suggests that there are at least a certain number of positive integer solutions. If there are at least [(2^n)/2] - 1 positive integer solutions lower than 2^n, then the Collatz conjecture is true in this region because this method can't identify duplicates. We can use a version of the pigeonhole principle to explain this - if we have at least 15 odd integer solutions lower than 32 (or 511 less than 1024) then all odd numbers in this region have a Collatz chain to 1 as we can't have two solutions for the same integer.

16. Second problem - the upper bound on the estimate is ragged. While we are looking for solutions < 32, 64/3 is only 21.333, 256/9 is only 28.444 and so on. So our method for finding solutions under 32 is actually looking for solutions under a ragged boundary in the 16-32 range. However, when we go from our estimate for 2^n to our estimate for 2^(n+1) we are clearly doubling our range, so I'd argue that so long as we can keep on doubling the estimate each time, we are still showing that there will always be sufficient integer solutions to 'fill every pigeonhole'.

17. Third problem. For certain values of q, we end up getting negative solutions. For instance we already saw this instance:

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

For these, we can simply shift our starting point up by a power of 2 (or as many as it takes to reach a positive solution. For instance (128 - 65)/81 gives us a positive solution lower than 64/81. Slightly ad hoc, but it means that our original estimate is a slight underestimate (since higher values of 2^n yield a wider range of values of q).

nb I'm increasingly tempted to conclude that this isn't even as much of a problem as I assume above, as it seems like it's impossible to get a negative integer solution and thus we don't need to allow for any such adjustment. I'm not sure on this yet though.

18. Fourth problem. While the estimate of 1 in 2 level 1 numbers is perfectly accurate, the estimation method is less good for other levels, where the range of values of q is more complex. We saw in point 14 that we had overestimates for some levels and underestimates for others. My suggestion here would be that for any given level, the estimation is a limit towards which the actual quantity of solutions tends. There is a  high degree of regularity within the solutions - for instance for level 3 solutions, any value q will produce an integer solution for 1 in 18 values of 2^n. But we also have 'horizontal' sorting, where (for instance) 1 in 18 of this series has to produce a solution for 2^22 - q, 2^23 - q etc

q = 9+6+2^19
q= 9+12+2^19
q = 9+24+2^19...
etc

And in general, since for any value of q we have 1 in 18 values of 2^n producing a solution, we must be tending towards 1 in 18 solutions for all values of q once we have a large number of values to consider.

19. Fifth problem - how do we account for outliers, like the level 41 and 39 numbers (27 and 31) below 32.
I'm not sure this is really a problem. I'm not claiming the original estimation method is perfect, only that it shows we will always have sufficient solutions. Where a high level gives us an 'unexpectedly' low solution, it simply means we don't need to go up as many levels to find 'sufficient solutions' from the lower numbers. Also, outliers will go on to produce a pretty well sorted range of solutions for lower levels - 27 gives us all the 4n+1 numbers which have the same ongoing Collatz chain - 109, 337 etc. And it also gives us the level 40 number (41), level 39 (31), level 38 (47) and so on - meaning that once this chain has worked its way through the system, we still end up with a pretty even spread of levels.

20. Sixth problem. I haven't actually shown that we always have 'sufficient solutions'. This seems self-evident from looking at the way patterns develop within Pascal's triangle - lower levels increase their hit rate at less than 2 for each increase in 2^n, while higher levels increase their hit rate at more than 2. So as long as we can add extra levels to our estimation method we should be able to double the estimate. It looks self-evident that we can always find at least (2^n/2)-1 solutions but I know this would need to be shown to be necessary. 

But for now I wonder if anyone has any thoughts on the basic method outlined above...


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)
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.