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) 111
1011
1000
v(-25) 111
0111
0001
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) 11
1011
10001
v(-37) 11
0111
00011
We multiply the 3rd term by 2, and the 6th by 8
v(-37) 1
1011
100011
v(-55) 1
0111
000111
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)
1011
1000111
v(-82)
0111
0001111
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 2
k 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.
