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.
No comments:
Post a Comment