Collatz - restated without the halving.

Here's the way of reformulating Collatz chains that I have been using. This gives us a way to express the conditions for 1) the existence of a loop and 2) the conjecture being true.

Start from n, any odd number

Step 1.
Multiply by 3 and add 1 = 3n+1

 Step 2
Multiply by 3 = 9n+ 3
Factor as (2^a)(an odd number)
Add 2^a = 9n+3+2^a
 
Step 3...
Multiply by 3 = 27n + 9 + 3(2^a)
Factor as (2^b)(an odd number)...
Add 2^b = 27n + 9 + 3(2^a) + 2^b

Repeat until we reach 2^z(n) or 2^z

As the total increases, the cumulative total is

[3^y x n] + [3^(y-1)] + [2^a x 3^(y-2)] + [2^b x 3^(y-3)] …. + [2^c x 3]+ 2^z...

The power of 3 falls by one in each term, until we reach 3^0 in the final term
The power of 2 increases in each term but can rise by more than 1 at a time – so in the example above d>c>b>a.

If the Collatz conjecture is true, we will always reach an equation of the form

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

For there to be a 3n+1 loop, which would be a counterexample to the conjecture, we would need this equation to be true:

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

We can adapt this method for 5n+1 chains by replacing all the 3s with 5s.

An attempted proof that there are no Collatz loops higher than 1, 4, 2

I think I've spotted the flaw in this, but will leave it up below for now.

To explain very briefly, I find two different ways to approximate the gap between the lowest element in a reduced Collatz chain and the highest. One suggests it is 'nearly' 2^(x-y). The other shows it must be less than 2/3 x 2^(x-y).

Then I look at how this condition can be met  (or actually not quite met) for the negative loops (and how the 5n+1 loops can reach < 2/5 x (2^x - 5^y)). From this I erroneously conclude that in this equation for the lowest element

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

we need one of these elements

[3^(y-1)] + [2^a x 3^(y-2)] + [2^b x 3^(y-3)] …. + [2^c x 3]+ 2^d

to be > 1/3 of the total sum in order for the ratio from lowest to highest element to be less than 2/3 x 2^(x-y).

This is how for instance the 5n+1 chain from 13 works:

125(13) + 25 + 10 + 4 = 128(13)
125(83) + 25 + 160 + 64 = 128(83)

The ratio is less than 2/5 * 2(x-y) in spite of the fact we multiply the second two elements by 2(x-y) because 25 is the largest element and is the one element that doesn't increase from 1110000 to 1000011. So it is possible to get to 16 x 13 with one more (5n+1)/2 step.

The flaw I've spotted is that the most efficient way for this ratio to increase by less than 2^(x-y) is actually if the zeroes are extremely evenly distributed instead of the largest element not increasing at all. Something like

11011011011011011000

