Here's a bit more on this, following on from some earlier
thoughts (in fact this post and the next one contains a compressed version of the three previous Collatz posts, focusing on the bits I am currently most interested in).
I mentioned before this kind of series:
A+1
B+1+2^p
C+1+2^p+2^q
D+1+2^p+2^q+2^r (where r > q > p)
B+1+2^p
C+1+2^p+2^q
D+1+2^p+2^q+2^r (where r > q > p)
To get from A to B etc, you add the first term to 2x the
full equation. For instance:
A + 2(A) = B
B + 2(B+1) = C
C + 2(C+1+2^p) = D
Etc. Here is a worked example.
7
21+1=22 (=11*2)
21+(2*22)=65
65+1+2 = 68 (=17*4)
65+(2*68)=201
201+1+2+4=208 (=13*16)
201+(2*208)= 617
617+1+2+4+16 = 640 (=5*128)
617+(2*640)=1897
1897+1+2+4+16+128 = 2048
21+(2*22)=65
65+1+2 = 68 (=17*4)
65+(2*68)=201
201+1+2+4=208 (=13*16)
201+(2*208)= 617
617+1+2+4+16 = 640 (=5*128)
617+(2*640)=1897
1897+1+2+4+16+128 = 2048
Now, the point of this is that this method gives us a series which can be shown to be equivalent
to a Collatz sequence. The sequence above is equivalent to 7, 11, 17, 13, 5, 1,
ignoring the halving.
7 = 7
22 = 2 x 11
68 = 4 x 17
208 = 16 x 13
640 = 5 x 128
2048 = 1 x 2048
What the sequence above is doing is starting from this way
of expressing a Collatz sequence (without halving):
(7 x3)+1 = 22
(22 x 3) + 2 = 68
(68 x 3) + 4 = 208 etc
Which we can also express as:
3^1 x 7 + 1 = 22
3^2 x 7 + 3 + 2 = 68
3^3 x 7 + 9 + 6 + 4
In this form, a number X's chain will reach 1 if it
satisfies an equation of this sort:
(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
(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
Where e>d>c>b>a
For instance, for 7 we end up with:
(243x7) + 81 + (27x2) + (9x4) + (3x16) + 128
1701 + 81 + 54+ 36 + 48 + 128 = 2048
So… the process I started with is a way of finding the
number that reaches the same sum as this equation, but without the powers of 3.
21+1 = 22
63 + 3 + 2 is equivalent to 65 + 1 + 2
189 + 9 + 6 + 4 is equivalent to 201 + 1 + 2 + 4
567 + 27 + 18 + 12 + 16 is equivalent to 617 + 1 + 2 + 4 +
16
1701 + 81 + 54+ 36 + 48 + 128 is equivalent to 1897+1+2+4+16+128
Now, the important thing about this is that we can explore
the pattern of how to reach a power of 2 in steps of powers of two relatively
easily, since it reduces this problem to a binary number problem - and to a problem where we know every chain reaches the "target" of a power of 2.
(Because, from any
number we can reach the next power of 2 in steps of increasing powers of 2 for
instance
89+1+2+4+32 = 128
67+1+4+8+16+32 = 128
119+1+8 =128)
Where the next power of 2 is 2^n then in the region between
2^(n-1) and 2^n the maximum number of steps this can take is n-1 (for instance
between 16 and 32 the maximum number of steps is four, from 17 + 1 + 2 + 4 + 8. The
average number of steps in the same region is (n-1)/2 (this is easy to show, I'll skip it for brevity).
Now, as we go up through the A, B, C, D sequence etc we can
make several observations.
At each step we are increasing by a factor of just over 3.
So the maximum number of steps in the region increases by about 1.5-1.6, the
average number of steps increases by about 0.75-0.8 (again, this can be made a bit
more rigorous, I’m summarising to keep this brief).
At the same time, each time we take a step through the
sequence, the minimum number of powers of 2 we need to be able to add increases
by 1. For instance in each of the sums below, we add one more term.
21+1
65+1+2
201+1+2+4
617+1+2+4+16
The consequence of these two things put together is that for
any starting number we eventually reach a point where (for an equivalent
Collatz sequence that doesn’t reach 1) each number we hit has to be more than
the average number of steps from a power of 2 – approximately 1.25 x the
average.
As an example of how this works - for the Collatz sequence for 27, after about 18 steps we are in region where the average number of steps to a power of 2 is 18 - thereafter it takes until about the 40th step to reach a power of 2.
Also, each time we skip a power of 2, we have to reduce the
maximum number of steps available by 1 – for instance as we extend the sequence
above, we will never be able to reach a number that adds 8, as each time we
will have to start by adding 1+2+4+16. So while we are in the region 2^8-2^9,
the maximum number of steps available is reduced to 8-1 = 7.
Now, while it is impossible to have an infinite sequence of
steps that don’t skip a power (again, this can be proven but I’m skimming),
quite long sequences of this sort are possible (for instance starting from 255
there are 7 upwards steps before we skip a power).
So the challenge facing this approach is to try to prove
that the sequence A, B, C, D, starting from any number can’t be infinitely
extended without hitting a number where the number of steps we need to reach
2^n is equal to the minimum number of steps we need.
I’ve noticed something else which takes us a tiny bit closer to this.
When we reach a number like 201 in the sequence above, after which we are going to
skip a power, the number of subsequent upwards steps without skipping a power
is partly defined by how many powers we skip this time. This sounds woolly, so let me
give a couple of examples.
201+1+2+4+16+32 = 256
We know at this stage that we will skip 8 (because the next
number will be 201 + 208 + 208 – this means we are adding 0 mod 16, and will land on another number that is 9 mod 16, meaning that adding 1, 2, 4 will take us to a multiple of 16).
Also, we don’t skip the subsequent power, 32. This means we
won’t have an upward step without skipping next time, which is correct – 617 +
1+2 +4+16+128+256 = 1024 – we are now going to skip 32 and 64.
Let’s look at a different sequence:
55
165+1
497+1+2
1497+1+2+4
4505+1+2+4+32
The turning point (where you skip a power) comes after 1497
The continued equation here would be 1497+1+2+4+32+512.
1497 = 8n+1 and 16n+1 and we are going to add 0 mod 8, 8 mod
16 to get to the next number, 4505. So we have to skip 8. We actually skip 16
too (I’ll explain the logic of this later ) so the next number we add
will be 32. Thereafter, 1497 is 64n-39, 128n-39, 256n-39, 512n-39, so we will
subsequently have upwards steps of 64, 128, 256, before skipping a power.
So to get to an upwards sequence of 3 steps without skipping,
we need to hit a number that skips 3 numbers.This means we can't hit a sequence of n steps where n is more than the difference between the maximum number of steps in the region and the minimum number of steps we are obliged to take.
Putting this stuff together we get 1) for all numbers we will eventually reach a region where we are obliged to take about 1.25 x the average number of steps in that region at every stage. 2) In order to get uninterrupted upwards runs of numbers (eg not skipping a power) in the next step, we need to skip that many powers this step. 3) Whenever we hit the latter stages of a region there will be some powers that we are forced to skip. For instance, from 1897, it is impossible for us to add 256 or 512 as part of the path to 2048. This makes it hard to see how we could avoid reaching a power of 2, but falls short of being a proof unless it can be refined some more.
No comments:
Post a Comment