would mean that every other 1 only increases by 1/2 (2(x-y) which could be enough to keep the total beneath 2/3 2^(x-y), This has a larger impact than one single element not increasing at all.

This is actually how the reduced 5n+1 loop from 17 - 41 - 108 works. 1101000 changes to 0100011

125(17) + 25 + 10 + 16 = 128(17)
125(108) + 100 + 160 + 64 = 128(17)

Both the first and last element increase by x4 instead of x16, and as a result the total increase is < 2/5(16)

So I'm not there. Here it is anyhow, and I'll see if that problem is fixable.


Method
First we examine some actual loops (one using the 5n+1 rule instead of 3n+1 and two using negative numbers) to establish characteristics that must be present in a loop.
Then we analyse how these would apply to positive numbers using the 3n+1 rule and show that above a certain threshold these characteristics can't be present.
Simons & de Weger have shown there is no k-cycle up to k = 68. This is used to show that the threshold for these characteristics is unachievable.

I.

If we replace 3n+1 with 5n+1 in the Collatz method, then 13, 33, 83 is a loop.

The full cycle is 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13
In this cycle we have 3 upward (5n+1) steps and 7 downward (halving) steps.
I will be using the following notation to represent this in 'binary' form thus: 1110000

(Read from left to right, Each 1 represents one upward step followed by one halving. If it is followed by 0, each zero before the next 1 represents an additional halving step.)

So depending on whether we start from 13, 33, or 83, the loop can be represented thus:
1110000
1100001
1000011

II.

We can also express this loop using a formula similar to the one often derived for the 3n+1 conjecture:

For there to be a 3n+1 loop we would need this equation to be true:

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

The power of 3 falls by one in each term, until we reach 2^n x 3^0 in the final term
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.
To compute a series like this:
Start from an odd integer n

Step 1
Multiply by 3.
Add 1

Step 2
Multiply by 3
Factor as (2^a)(an odd number)
Add 2^a
 
Step 3...
Multiply by 3
Factor as (2^b)(an odd number)...
Add 2^b

Repeat until we reach 2^z(n)

We can adapt this method for 5n+1 loop by replacing 3 with 5 throughout

(see appendix A for more explanation if this isn't clear):

So for 13, 33, 83 we can express the Collatz chains as:

5^3(13) + 5^2 + 5(2) + 4  = 2^7(13)
5^3(33) + 5^2 + 5(32) + 64  = 2^7(33)
5^3(83) + 5^2 + 5(32) + 64  = 2^7(83)

Rewrite as:

13(2^7 - 5^3) =  5^2 + 5(2) + 4
33(2^7 - 5^3) = 5^2 + 5(32) + 64
83(2^7 - 5^3) = 5^2 + 5(32) + 64

Let n = the starting number in any loop
Let y be the number of upward steps in a loop from n to n
Let z be the number of halving steps in a loop
Let v represent the right hand side of these rewritten equations and v(n) represent the right hand side of this equation for n - in other words the difference between 2^z(n) and 5^y(n).

So in the equations above, v(13) = 39, v(33) = 99, v(83) = 249

III.

From II, for any n that is part of a 5n+1 loop

n(2^z - 5^y) = v(n)

Note this also works for the 5n+1 loop 1, 3

v(1) = 1(32-25) = 5+2 = 7 
v (3) = 3(32-25) = 5+16 = 21

The loop from 1 is 25(1) + 5 + 2 = 32(1)
The loop from 3 is 25(3) + 5 + 16 = 32(3)

IV.

Similarly for a 3n+1 loop:

n(2^z - 3^y) = v(n)

We can test this on a few 3n+1 loops:

For the trivial loop 1:

1(16-9) = 3+4

For the loop -5, -7

-5(8-9) = 3+2
-7(8-9) = 3+4

For the loop -17, -25, -37, -55, -41, -61, -81

-17(2048-2187) =  729 + 2(243) + 4(81) + 8(27) + 32(9) + 64(3) + 128
-25(2048-2187) =  729 + 2(243) + 4(81) + 16(27) + 32(9) + 64(3) + 1024
-37(2048-2187) =  729 + 2(243) + 8(81) + 16(27) + 32(9) + 512(3) + 1024
-55(2048-2187) =  729 + 4(243) + 8(81) + 16(27) + 256(9) + 512(3) + 1024
-41(2048-2187) =  729 + 2(243) + 4(81) + 64(27) + 128(9) + 256(3) + 512
-61(2048-2187) =  729 + 2(243) + 32(81) + 64(27) + 128(9) + 256(3) + 1024
-91(2048-2187) =  729 + 16(243) + 32(81) + 64(27) + 128(9) + 512(3) + 1024

The binary version of this cycle is
11110111000
11101110001
11011100011
10111000111
11100011110
11000111101
10001111011

For v(-17), I will refer to 729, 2(243), 4(81), 8(27), 32(9), 64(3), 128 as 'the terms' of the series for v(LE)

V.

I just want to go through this line by line to make a few observations

v(-17) = 11110111000
This means that the powers of 2 in v(-17) are, 1, 2, 4, 8, 32, 64, 128 (as in the first line above)

When we step to v(-25):

v(-17) 11110111000
v(-25) 11101110001

We are multiplying the 4th term by 2, and the 7th term by 8

The same applies for the next two steps (with the term to be increased moving back by one step)

v(-25) 11101110001
v(-37) 11011100011

We multiply the 3rd term by 2, and the 6th by 8

v(-37) 11011100011
v(-55) 10111000111

Multiply the 2nd term by 2 and the 5th by 8

v(-55) 10111000111
v(-41) 11100011110

This step is more complicated. But it is easier to understand if we look at this step with only a single halving (from 164 to 82, ignoring the halving step to 41):

v(-55) 10111000111
v(-82) 01110001111

Now we can see the same pattern, double the 1st term, multiply the 4th by 8.

(To check this is working, it can be halved back down by moving each digit one place to the left (the initial zero moves to the end to complete the loop: v(-41) 11100011110).


VII.

It is not only easier to see the pattern with only one halving per step. It also gives us a possible path to a proof. So here is the whole loop laid out visually.

At the bottom we divide by -139 (= 2048- 2187) to demonstrate that these are all examples of the equation from IV: n(2^z - 3^y) = v(n)

Note that when we express the chain this way the number of zeros in the loop dictates how much we multiply the terms by. This pattern has 4 zeroes in groups of 3 and 1. The group of 3 means we multiply by 8, the group of 1 means we multiply by 2.

The numbers in red are the ones that have been multiplied by 2 or 8. Note that most of the lines increase by x2 and x8, with two exceptions, the first and fifth term.

The number of zeroes = z - y

This means that the total value of v(n) has increased by slightly less than 2x8 = 16.

And in general the ratio between v(-17) and v(-182) must be slightly less than 2^(z-y):1

Of course we need to be a great deal more precise about what limits there are on 'slightly' - we will return to this crucial question in X. (We will see that it's actually considerably less in this instance, but that that is the reason a loop is possible.)

VIII.

Let the 'elements of a loop' refer to the numbers in a Collatz loop adjusted in this way, with only one halving per trebling. So in the loop above, -17 is the lowest element of the loop and -182 is the highest element. ('lowest' here refers to numerical value, not negative or positive)

Let LE be the lowest element of an adjusted 3n+1  loop
Let HE be the highest element of an adjusted 3n+1 loop

From IV: n rises at the same rate as v(n) 
v(HE):v(LE) = HE:LE  
Thus the ratio HE:LE is slightly less than 2^(z-y) (with the same caveat about the definition of 'slightly)


IX.

When we go from HE to LE we multiply by 3, add a power of 2 and divide by a power of 2.

If instead, we were to multiply by 3, add the appropriate power of 2 and divide only once by 2, the result is 2^(z-y)(LE).

This is a normal 3n+1 step, so the result must be equivalent to multiplying HE by less than 4/2 but more than 3/2 (in practise it will be much closer to 3/2 but these are the absolute bounds).

Therefore 1/2[LE(2^(z-y))] < HE < 2/3[LE(2^(z-y))]

X.

We now have two definitions of the increase from the lowest to highest element.

From VIII
The ratio HE:LE is slightly less than 2^(z-y):1 

From IX
1/2[LE(2^(z-y))] < HE < 2/3[LE(2^(z-y))]

The important part of this is 

HE < 2/3[LE(2^(z-y))]

So the question is, under what circumstances can 'slightly less' than LE[2^(z-y)] be less than 2/3[LE(2^(z-y))]

XI.

If we go back to the loops we started from, we can compare v(LE) with v(HE)

For 3, 13, 83

v(LE) = 25 + 10 + 4
v(HE) = 25 + 160 + 64



z-y = 4
2^(z-y)= 16

We can see that these terms (10 + 4) have increased at x16. However because 25 hasn't increased, the total increase from LE to HE is 249/39, which is less than 2/3[16]

(In this case, because this is a 5n+1 loop, we actually need this ratio to be less than 2/5[16], which it is. If this proof works for the 3n+1 problem, this would maybe suggest a path towards generalising it for 5n+1, 7n+1 etc).

For the 3n+1 loop where LE = -17 and HE = -182

v(LE) = 729 + 2(243) + 4(81) + 8(27) + 32(9) + 64(3) + 128 = 2363
v(HE) = 2(729) + 32(243) + 64(81) + 128(27) + 256(9) + 1024(3) + 2048 = 25298
  
z-y = 4
2^(z-y)= 16

Each element has increased by x16 except for 729 (which has increased by x2) and 32(9) (which has increased by x8). The total ratio HE:LE is 10.706 which is slightly higher than 2/3[16]. This creates a loop only because this is a loop of negative numbers and 3^z > 2^y.

XII.

From these cases we can see that if each term in the expression is multiplied by 2^(z-y) (with a few exceptions) then the resulting ratio will be less than 2^(z-y):1. How much less depends on what proportion of v(LE) the exceptions are.

Let J = the sum of the terms that don't increase by 2(z-y)

XIII.

To start with, in order to simplify the calculations, assume J is always the first and largest term in v(LE). In the chain for v(-17) we see that 729 only increases by x2 while 288 only increases by x8.
The impact on the final ratio would have been larger if 729 hadn't increased at all while 288 had increased by 16. So by assuming J is the largest term, we are establishing an absolute limit for how much less than 2(z-y):1 the ratio v(HE):v(LE) can be.

XIV.

The next few steps are slightly tedious as we need to narrow down the values of J that could support a loop. The strategy here will be:
1. Show that if J =< 1/3[v(LE)] a loop is impossible.
2. Show that where the first term is J and is > 1/3[v(LE), a loop still isn't possible.
3. Show that where J is a later term a loop isn't possible.


XV.

Assume v(LE) = 3J
v(HE) = 2^(z-y)2J + J

2^(z-y)2J + J > 2/3[2^(z-y)3J]

Therefore

If J < 1/3[v(LE)] then it is not true that v(HE):v(LE) < 2/3[2^(z-y)]:1

And therefore a 3n+1 loop is impossible if J =< 1/3[v(LE)].

XVI.

Next, let's look at a Collatz sequence that starts with a long series of upward steps. This will produce a series of terms for which the first term is greater than 1/3[v(LE)].

For instance:

v(n) = 729 + 2(243) + 4(81) + 8(27) + 16(9) + 32(3) + 64
= 729 + 2/3(729) + 4/9(729) + 8/27(729) + 16/81(729) + 32/243(729) + 64/729(729)

The sum of the series 1 + 2^n/3^n tends up to a limit of 3. So the first term is always slightly more than a third of the total as long as the upward steps continue.

This is one way of producing examples of J > 1/3[v(LE)], where J is the first term.

However we can rule these out as possible examples of a loop because, to quote Wikipedia:

"A k-cycle is a cycle that can be partitioned into 2k contiguous subsequences: k increasing sequences of odd numbers alternating with k decreasing sequences of even numbers. For instance, if the cycle consists of a single increasing sequence of odd numbers followed by a decreasing sequence of even numbers, it is called a 1-cycle.
Steiner (1977) proved that there is no 1-cycle other than the trivial (1;2). ... Simons & de Weger extended this proof up to 68-cycles: there is no k-cycle up to k = 68."

XVII.

Therefore we can't have a loop that starts with a long upward chain and then halves all the way back to the starting point.
 
XVIII.

As soon as we have more than two phases of increasing odd numbers in a Collatz chain, the first term is no longer > 1/3 v(LE).

In case this isn't obvious, here's a worked example.

1 + 2/3 + 4/9 + 8/27  .... sums to
1, 5/3, 19/9, 65/27, 211/243...

In other words the nth term is 3 - [2^n/3^(n-1)]

However, after one downward phase it reaches 3 - [2^(n-1)/3^(n-1)] (or higher)
Then the step after that will be  3 + [2^(n-2)/3^(n-1)] (or higher)

For instance if the fourth step were downward:
1, 5/3, 19/9, 65/27, 227/243, 745/729

Since at each stage we are multiplying the numerator by 3 and adding a power of 2 this will never fall below 3, so the first term will never again be more than 1/3 of the total.

XIX.

So this rules out the possibility of a loop starting with a long upward chain, with J as the first term > 1/3 v(LE).

The only other way we could have a term higher than 1/3 v(LE)  is if we have a sudden increase in the series of terms such as:

243 + 162 + 108 + 72 + 48 + 1024

However we can rule out the possibility of this kind of leap allowing us to 'construct' a loop also.


Lets start by consider an upward climbing series again.

2187n + 729 + 486 + 324 + 216 + 144 + 64

1 + 2/3 + 4/9 + 8/27.... tends up towards a limit of 3

Therefore 3^y(n) + 3^(n-1) + 2*3^(n-2) + 4*3^(n-3) + 8*3^(n-4)... tends towards 3^y(n) +3^y

For any integer value of n, 3^y(n) + 3^y < 2[3^y(n)]

This means that in a series of this sort, with a long upward climb, the only value of 2^z(n) that it can possibly reach is the first power of 2 higher than 3^y(n)

Let's 2^Z be the first power of 2 higher than 3^y(n)

Therefore if we add one last term to reach 2^Z it can't be higher than 2^(Z-1) 

(In case it isn't obvious, this is because, in a Collatz chain without halving, each power of 2 that we add after multiplying by 3 leads to a multiple of a higher power of 2 - for instance 7*3 = 21. 21 + 1 = 2 x 11. 22 * 3 + 2 = 66. 66+2 = 4 *17.... and so on).

Furthermore, because this is v(LE) the last term can't actually be higher than 2^(Z-2) - because otherwise the final step of the loop from LE to LE would be an upward step.

So for this series

2187n + 729 + 486 + 324 + 216 + 144 + 64

We could (theoretically) replace the last term with a maximum of 1024:

2187n + 729 + 486 + 324 + 216 + 144 + 1024 = 4096n

Therefore the last term must be smaller than 3^y.

If we were to add a higher power than this, there would be too many halving steps and the value of n would fall from the start to the end of the 'cycle', making a loop impossible.

However, 1024 > 1/3(729 + 486 + 324 + 216 + 144 +1024) so at this stage it as still looks as though we can add a last term > 1/3 v(LE)

XX.

However we already know from XVI that a cycle of this sort isn't possible, and that the first part of the series must  increase to more than three times the first term.

So next I want to look at whether it is possible to start from a series like this, but to adjust the terms upwards so as to reach a feasible value of 2^z(n)

We can generalise this kind of series in a word equation thus:

3^y(n) + [an integer tending up towards 3^y] + [a final term 2^(Z-2)  > 1/3 v(LE)] = 2^Z(n)

To rule this out we need to show three things.
1) The last term always increases by a significant ratio between v(LE) and v(HE).
2)  In the loop from LE to 2^z(LE) and the loop from HE to 2^z(HE) the value of 2^z is the same.
3) We can't increase the first part of the chain by enough to reach the necessary power of 2^z(n)

1) When we look at v(n) for the -17 cycle, we see that the numbers effectively move backward through a loop, not quite returning to their starting position:

11110111000

11101110001

11011100011

10111000111

11100011110

11000111101

10001111011

If a one follows a zero, then the number of zeros it follows tells us how much less than 2^(z-y) this number will increase by between LE and HE. So for v(-17) we have:

11110111000

The initial 1 follows three zeros (viewing this as a loop). So it increases by 8 times less than 2^(z-y) (by x2 instead of x16). The fifth 1 follows one zero, so it increases by 2 times less than 2^(z-y) (by x8 instead of x16).

2) As we go through the cycle from LE to LE or from HE to HE the total number of 3n+1and halving steps is the same. So, in the value of 2^z(LE) we reach and in the value of 2^z(HE), the value of z is the same.

Simons & de Weger have shown there is no k-cycle up to k = 68

This means that in the binary series expressing v(LE) there are at least 68 discrete groups of zeros.

This means that the last term must increase by at least 2^68 from LE to HS(because there are at least 68 zeros that don't precede it)

So now we need the series for v(LE) to be more like

3^y(n) + [an integer tending up towards 3^y] + [a final term 2^(Z-2)  > 1/3 v(LE)] = 2^(Z+67)(n)

The right hand side is 2^67 higher, which means that the final term has the required space to grow from v(LE) to v(HE) while z remains the same (in this case z = Z+67)


This is clearly not possible as we would have too many halving steps for a loop. In other words the left hand side of this 'equation' is less than 2^Z(n), while the right hand side is 2^67 times larger than that.

But can we close the gap by increasing the terms on the left hand side?

3) Each time we increase a term in the series (whether it is the the final term or not), we increase the potential value of 2^z. However, if we double the series (excluding the last term), then we also have to double the last term from 2^(Z-2) to 2^(Z-1) in order for it to stay higher than 1/3 v(LE).

This has the knock-on effect that we have to increase the power of 2 on the right hand side of the equation (because we still need to make sure that there is room for the final term to grow by 2^68 from v(LE) to v(HE)

So we can't ever close the gap, and it is impossible for there to be an equation of this sort.

XXI.

It is not possible that J > 1/3[v(LE)] for a k-cycle where k is greater than 68.

Therefore there are no 3n+1 chains that satisfy the conditions for a loop.

Therefore there are no 3n+1 cycles other than 1, 4, 2





Appendix A

Just to clarify how the equation referred to is derived. In order to ‘ignore the halving’ in a Collatz chain, we can adjust the basic calculation as below – I’ll work through an example, then show how this can be generalised.

For the Collatz chain 17 - 13 - 5 - 1, the process works like this.

17 x 3 + 1 = 52

We would halve twice to get from 52 to 17, so to reflect that we add 4 (=2^2) at the next step.

52 x 3 + 4 = 160

We would halve 3 times to get from 40 to 5, so now we have to increase the amount we add by 3 powers of 2 – from 4 to 32 (2^2 to 2^5).

160 x 3 + 32 = 512

To compute this, at the first step we multiply by 3 and add 1.
For every subsequent step we multiply by 3, express the result as 2^n x (an odd number) and add 2^n

And as we progress this generates the adjusted Collatz chain:

17 ~ (4 x 13) ~ (32 x 5) ~ (512 x 1)

The final sum can now be expressed thus:

(27 x 17) + (9 x 1) + (3 x 4) + 32 = 512

In general we would need to show that for any odd number X there is a calculation of this sort that adds up to a power of 2. The calculation can be generalised 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^0 in the final 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.

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 3ⁿ 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

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


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

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.