Abstract: I explain how and why just looking at the last bits of numbers gives deep insights into their Collatz/2 (odds halved) sequences. The conclusion is for mathematicians to validate: I either show how to find an infinite amount of infinite counter-examples*) to the Collatz conjecture. Or at the least, I show that there can be no upper bound to sequence length. I can cheaply narrow down the amount of numbers that elude a trivial answer. These gaps between the trivial ones are the challenge. I can both construct examples of any great length, or systematically find them all up to a given length. Thanks to my prediction formula, I can skip calculating many initial steps of almost all sequences.
Collatz – Tales of Tailsby Daniel is licensed under    Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) |
TL;DRThe lowest l bits of any number exactly define the next l steps. Flipping bit l will make step l change direction. For one more bit, one (hard to predict) value will make the next step halve down, the other will make it multiply up. So some series of extra bits will ultimately make a sequence stop, while others will make it rise indefinitely. |
Definitions: I call the lowest bits of a number its tail of length l (that's an ell). One calls to stop the fact that a Collatz sequence (your understanding of which I presume) reaches a smaller than the initial number. (The original notion of reaching 1 – or worse a tiny endless loop – is called total stopping, but that's not directly of interest here.) The terms Good, Bad and Ugly are so central, they get a chapter of their own.
As a software engineer, I took a bit-biter approach to his conjecture. By reformulating his arithmetic operations to equivalent bit-ops with only one addition (the 2nd, an increment, can be done by flipping the final bits up to and including the lowest 0-bit), my code is about ⅓ faster. I started out by playing with my Perl one-liner magic wand. But it has grown into a serious analysis. All of this was developed by me. But I haven't got an overview of relevant studies, so some or all of this might not be new*).
Wife plays board games with another man. She's monopolyamorous. 🤭
Collatz' Game of LifeOne can look at the bit transitions for each step as generations of an automaton. The trivial case for even numbers just copies down the bit that was on the left.
The odd case is fully ruled by the following table, where the rows are the preceding bit, the columns the same bit, and as a 3rd input whether we add 1. That's by definition the case for a lowest 1-bit, but also if the bits to the right produce a carry. A carry comes from '01' repetitions up to the end or up to a '11'.
| +0 | +1 | |||
|---|---|---|---|---|
| _0 | _1 | _0 | _1 | |
| 0_ | 0 | 1 | 1 | 0 |
| 1_ | 1 | 0 | 0 | 1 |
That's it, from the perspective of each one resulting bit. It becomes '0' exactly if zero or two inputs are '1'. Maybe just an interesting digression because the carry bits somewhat chaotically depend on a varying number of positions to the right. Unlike Conway's cognate, no bit patterns can die out. On the contrary: even if a bit group doesn't get a carry added in, steps up will always make it grow to the right and in every other step also to the left.
However the exciting part is this: because, as we'll see next, the bit-oriented definition of T(n) has exactly one shift right in every step, exactly one bit from the left mingles in, and no others further left. And most importantly, it's deterministic: bits either stay the same or flip but never coalesce to the same value. Flip any of the 3 inputs, and it flips the output. The bit from the left is the most exciting one: it propagates straight towards the end and influences the next step, once it reaches the end.
Odds are, math puns make me feel even number. 😂
Tell-TailsFor proof by full induction it would be enough to show that every number stops. To this end the "shortcut" Collatz/2 (odds halved) function (which is the only variant I ever refer to here) when converted to a bit-shift operation
has an interesting property: in every step there's a shift right by 1 bit. In other words, the two lowest bits govern the next two steps, the three lowest the next three, etc. No bits further left intervene. This is quite huge: if a sequence reaches a lower number in l steps, it's exactly the tail of length l which is responsible. All numbers sharing that same tail will have the identical rise and fall pattern and also stop, i.e. reach a lower number in l steps.
This is by definition true for a final '0'. For '1' it isn't, so we need to try both a '0' and a '1' in front of it. Turns out '01' numbers always end in two steps. For '11' it can't be decided, so we need to explore both '011' and '111'. Both can't be decided, so we need to explore '0011', '1011', '0111' and '1111'. Again all numbers ending in '0011' get reduced in 4 steps. For the other three branches of our exploration tree, we must again add '0' and '1' in front of them. Now '01011' and '10111' get reduced in 5 steps.
Leading 0-bits are significant because within numbers ending in that tail, they're actually inner 0-bits. Because the last l bits predict the next l steps, either all numbers ending in a tail stop – or none do. This is illustrated by the diagonal, which delimits, as per the automaton above, the bits that influence the next steps. The 0..3 are what's prepended to each tail, just to show it doesn't matter what precedes. Add any tails you want to try (except '0' or '01' which would need special handling) as parameters. The colours (people with impairment may adapt their system, terminal, or browser) are explained below. The last output illustrates how quickly a wide gap of 0-bits melts – but also, even before a carry bit enters from the right, how fast isolated bits grow. This is hardly a one-liner but does profit from pl, without which it'd be rather longer. This gets the job done quick&dirty, rather than elegantly, sorry:
pl -oA '$a = eval "0b$_"; $l = length; -$l, map $a|($_<<$l), 0..3 ' \
'if( $_ < 0 ) { $l = -$_; $m = 9; next }
$n = $_; $b = 2; $p = 85 - $l; echo "-" x $m if $ARGIND > 1; $m = 3;
while( 1 ) {
echo qw(\\ / +)[$b], Form( "%20d %1:64b" ) =~ s/.{$p}\K( *)/"\\" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
die "tail too short" if ++$p > 85;
} ' 0011 01011 10111 1111100111 000000001111111111pl -oA '$a = eval "0b$_"; $l = length; -$l, map $a|($_<<$l), 0..3 ' \
'if( $_ < 0 ) { $l = -$_; $m = 9; next }
$n = $_; $b = 2; $p = 85 - $l; e "-" x $m if $I > 1; $m = 3;
while( 1 ) {
e qw(\\ / +)[$b], F( "%20d %1:64b" ) =~ s/.{$p}\K( *)/"\\" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
die "tail too short" if ++$p > 85;
} ' 0011 01011 10111 1111100111 000000001111111111+ 3 \00 11 / 5 \10 1 / 8 10\00 \ 4 10\0 \ 2 10\ --- + 19 1\00 11 / 29 11\10 1 / 44 1011\00 \ 22 1011\0 \ 11 1011\ --- + 35 10\00 11 / 53 110\10 1 / 80 10100\00 \ 40 10100\0 \ 20 10100\ --- + 51 11\00 11 / 77 1001\10 1 / 116 11101\00 \ 58 11101\0 \ 29 11101\ --------- + 11 \0 1 011 / 17 1\0 0 01 / 26 11\0 \ 13 11\1 00 1 / 20 1010\0 \ 10 1010\ --- + 43 1\0 1 011 / 65 100\0 0 01 / 98 1100\0 \ 49 1100\1 00 1 / 74 100101\0 \ 37 100101\ --- + 75 10\0 1 011 / 113 111\0 0 01 / 170 10101\0 \ 85 10101\1 00 1 / 128 1000000\0 \ 64 1000000\ --- + 107 11\0 1 011 / 161 1010\0 0 01 / 242 11110\0 \ 121 11110\1 00 1 / 182 1011011\0 \ 91 1011011\ --------- + 23 \10 111 / 35 10\00 11 / 53 110\10 1 / 80 10100\00 \ 40 10100\0 \ 20 10100\ --- + 55 1\10 111 / 83 101\00 11 / 125 1111\10 1 / 188 101111\00 \ 94 101111\0 \ 47 101111\ --- + 87 10\10 111 / 131 1000\00 11 / 197 11000\10 1 / 296 1001010\00 \ 148 1001010\0 \ 74 1001010\ --- + 119 11\10 111 / 179 1011\00 11 / 269 100001\10 1 / 404 1100101\00 \ 202 1100101\0 \ 101 1100101\ --------- + 999 \111 110 0111 / 1499 10\111 011 011 / 2249 1000\110 010 01 / 3374 11010\010 \ 1687 11010\111 0010 111 / 2531 1001111\000 11 / 3797 11101101\010 1 / 5696 1011001000\000 \ 2848 1011001000\00 \ 1424 1011001000\0 \ 712 1011001000\ --- + 2023 1\111 110 0111 / 3035 101\111 011 011 / 4553 10001\110 010 01 / 6830 110101\010 \ 3415 110101\111 0010 111 / 5123 10100000\000 11 / 7685 111100000\010 1 / 11528 10110100001\000 \ 5764 10110100001\00 \ 2882 10110100001\0 \ 1441 10110100001\ --- + 3047 10\111 110 0111 / 4571 1000\111 011 011 / 6857 11010\110 010 01 / 10286 1010000\010 \ 5143 1010000\111 0010 111 / 7715 11110001\000 11 / 11573 1011010011\010 1 / 17360 100001111010\000 \ 8680 100001111010\00 \ 4340 100001111010\0 \ 2170 100001111010\ --- + 4071 11\111 110 0111 / 6107 1011\111 011 011 / 9161 100011\110 010 01 / 13742 1101011\010 \ 6871 1101011\111 0010 111 / 10307 101000010\000 11 / 15461 1111000110\010 1 / 23192 101101010011\000 \ 11596 101101010011\00 \ 5798 101101010011\0 \ 2899 101101010011\ --------- + 1023 \0000 0 0001111111111 / 1535 \0000 0 010111111111 / 2303 \0000 1 00011111111 / 3455 \0001 1 0101111111 / 5183 \0101 0 000111111 / 7775 \1111 0 01011111 / 11663 10\1101 1 0001111 / 17495 1000\1000 1 010111 / 26243 11001\1010 0 00011 / 39365 1001100\1110 0 0101 / 59048 11100110\1010 \ 29524 11100110\1 0001010 \ 14762 11100110\1 001010 \ 7381 11100110\1 01010 1 / 11072 1010110100\0000 \ 5536 1010110100\000 \ 2768 1010110100\00 \ 1384 1010110100\0 \ 692 1010110100\ --- + 263167 1\0000 0 0001111111111 / 394751 11\0000 0 010111111111 / 592127 1001\0000 1 00011111111 / 888191 11011\0001 1 0101111111 / 1332287 1010001\0101 0 000111111 / 1998431 11110011\1111 0 01011111 / 2997647 1011011011\1101 1 0001111 / 4496471 100010010011\1000 1 010111 / 6744707 1100110111010\1010 0 00011 / 10117061 100110100101111\1110 0 0101 / 15175592 1110011110001111\1010 \ 7587796 1110011110001111\1 0001010 \ 3793898 1110011110001111\1 001010 \ 1896949 1110011110001111\1 01010 1 / 2845424 101011011010101111\0000 \ 1422712 101011011010101111\000 \ 711356 101011011010101111\00 \ 355678 101011011010101111\0 \ 177839 101011011010101111\ --- + 525311 10\0000 0 0001111111111 / 787967 110\0000 0 010111111111 / 1181951 10010\0000 1 00011111111 / 1772927 110110\0001 1 0101111111 / 2659391 10100010\0101 0 000111111 / 3989087 111100110\1111 0 01011111 / 5983631 10110110100\1101 1 0001111 / 8975447 1000100011110\1000 1 010111 / 13463171 11001101011011\1010 0 00011 / 20194757 1001101000010010\1110 0 0101 / 30292136 11100111000111000\1010 \ 15146068 11100111000111000\1 0001010 \ 7573034 11100111000111000\1 001010 \ 3786517 11100111000111000\1 01010 1 / 5679776 1010110101010101010\0000 \ 2839888 1010110101010101010\000 \ 1419944 1010110101010101010\00 \ 709972 1010110101010101010\0 \ 354986 1010110101010101010\ --- + 787455 11\0000 0 0001111111111 / 1181183 1001\0000 0 010111111111 / 1771775 11011\0000 1 00011111111 / 2657663 1010001\0001 1 0101111111 / 3986495 11110011\0101 0 000111111 / 5979743 1011011001\1111 0 01011111 / 8969615 100010001101\1101 1 0001111 / 13454423 1100110101001\1000 1 010111 / 20181635 100110011111100\1010 0 00011 / 30272453 1110011011110101\1110 0 0101 / 45408680 101011010011100001\1010 \ 22704340 101011010011100001\1 0001010 \ 11352170 101011010011100001\1 001010 \ 5676085 101011010011100001\1 01010 1 / 8514128 10000001111010100101\0000 \ 4257064 10000001111010100101\000 \ 2128532 10000001111010100101\00 \ 1064266 10000001111010100101\0 \ 532133 10000001111010100101\
Like for other pl examples, hover (or tap) near the ▶ play button to pop out the result and use the ☰ veggie-burger menu to toggle many-line display and short and/or long form. The blue sidelines show the structure and act as breadcrumbs: You can hover, click or bookmark them.
Tilting the diagonal, so that the shifts right go straight down, gives a rather different perspective. Throw in the explosive 27, stretched to l = 59, where it finally becomes a Good tail. We see that several longer series of 1-bits appear at the end, each time jazzing the sequence upwards. This needs bignum (which may need turning off upgrade, pending Perl issue #21370.) because the last three evolve beyond 64 bits:
pl -Mbigint -oA '$a = eval "0b$_"; $l = length; -$l, map $a|($_<<$l), 0, 1, 2, 3 ' \
'if( $_ < 0 ) { $l = -$_; $m = 9; next }
$n = $_; $b = 2; $i = 63 + $l; $p = 64 - $l; echo "-" x $m if $ARGIND > 1; $m = 3;
while( 1 ) {
echo qw(\\ / +)[$b], Form( "%21s%*s", $_, --$i, $_->to_bin ) =~ s/.{83}\K( *)/"|" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
die "tail too short" if ++$p > 64;
} ' 0011 01011 10111 1111100111 000000001111111111 \
00000000000000000000000000000000000000000000000000000011011pl -Mbigint -oA '$a = eval "0b$_"; $l = length; -$l, map $a|($_<<$l), 0, 1, 2, 3 ' \
'if( $_ < 0 ) { $l = -$_; $m = 9; next }
$n = $_; $b = 2; $i = 63 + $l; $p = 64 - $l; e "-" x $m if $I > 1; $m = 3;
while( 1 ) {
e qw(\\ / +)[$b], F( "%21s%*s", $_, --$i, $_->to_bin ) =~ s/.{83}\K( *)/"|" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
die "tail too short" if ++$p > 64;
} ' 0011 01011 10111 1111100111 000000001111111111 \
00000000000000000000000000000000000000000000000000000011011+ 3 |00 11 / 5 |10 1 / 8 10|00 \ 4 10|0 \ 2 10| --- + 19 1|00 11 / 29 11|10 1 / 44 1011|00 \ 22 1011|0 \ 11 1011| --- + 35 10|00 11 / 53 110|10 1 / 80 10100|00 \ 40 10100|0 \ 20 10100| --- + 51 11|00 11 / 77 1001|10 1 / 116 11101|00 \ 58 11101|0 \ 29 11101| --------- + 11 |0 1 011 / 17 1|0 0 01 / 26 11|0 \ 13 11|1 00 1 / 20 1010|0 \ 10 1010| --- + 43 1|0 1 011 / 65 100|0 0 01 / 98 1100|0 \ 49 1100|1 00 1 / 74 100101|0 \ 37 100101| --- + 75 10|0 1 011 / 113 111|0 0 01 / 170 10101|0 \ 85 10101|1 00 1 / 128 1000000|0 \ 64 1000000| --- + 107 11|0 1 011 / 161 1010|0 0 01 / 242 11110|0 \ 121 11110|1 00 1 / 182 1011011|0 \ 91 1011011| --------- + 23 |10 111 / 35 10|00 11 / 53 110|10 1 / 80 10100|00 \ 40 10100|0 \ 20 10100| --- + 55 1|10 111 / 83 101|00 11 / 125 1111|10 1 / 188 101111|00 \ 94 101111|0 \ 47 101111| --- + 87 10|10 111 / 131 1000|00 11 / 197 11000|10 1 / 296 1001010|00 \ 148 1001010|0 \ 74 1001010| --- + 119 11|10 111 / 179 1011|00 11 / 269 100001|10 1 / 404 1100101|00 \ 202 1100101|0 \ 101 1100101| --------- + 999 |111 110 0111 / 1499 10|111 011 011 / 2249 1000|110 010 01 / 3374 11010|010 \ 1687 11010|111 0010 111 / 2531 1001111|000 11 / 3797 11101101|010 1 / 5696 1011001000|000 \ 2848 1011001000|00 \ 1424 1011001000|0 \ 712 1011001000| --- + 2023 1|111 110 0111 / 3035 101|111 011 011 / 4553 10001|110 010 01 / 6830 110101|010 \ 3415 110101|111 0010 111 / 5123 10100000|000 11 / 7685 111100000|010 1 / 11528 10110100001|000 \ 5764 10110100001|00 \ 2882 10110100001|0 \ 1441 10110100001| --- + 3047 10|111 110 0111 / 4571 1000|111 011 011 / 6857 11010|110 010 01 / 10286 1010000|010 \ 5143 1010000|111 0010 111 / 7715 11110001|000 11 / 11573 1011010011|010 1 / 17360 100001111010|000 \ 8680 100001111010|00 \ 4340 100001111010|0 \ 2170 100001111010| --- + 4071 11|111 110 0111 / 6107 1011|111 011 011 / 9161 100011|110 010 01 / 13742 1101011|010 \ 6871 1101011|111 0010 111 / 10307 101000010|000 11 / 15461 1111000110|010 1 / 23192 101101010011|000 \ 11596 101101010011|00 \ 5798 101101010011|0 \ 2899 101101010011| --------- + 1023 |0000 0 0001111111111 / 1535 |0000 0 010111111111 / 2303 |0000 1 00011111111 / 3455 |0001 1 0101111111 / 5183 |0101 0 000111111 / 7775 |1111 0 01011111 / 11663 10|1101 1 0001111 / 17495 1000|1000 1 010111 / 26243 11001|1010 0 00011 / 39365 1001100|1110 0 0101 / 59048 11100110|1010 \ 29524 11100110|1 0001010 \ 14762 11100110|1 001010 \ 7381 11100110|1 01010 1 / 11072 1010110100|0000 \ 5536 1010110100|000 \ 2768 1010110100|00 \ 1384 1010110100|0 \ 692 1010110100| --- + 263167 1|0000 0 0001111111111 / 394751 11|0000 0 010111111111 / 592127 1001|0000 1 00011111111 / 888191 11011|0001 1 0101111111 / 1332287 1010001|0101 0 000111111 / 1998431 11110011|1111 0 01011111 / 2997647 1011011011|1101 1 0001111 / 4496471 100010010011|1000 1 010111 / 6744707 1100110111010|1010 0 00011 / 10117061 100110100101111|1110 0 0101 / 15175592 1110011110001111|1010 \ 7587796 1110011110001111|1 0001010 \ 3793898 1110011110001111|1 001010 \ 1896949 1110011110001111|1 01010 1 / 2845424 101011011010101111|0000 \ 1422712 101011011010101111|000 \ 711356 101011011010101111|00 \ 355678 101011011010101111|0 \ 177839 101011011010101111| --- + 525311 10|0000 0 0001111111111 / 787967 110|0000 0 010111111111 / 1181951 10010|0000 1 00011111111 / 1772927 110110|0001 1 0101111111 / 2659391 10100010|0101 0 000111111 / 3989087 111100110|1111 0 01011111 / 5983631 10110110100|1101 1 0001111 / 8975447 1000100011110|1000 1 010111 / 13463171 11001101011011|1010 0 00011 / 20194757 1001101000010010|1110 0 0101 / 30292136 11100111000111000|1010 \ 15146068 11100111000111000|1 0001010 \ 7573034 11100111000111000|1 001010 \ 3786517 11100111000111000|1 01010 1 / 5679776 1010110101010101010|0000 \ 2839888 1010110101010101010|000 \ 1419944 1010110101010101010|00 \ 709972 1010110101010101010|0 \ 354986 1010110101010101010| --- + 787455 11|0000 0 0001111111111 / 1181183 1001|0000 0 010111111111 / 1771775 11011|0000 1 00011111111 / 2657663 1010001|0001 1 0101111111 / 3986495 11110011|0101 0 000111111 / 5979743 1011011001|1111 0 01011111 / 8969615 100010001101|1101 1 0001111 / 13454423 1100110101001|1000 1 010111 / 20181635 100110011111100|1010 0 00011 / 30272453 1110011011110101|1110 0 0101 / 45408680 101011010011100001|1010 \ 22704340 101011010011100001|1 0001010 \ 11352170 101011010011100001|1 001010 \ 5676085 101011010011100001|1 01010 1 / 8514128 10000001111010100101|0000 \ 4257064 10000001111010100101|000 \ 2128532 10000001111010100101|00 \ 1064266 10000001111010100101|0 \ 532133 10000001111010100101| --------- + 27 |00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 000011 011 / 41 |00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 001010 01 / 62 |00 \ 31 |0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 011111 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 011111 / 47 |00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 01 01111 / 71 |00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 001 00 0111 / 107 |00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 011 01 011 / 161 |00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0001 010 00 01 / 242 |00 \ 121 |0 0000 00 00 0000000 00000000 000 0000 000 00000 0011 110 01 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 0011 110 01 / 182 |00 \ 91 |0 0000 00 00 0000000 00000000 000 0000 000 00000 1011 011 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 1011 011 / 137 |00 0 0000 00 00 0000000 00000000 000 0000 000 00010 0010 01 / 206 |00 \ 103 |0 0000 00 00 0000000 00000000 000 0000 000 00110 0111 000 0 0000 00 00 0000000 00000000 000 0000 000 00110 0111 / 155 |00 0 0000 00 00 0000000 00000000 000 0000 000 10011 011 / 233 |00 0 0000 00 00 0000000 00000000 000 0000 001 11010 01 / 350 |00 \ 175 |0 0000 00 00 0000000 00000000 000 0000 101 01111 000 0 0000 00 00 0000000 00000000 000 0000 101 01111 / 263 |00 0 0000 00 00 0000000 00000000 000 0010 000 0111 / 395 |00 0 0000 00 00 0000000 00000000 000 0110 001 011 / 593 |00 0 0000 00 00 0000000 00000000 001 0010 100 01 / 890 |00 \ 445 |0 0000 00 00 0000000 00000000 011 0111 101 000 0 0000 00 00 0000000 00000000 011 0111 101 / 668 |00 \ 334 |0 0000 00 00 0000000 00000001 010 0111 0000 \ 167 |0 0000 00 00 0000000 00000001 010 0111 000 0 0000 00 00 0000000 00000001 010 0111 / 251 |00 0 0000 00 00 0000000 00000011 111 011 / 377 |00 0 0000 00 00 0000000 00001011 110 01 / 566 |00 \ 283 |0 0000 00 00 0000000 00100011 011 000 0 0000 00 00 0000000 00100011 011 / 425 |00 0 0000 00 00 0000000 01101010 01 / 638 |00 \ 319 |0 0000 00 00 0000001 00111111 000 0 0000 00 00 0000001 00111111 / 479 |00 0 0000 00 00 0000011 1011111 / 719 |00 0 0000 00 00 0001011 001111 / 1079 |00 0 0000 00 00 0100001 10111 / 1619 |00 0 0000 00 00 1100101 0011 / 2429 |00 0 0000 00 10 0101111 101 / 3644 |00 \ 1822 |0 0000 01 11 0001111 0000 \ 911 |0 0000 01 11 0001111 000 0 0000 01 11 0001111 / 1367 |00 0 0001 01 01 010111 / 2051 |00 0 0100 00 00 00011 / 3077 |00 0 1100 00 00 0101 / 4616 |01 \ 2308 |0 0100 00 01 00001 \ 1154 |0 0100 00 01 0001 \ 577 |0 0100 00 01 001 0 0100 00 01 / 866 |11 \ 433 |0 1100 01 011 0 1100 01 / 650 10|10 \ 325 10|0 0101 010 0 0101 / 488 111|10 \ 244 111|1 00010 \ 122 111|1 0010 \ 61 111|1 010 1 / 92 10111|00 \ 46 10111|0 \ 23 10111| --- + 576460752303423515 1|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 000011 011 / 864691128455135273 11|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 001010 01 / 1297036692682702910 1001|00 \ 648518346341351455 1001|0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 011111 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 011111 / 972777519512027183 11011|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 01 01111 / 1459166279268040775 1010001|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 001 00 0111 / 2188749418902061163 11110011|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 011 01 011 / 3283124128353091745 1011011001|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0001 010 00 01 / 4924686192529637618 100010001011|00 \ 2462343096264818809 100010001011|0 0000 00 00 0000000 00000000 000 0000 000 00000 0011 110 01 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 0011 110 01 / 3693514644397228214 1100110100001|00 \ 1846757322198614107 1100110100001|0 0000 00 00 0000000 00000000 000 0000 000 00000 1011 011 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 1011 011 / 2770135983297921161 100110011100011|00 0 0000 00 00 0000000 00000000 000 0000 000 00010 0010 01 / 4155203974946881742 1110011010101001|00 \ 2077601987473440871 1110011010101001|0 0000 00 00 0000000 00000000 000 0000 000 00110 0111 000 0 0000 00 00 0000000 00000000 000 0000 000 00110 0111 / 3116402981210161307 101011001111111011|00 0 0000 00 00 0000000 00000000 000 0000 000 10011 011 / 4674604471815241961 10000001101111110001|00 0 0000 00 00 0000000 00000000 000 0000 001 11010 01 / 7011906707722862942 110000101001111010011|00 \ 3505953353861431471 110000101001111010011|0 0000 00 00 0000000 00000000 000 0000 101 01111 000 0 0000 00 00 0000000 00000000 000 0000 101 01111 / 5258930030792147207 10010001111101101111001|00 0 0000 00 00 0000000 00000000 000 0010 000 0111 / 7888395046188220811 110110101111001001101011|00 0 0000 00 00 0000000 00000000 000 0110 001 011 / 11832592569282331217 10100100001101011101000001|00 0 0000 00 00 0000000 00000000 001 0010 100 01 / 17748888853923496826 111101100101000010111000011|00 \ 8874444426961748413 111101100101000010111000011|0 0000 00 00 0000000 00000000 011 0111 101 000 0 0000 00 00 0000000 00000000 011 0111 101 / 13311666640442622620 10111000101111001000101001001|00 \ 6655833320221311310 10111000101111001000101001001|0 0000 00 00 0000000 00000001 010 0111 0000 \ 3327916660110655655 10111000101111001000101001001|0 0000 00 00 0000000 00000001 010 0111 000 0 0000 00 00 0000000 00000001 010 0111 / 4991874990165983483 1000101010001101011001111011011|00 0 0000 00 00 0000000 00000011 111 011 / 7487812485248975225 11001111110101000001101110010001|00 0 0000 00 00 0000000 00001011 110 01 / 11231718727873462838 1001101111011111000101001010110011|00 \ 5615859363936731419 1001101111011111000101001010110011|0 0000 00 00 0000000 00100011 011 000 0 0000 00 00 0000000 00100011 011 / 8423789045905097129 11101001110011101001111100000011001|00 0 0000 00 00 0000000 01101010 01 / 12635683568857645694 1010111101011010111101110100001001011|00 \ 6317841784428822847 1010111101011010111101110100001001011|0 0000 00 00 0000001 00111111 000 0 0000 00 00 0000001 00111111 / 9476762676643234271 100000111000010000111001011100011100001|00 0 0000 00 00 0000011 1011111 / 14215144014964851407 1100010101000110010101100010101010100011|00 0 0000 00 00 0001011 001111 / 21322716022447277111 100100111111010011000000100111111111101001|00 0 0000 00 00 0100001 10111 / 31984074033670915667 1101110111101111001000001110111111110111011|00 0 0000 00 00 1100101 0011 / 47976111050506373501 101001100111001101011000101100111111100110001|00 0 0000 00 10 0101111 101 / 71964166575759560252 1111100110101101000001010000110111110110010011|00 \ 35982083287879780126 1111100110101101000001010000110111110110010011|0 0000 01 11 0001111 0000 \ 17991041643939890063 1111100110101101000001010000110111110110010011|0 0000 01 11 0001111 000 0 0000 01 11 0001111 / 26986562465909835095 101110110100000111000011110010100111100010111001|00 0 0001 01 01 010111 / 40479843698864752643 10001100011100010101001011010111110110101000101011|00 0 0100 00 00 00011 / 60719765548297128965 110100101010100111111100010000111100011111010000001|00 0 1100 00 00 0101 / 91079648322445693448 10011101111111110111110100110010110101011101110000011|01 \ 45539824161222846724 10011101111111110111110100110010110101011101110000011|0 0100 00 01 00001 \ 22769912080611423362 10011101111111110111110100110010110101011101110000011|0 0100 00 01 0001 \ 11384956040305711681 10011101111111110111110100110010110101011101110000011|0 0100 00 01 001 0 0100 00 01 / 17077434060458567522 111011001111111100111011110011000100000011001010001001|11 \ 8538717030229283761 111011001111111100111011110011000100000011001010001001|0 1100 01 011 0 1100 01 / 12808075545343925642 10110001101111110110110011011001001100001001011110011101|10 \ 6404037772671962821 10110001101111110110110011011001001100001001011110011101|0 0101 010 0 0101 / 9606056659007944232 1000010101001111100100011010001011100100011100011011011000|10 \ 4803028329503972116 1000010101001111100100011010001011100100011100011011011000|1 00010 \ 2401514164751986058 1000010101001111100100011010001011100100011100011011011000|1 0010 \ 1200757082375993029 1000010101001111100100011010001011100100011100011011011000|1 010 1 / 1801135623563989544 11000111111101110101101001110100010101101010101010010001010|00 \ 900567811781994772 11000111111101110101101001110100010101101010101010010001010|0 \ 450283905890997386 11000111111101110101101001110100010101101010101010010001010| --- + 1152921504606847003 10|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 000011 011 / 1729382256910270505 110|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 001010 01 / 2594073385365405758 10010|00 \ 1297036692682702879 10010|0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 011111 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 011111 / 1945555039024054319 110110|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 01 01111 / 2918332558536081479 10100010|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 001 00 0111 / 4377498837804122219 111100110|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 011 01 011 / 6566248256706183329 10110110010|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0001 010 00 01 / 9849372385059274994 1000100010110|00 \ 4924686192529637497 1000100010110|0 0000 00 00 0000000 00000000 000 0000 000 00000 0011 110 01 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 0011 110 01 / 7387029288794456246 11001101000010|00 \ 3693514644397228123 11001101000010|0 0000 00 00 0000000 00000000 000 0000 000 00000 1011 011 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 1011 011 / 5540271966595842185 1001100111000110|00 0 0000 00 00 0000000 00000000 000 0000 000 00010 0010 01 / 8310407949893763278 11100110101010010|00 \ 4155203974946881639 11100110101010010|0 0000 00 00 0000000 00000000 000 0000 000 00110 0111 000 0 0000 00 00 0000000 00000000 000 0000 000 00110 0111 / 6232805962420322459 1010110011111110110|00 0 0000 00 00 0000000 00000000 000 0000 000 10011 011 / 9349208943630483689 100000011011111100010|00 0 0000 00 00 0000000 00000000 000 0000 001 11010 01 / 14023813415445725534 1100001010011110100110|00 \ 7011906707722862767 1100001010011110100110|0 0000 00 00 0000000 00000000 000 0000 101 01111 000 0 0000 00 00 0000000 00000000 000 0000 101 01111 / 10517860061584294151 100100011111011011110010|00 0 0000 00 00 0000000 00000000 000 0010 000 0111 / 15776790092376441227 1101101011110010011010110|00 0 0000 00 00 0000000 00000000 000 0110 001 011 / 23665185138564661841 101001000011010111010000010|00 0 0000 00 00 0000000 00000000 001 0010 100 01 / 35497777707846992762 1111011001010000101110000110|00 \ 17748888853923496381 1111011001010000101110000110|0 0000 00 00 0000000 00000000 011 0111 101 000 0 0000 00 00 0000000 00000000 011 0111 101 / 26623333280885244572 101110001011110010001010010010|00 \ 13311666640442622286 101110001011110010001010010010|0 0000 00 00 0000000 00000001 010 0111 0000 \ 6655833320221311143 101110001011110010001010010010|0 0000 00 00 0000000 00000001 010 0111 000 0 0000 00 00 0000000 00000001 010 0111 / 9983749980331966715 10001010100011010110011110110110|00 0 0000 00 00 0000000 00000011 111 011 / 14975624970497950073 110011111101010000011011100100010|00 0 0000 00 00 0000000 00001011 110 01 / 22463437455746925110 10011011110111110001010010101100110|00 \ 11231718727873462555 10011011110111110001010010101100110|0 0000 00 00 0000000 00100011 011 000 0 0000 00 00 0000000 00100011 011 / 16847578091810193833 111010011100111010011111000000110010|00 0 0000 00 00 0000000 01101010 01 / 25271367137715290750 10101111010110101111011101000010010110|00 \ 12635683568857645375 10101111010110101111011101000010010110|0 0000 00 00 0000001 00111111 000 0 0000 00 00 0000001 00111111 / 18953525353286468063 1000001110000100001110010111000111000010|00 0 0000 00 00 0000011 1011111 / 28430288029929702095 11000101010001100101011000101010101000110|00 0 0000 00 00 0001011 001111 / 42645432044894553143 1001001111110100110000001001111111111010010|00 0 0000 00 00 0100001 10111 / 63968148067341829715 11011101111011110010000011101111111101110110|00 0 0000 00 00 1100101 0011 / 95952222101012744573 1010011001110011010110001011001111111001100010|00 0 0000 00 10 0101111 101 / 143928333151519116860 11111001101011010000010100001101111101100100110|00 \ 71964166575759558430 11111001101011010000010100001101111101100100110|0 0000 01 11 0001111 0000 \ 35982083287879779215 11111001101011010000010100001101111101100100110|0 0000 01 11 0001111 000 0 0000 01 11 0001111 / 53973124931819668823 1011101101000001110000111100101001111000101110010|00 0 0001 01 01 010111 / 80959687397729503235 100011000111000101010010110101111101101010001010110|00 0 0100 00 00 00011 / 121439531096594254853 1101001010101001111111000100001111000111110100000010|00 0 1100 00 00 0101 / 182159296644891382280 100111011111111101111101001100101101010111011100000110|01 \ 91079648322445691140 100111011111111101111101001100101101010111011100000110|0 0100 00 01 00001 \ 45539824161222845570 100111011111111101111101001100101101010111011100000110|0 0100 00 01 0001 \ 22769912080611422785 100111011111111101111101001100101101010111011100000110|0 0100 00 01 001 0 0100 00 01 / 34154868120917134178 1110110011111111001110111100110001000000110010100010010|11 \ 17077434060458567089 1110110011111111001110111100110001000000110010100010010|0 1100 01 011 0 1100 01 / 25616151090687850634 101100011011111101101100110110010011000010010111100111000|10 \ 12808075545343925317 101100011011111101101100110110010011000010010111100111000|0 0101 010 0 0101 / 19212113318015887976 10000101010011111001000110100010111001000111000110110101001|10 \ 9606056659007943988 10000101010011111001000110100010111001000111000110110101001|1 00010 \ 4803028329503971994 10000101010011111001000110100010111001000111000110110101001|1 0010 \ 2401514164751985997 10000101010011111001000110100010111001000111000110110101001|1 010 1 / 3602271247127978996 110001111111011101011010011101000101011010101010100011111101|00 \ 1801135623563989498 110001111111011101011010011101000101011010101010100011111101|0 \ 900567811781994749 110001111111011101011010011101000101011010101010100011111101| --- + 1729382256910270491 11|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 000011 011 / 2594073385365405737 1001|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 001010 01 / 3891110078048108606 11011|00 \ 1945555039024054303 11011|0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 011111 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 00 011111 / 2918332558536081455 1010001|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 000 01 01111 / 4377498837804122183 11110011|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 001 00 0111 / 6566248256706183275 1011011001|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0000 011 01 011 / 9849372385059274913 100010001011|00 0 0000 00 00 0000000 00000000 000 0000 000 00000 0001 010 00 01 / 14774058577588912370 1100110100001|00 \ 7387029288794456185 1100110100001|0 0000 00 00 0000000 00000000 000 0000 000 00000 0011 110 01 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 0011 110 01 / 11080543933191684278 100110011100011|00 \ 5540271966595842139 100110011100011|0 0000 00 00 0000000 00000000 000 0000 000 00000 1011 011 000 0 0000 00 00 0000000 00000000 000 0000 000 00000 1011 011 / 8310407949893763209 1110011010101001|00 0 0000 00 00 0000000 00000000 000 0000 000 00010 0010 01 / 12465611924840644814 101011001111111011|00 \ 6232805962420322407 101011001111111011|0 0000 00 00 0000000 00000000 000 0000 000 00110 0111 000 0 0000 00 00 0000000 00000000 000 0000 000 00110 0111 / 9349208943630483611 10000001101111110001|00 0 0000 00 00 0000000 00000000 000 0000 000 10011 011 / 14023813415445725417 110000101001111010011|00 0 0000 00 00 0000000 00000000 000 0000 001 11010 01 / 21035720123168588126 10010001111101101111001|00 \ 10517860061584294063 10010001111101101111001|0 0000 00 00 0000000 00000000 000 0000 101 01111 000 0 0000 00 00 0000000 00000000 000 0000 101 01111 / 15776790092376441095 110110101111001001101011|00 0 0000 00 00 0000000 00000000 000 0010 000 0111 / 23665185138564661643 10100100001101011101000001|00 0 0000 00 00 0000000 00000000 000 0110 001 011 / 35497777707846992465 111101100101000010111000011|00 0 0000 00 00 0000000 00000000 001 0010 100 01 / 53246666561770488698 10111000101111001000101001001|00 \ 26623333280885244349 10111000101111001000101001001|0 0000 00 00 0000000 00000000 011 0111 101 000 0 0000 00 00 0000000 00000000 011 0111 101 / 39934999921327866524 1000101010001101011001111011011|00 \ 19967499960663933262 1000101010001101011001111011011|0 0000 00 00 0000000 00000001 010 0111 0000 \ 9983749980331966631 1000101010001101011001111011011|0 0000 00 00 0000000 00000001 010 0111 000 0 0000 00 00 0000000 00000001 010 0111 / 14975624970497949947 11001111110101000001101110010001|00 0 0000 00 00 0000000 00000011 111 011 / 22463437455746924921 1001101111011111000101001010110011|00 0 0000 00 00 0000000 00001011 110 01 / 33695156183620387382 11101001110011101001111100000011001|00 \ 16847578091810193691 11101001110011101001111100000011001|0 0000 00 00 0000000 00100011 011 000 0 0000 00 00 0000000 00100011 011 / 25271367137715290537 1010111101011010111101110100001001011|00 0 0000 00 00 0000000 01101010 01 / 37907050706572935806 100000111000010000111001011100011100001|00 \ 18953525353286467903 100000111000010000111001011100011100001|0 0000 00 00 0000001 00111111 000 0 0000 00 00 0000001 00111111 / 28430288029929701855 1100010101000110010101100010101010100011|00 0 0000 00 00 0000011 1011111 / 42645432044894552783 100100111111010011000000100111111111101001|00 0 0000 00 00 0001011 001111 / 63968148067341829175 1101110111101111001000001110111111110111011|00 0 0000 00 00 0100001 10111 / 95952222101012743763 101001100111001101011000101100111111100110001|00 0 0000 00 00 1100101 0011 / 143928333151519115645 1111100110101101000001010000110111110110010011|00 0 0000 00 10 0101111 101 / 215892499727278673468 101110110100000111000011110010100111100010111001|00 \ 107946249863639336734 101110110100000111000011110010100111100010111001|0 0000 01 11 0001111 0000 \ 53973124931819668367 101110110100000111000011110010100111100010111001|0 0000 01 11 0001111 000 0 0000 01 11 0001111 / 80959687397729502551 10001100011100010101001011010111110110101000101011|00 0 0001 01 01 010111 / 121439531096594253827 110100101010100111111100010000111100011111010000001|00 0 0100 00 00 00011 / 182159296644891380741 10011101111111110111110100110010110101011101110000011|00 0 1100 00 00 0101 / 273238944967337071112 111011001111111100111011110011000100000011001010001001|01 \ 136619472483668535556 111011001111111100111011110011000100000011001010001001|0 0100 00 01 00001 \ 68309736241834267778 111011001111111100111011110011000100000011001010001001|0 0100 00 01 0001 \ 34154868120917133889 111011001111111100111011110011000100000011001010001001|0 0100 00 01 001 0 0100 00 01 / 51232302181375700834 10110001101111110110110011011001001100001001011110011011|11 \ 25616151090687850417 10110001101111110110110011011001001100001001011110011011|0 1100 01 011 0 1100 01 / 38424226636031775626 1000010101001111100100011010001011100100011100011011010011|10 \ 19212113318015887813 1000010101001111100100011010001011100100011100011011010011|0 0101 010 0 0101 / 28818169977023831720 11000111111101110101101001110100010101101010101010001111010|10 \ 14409084988511915860 11000111111101110101101001110100010101101010101010001111010|1 00010 \ 7204542494255957930 11000111111101110101101001110100010101101010101010001111010|1 0010 \ 3602271247127978965 11000111111101110101101001110100010101101010101010001111010|1 010 1 / 5403406870691968448 1001010111111001100000111101011101000000111111111110101110000|00 \ 2701703435345984224 1001010111111001100000111101011101000000111111111110101110000|0 \ 1350851717672992112 1001010111111001100000111101011101000000111111111110101110000|
We can also tilt the other way, making the carry bit go straight down. There's a vertical left edge when there is a carry at the beginning, else it recedes. No matter which way we tilt, it's never clear cut because the automaton still says that there are three inputs. That includes one from the left, which with this tilt seems to come from two positions to the left.
pl -oA '$a = eval "0b$_"; $l = length; -$l, map $a|($_<<$l), 0..3 ' \
'if( $_ < 0 ) { $l = -$_; $m = 9; next }
$n = $_; $b = 2; $i = 63; $p = 85 - $l; $o = -1; echo "-" x $m if $ARGIND > 1; $m = 3;
while( 1 ) {
$po = $p + ++$o;
echo qw(\\ / +)[$b], Form( "%20d %1:*b", $_, ++$i ) =~ s/.{$po}\K( *)/"\\" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
die "tail too short" if ++$p > 85;
} ' 0011 01011 10111 1111100111 000000001111111111pl -oA '$a = eval "0b$_"; $l = length; -$l, map $a|($_<<$l), 0..3 ' \
'if( $_ < 0 ) { $l = -$_; $m = 9; next }
$n = $_; $b = 2; $i = 63; $p = 85 - $l; $o = -1; e "-" x $m if $I > 1; $m = 3;
while( 1 ) {
$po = $p + ++$o;
e qw(\\ / +)[$b], F( "%20d %1:*b", $_, ++$i ) =~ s/.{$po}\K( *)/"\\" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
die "tail too short" if ++$p > 85;
} ' 0011 01011 10111 1111100111 000000001111111111+ 3 \00 11 / 5 \10 1 / 8 10\00 \ 4 10\0 \ 2 10\ --- + 19 1\00 11 / 29 11\10 1 / 44 1011\00 \ 22 1011\0 \ 11 1011\ --- + 35 10\00 11 / 53 110\10 1 / 80 10100\00 \ 40 10100\0 \ 20 10100\ --- + 51 11\00 11 / 77 1001\10 1 / 116 11101\00 \ 58 11101\0 \ 29 11101\ --------- + 11 \0 1 011 / 17 1\0 0 01 / 26 11\0 \ 13 11\1 00 1 / 20 1010\0 \ 10 1010\ --- + 43 1\0 1 011 / 65 100\0 0 01 / 98 1100\0 \ 49 1100\1 00 1 / 74 100101\0 \ 37 100101\ --- + 75 10\0 1 011 / 113 111\0 0 01 / 170 10101\0 \ 85 10101\1 00 1 / 128 1000000\0 \ 64 1000000\ --- + 107 11\0 1 011 / 161 1010\0 0 01 / 242 11110\0 \ 121 11110\1 00 1 / 182 1011011\0 \ 91 1011011\ --------- + 23 \10 111 / 35 10\00 11 / 53 110\10 1 / 80 10100\00 \ 40 10100\0 \ 20 10100\ --- + 55 1\10 111 / 83 101\00 11 / 125 1111\10 1 / 188 101111\00 \ 94 101111\0 \ 47 101111\ --- + 87 10\10 111 / 131 1000\00 11 / 197 11000\10 1 / 296 1001010\00 \ 148 1001010\0 \ 74 1001010\ --- + 119 11\10 111 / 179 1011\00 11 / 269 100001\10 1 / 404 1100101\00 \ 202 1100101\0 \ 101 1100101\ --------- + 999 \111 110 0111 / 1499 10\111 011 011 / 2249 1000\110 010 01 / 3374 11010\010 \ 1687 11010\111 0010 111 / 2531 1001111\000 11 / 3797 11101101\010 1 / 5696 1011001000\000 \ 2848 1011001000\00 \ 1424 1011001000\0 \ 712 1011001000\ --- + 2023 1\111 110 0111 / 3035 101\111 011 011 / 4553 10001\110 010 01 / 6830 110101\010 \ 3415 110101\111 0010 111 / 5123 10100000\000 11 / 7685 111100000\010 1 / 11528 10110100001\000 \ 5764 10110100001\00 \ 2882 10110100001\0 \ 1441 10110100001\ --- + 3047 10\111 110 0111 / 4571 1000\111 011 011 / 6857 11010\110 010 01 / 10286 1010000\010 \ 5143 1010000\111 0010 111 / 7715 11110001\000 11 / 11573 1011010011\010 1 / 17360 100001111010\000 \ 8680 100001111010\00 \ 4340 100001111010\0 \ 2170 100001111010\ --- + 4071 11\111 110 0111 / 6107 1011\111 011 011 / 9161 100011\110 010 01 / 13742 1101011\010 \ 6871 1101011\111 0010 111 / 10307 101000010\000 11 / 15461 1111000110\010 1 / 23192 101101010011\000 \ 11596 101101010011\00 \ 5798 101101010011\0 \ 2899 101101010011\ --------- + 1023 \0000 0 0001111111111 / 1535 \0000 0 010111111111 / 2303 \0000 1 00011111111 / 3455 \0001 1 0101111111 / 5183 \0101 0 000111111 / 7775 \1111 0 01011111 / 11663 10\1101 1 0001111 / 17495 1000\1000 1 010111 / 26243 11001\1010 0 00011 / 39365 1001100\1110 0 0101 / 59048 11100110\1010 \ 29524 11100110\1 0001010 \ 14762 11100110\1 001010 \ 7381 11100110\1 01010 1 / 11072 1010110100\0000 \ 5536 1010110100\000 \ 2768 1010110100\00 \ 1384 1010110100\0 \ 692 1010110100\ --- + 263167 1\0000 0 0001111111111 / 394751 11\0000 0 010111111111 / 592127 1001\0000 1 00011111111 / 888191 11011\0001 1 0101111111 / 1332287 1010001\0101 0 000111111 / 1998431 11110011\1111 0 01011111 / 2997647 1011011011\1101 1 0001111 / 4496471 100010010011\1000 1 010111 / 6744707 1100110111010\1010 0 00011 / 10117061 100110100101111\1110 0 0101 / 15175592 1110011110001111\1010 \ 7587796 1110011110001111\1 0001010 \ 3793898 1110011110001111\1 001010 \ 1896949 1110011110001111\1 01010 1 / 2845424 101011011010101111\0000 \ 1422712 101011011010101111\000 \ 711356 101011011010101111\00 \ 355678 101011011010101111\0 \ 177839 101011011010101111\ --- + 525311 10\0000 0 0001111111111 / 787967 110\0000 0 010111111111 / 1181951 10010\0000 1 00011111111 / 1772927 110110\0001 1 0101111111 / 2659391 10100010\0101 0 000111111 / 3989087 111100110\1111 0 01011111 / 5983631 10110110100\1101 1 0001111 / 8975447 1000100011110\1000 1 010111 / 13463171 11001101011011\1010 0 00011 / 20194757 1001101000010010\1110 0 0101 / 30292136 11100111000111000\1010 \ 15146068 11100111000111000\1 0001010 \ 7573034 11100111000111000\1 001010 \ 3786517 11100111000111000\1 01010 1 / 5679776 1010110101010101010\0000 \ 2839888 1010110101010101010\000 \ 1419944 1010110101010101010\00 \ 709972 1010110101010101010\0 \ 354986 1010110101010101010\ --- + 787455 11\0000 0 0001111111111 / 1181183 1001\0000 0 010111111111 / 1771775 11011\0000 1 00011111111 / 2657663 1010001\0001 1 0101111111 / 3986495 11110011\0101 0 000111111 / 5979743 1011011001\1111 0 01011111 / 8969615 100010001101\1101 1 0001111 / 13454423 1100110101001\1000 1 010111 / 20181635 100110011111100\1010 0 00011 / 30272453 1110011011110101\1110 0 0101 / 45408680 101011010011100001\1010 \ 22704340 101011010011100001\1 0001010 \ 11352170 101011010011100001\1 001010 \ 5676085 101011010011100001\1 01010 1 / 8514128 10000001111010100101\0000 \ 4257064 10000001111010100101\000 \ 2128532 10000001111010100101\00 \ 1064266 10000001111010100101\0 \ 532133 10000001111010100101\
Flagtail Fish
You'll have noticed the colouring of tails in the output. I cheated a bit because these are added not by pl but done while rendering the web page. Once we know how the sequence went, in hindsight we can colour tail bits according to what they will ultimately cause. That way the colour stripes show the evolution of neighbouring bits which reach the end as the same value. They're bold, when they match their final value. On any decent terminal emulator, you can pipe the output of any other command on this page through this to add colouring:
pl -ln 'if( /[01]$/ ) {
unshift @a, $_;
} else {
@l = $b = 0;
for( @a ) {
if( /$b$/ ) { ++$l[0] } else { unshift @l, 1; $b ^= 1 }
$c = 2 - $b; $d = $b; $l = length;
for $x ( @l ) {
s/($d+)/\e[1m$1\e[22m/g, s/^/\e[3${c}m/ for substr $_, $l -= $x, $x;
$d ^= 1; $c ^= 3
}
$_ .= "\e[m";
}
say pop @a while @a; say;
} 'You would want to get Collatz colouring automatically. Let's define a cpl command that you can substitute for pl in any of the other examples. Or even redefine pl itself (guarding against endless recursion), so you can run all examples unmodified. On most normal Shells, including on Windows, one of these will give you that, when replacing pl … with the command above this paragraph:
cpl() {
pl "$@ " |
pl ...
}
pl() {
perl -S pl "$@ " |
perl -S pl ...
}"You're bad!" – "I need a 2nd opinion." – "You're ugly too!" 🐽
The Good, the Bad and the UglyMore salient definitions: All tails of length l fall into three categories:
Good are all the tails that stop in l steps. I suffix them with '-' meaning till here: you only need to look that far from the end to know that all numbers with this tail stop.
Bad are all other tails that don't stop in l steps. I suffix them with '+' meaning longer tails need to be looked at to decide whether they'll stop. Leading spaces aren't quite like for the Good ones. There it means no need to explore deeper. Here one space means both next bit-values are part of a Bad tail, two spaces mean all four next 2-bit-values, etc. E.g., '100011011+' appears in the length 12 column below, meaning all eight possibilities to prepend three bits are Bad. And one of them, '011100011011+' appears in the length 17 column, meaning all 32 possibilities to prepend another five bits are Bad. In other words, in nine and twelve steps, these numbers' sequences rise to numbers that are more than eight and 32 times the originals. Thus, they're unstoppable within that inspected length.
If you need the actual expansion of those spaces into all separate tails, here's an example. This is piped, so you could pass in a whole file:
echo ' 100011011+ ' |
pl -nl 's/( +)/$l = length($1); "{" . join( ",", map Form( "%0${l}b" ), 0..2**$l-1 ) . "}"/e;
say for glob 'echo ' 100011011+ ' |
pl -nl 's/( +)/$l = length($1); "{" . join( ",", map F( "%0${l}b" ), 0..2**$l-1 ) . "}"/e;
say for glob '000100011011+ 001100011011+ 010100011011+ 011100011011+ 100100011011+ 101100011011+ 110100011011+ 111100011011+
Ugly are a subset of the Bad that are obvious just by looking at them. I suffix them with '*' (a screwed '+'). Probably the only pattern where this is so, are the tails of l = i + j, where j is the number of final 1-bits and 2i < (3/2)j (using a slightly stricter upper bound of 3n/2), or equivalently 2l < 3j. That's because the sequence will go straight up j times. Even if we thereafter halved i times, it wouldn't be enough to stop.
Where do lizards get new tails?
Exploring the tree fully to a length of 17, we get the following tails (and more, ranging from 5kb to 3.3Gb compressed, for download below). Fairly many lengths are lumped in with the lower neighbour because there are no new Good tails at those lengths. This is because of how growing powers of 2 and 3 overtake each other irregularly. A new Good tail correlates with the Ugly getting one bit longer with each column to the left, which follows from the way they grow.
I don't repeat Good tails from the right – because they're Good, no matter how many more bits you stick in front. That makes this look heavily distorted in favour of Bad tails. But the opposite is true because the shorter Good tails cover the lion's share of numbers. Colour isn't striped as I list only initial tails, not full sequences as above.
| 17, 16 | 15 | 14, 13 | 12 | 11, 10 | 9, 8 | 7 | 6, 5 | 4 | 3, 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
| 30, 29 | 28, 27 | 26 | 25, 24 | 23 | 22, 21 | 20 | 19, 18 | |||
| 40 | 39 | 38, 37 | 36, 35 | 34 | 33, 32 | 31 | ||||
The Good tails are the solutions. If just by looking at sufficiently long tails, each were ultimately a Good tail, then proof by full induction would be successful.
Renewable energy? I'm a big fan! ♾️
Bigger Bit by BitOf all lengths up to 40 which I have tested, I found the following distribution. I show only the lengths producing new Good tails and each time the percentage of all possible numbers of that bit length. As I show below at least one in two lengthenings of a Bad tail is again Bad. Thus, the Bad tails can never reach 0%. And the new Good percentage can at best be half the previous Bad percentage. Usually it falls far short of that because it often takes several more steps to stop and there is only exactly one shortest Good tail lengthening it. But it also can't permanently fall to 0% because I also show that it's always possible to find a Good tail by lengthening a Bad tail.
| l | 2l numbers | Bad tails | new Good tails | contain Good tails | |||
|---|---|---|---|---|---|---|---|
| 1 | 2 | 1 | 50.000% | 1 | 50.000% | 1 | 50.000% |
| 2 | 4 | 1 | 25.000% | 1 | 25.000% | 3 | 75.000% |
| 4 | 16 | 3 | 18.750% | 1 | 6.250% | 13 | 81.250% |
| 5 | 32 | 4 | 12.500% | 2 | 6.250% | 28 | 87.500% |
| 7 | 128 | 13 | 10.156% | 3 | 2.344% | 115 | 89.844% |
| 8 | 256 | 19 | 7.422% | 7 | 2.734% | 237 | 92.578% |
| 10 | 1,024 | 64 | 6.250% | 12 | 1.172% | 960 | 93.750% |
| 12 | 4,096 | 226 | 5.518% | 30 | 0.732% | 3,870 | 94.482% |
| 13 | 8,192 | 367 | 4.480% | 85 | 1.038% | 7,825 | 95.520% |
| 15 | 32,768 | 1,295 | 3.952% | 173 | 0.528% | 31,473 | 96.048% |
| 16 | 65,536 | 2,114 | 3.226% | 476 | 0.726% | 63,422 | 96.774% |
| 18 | 262,144 | 7,495 | 2.859% | 961 | 0.367% | 254,649 | 97.141% |
| 20 | 1,048,576 | 27,328 | 2.606% | 2,652 | 0.253% | 1,021,248 | 97.394% |
| 21 | 2,097,152 | 46,611 | 2.223% | 8,045 | 0.384% | 2,050,541 | 97.777% |
| 23 | 8,388,608 | 168,807 | 2.012% | 17,637 | 0.210% | 8,219,801 | 97.988% |
| 24 | 16,777,216 | 286,581 | 1.708% | 51,033 | 0.304% | 16,490,635 | 98.292% |
| 26 | 67,108,864 | 1,037,374 | 1.546% | 108,950 | 0.162% | 66,071,490 | 98.454% |
| 27 | 134,217,728 | 1,762,293 | 1.313% | 312,455 | 0.233% | 132,455,435 | 98.687% |
| 29 | 536,870,912 | 6,385,637 | 1.189% | 663,535 | 0.124% | 530,485,275 | 98.811% |
| 31 | 2,147,483,648 | 23,642,078 | 1.101% | 1,900,470 | 0.088% | 2,123,841,570 | 98.899% |
| 32 | 4,294,967,296 | 41,347,483 | 0.963% | 5,936,673 | 0.138% | 4,253,619,813 | 99.037% |
| 34 | 17,179,869,184 | 151,917,636 | 0.884% | 13,472,296 | 0.078% | 17,027,951,548 | 99.116% |
| 35 | 34,359,738,368 | 263,841,377 | 0.768% | 39,993,895 | 0.116% | 34,095,896,991 | 99.232% |
| 37 | 137,438,953,472 | 967,378,591 | 0.704% | 87,986,917 | 0.064% | 136,471,574,881 | 99.296% |
| 39 | 549,755,813,888 | 3,611,535,862 | 0.657% | 257,978,502 | 0.047% | 546,144,278,026 | 99.343% |
| 40 | 1,099,511,627,776 | 6,402,835,000 | 0.582% | 820,236,724 | 0.075% | 1,093,108,792,776 | 99.418% |
The Collatz community has tested all numbers up to 68 bits long. It was found experimentally that they all do stop ultimately. But, impressive as that may be, that only explored a relatively shallow tree up to depth 68 – a mere drop in the sea of infinity. A tiny fraction of those numbers won't stop in 68 steps. E.g., if one of them stopped in 100 steps, that's to say that those 68 bits become a Good tail if padded with 0-bits to length l = 100. But then, flipping that 100th bit to '1' will give a different number which is a Bad tail.
The next frontier are the 69 bit numbers with a leading 1-bit. It's a waste of time to test all those numbers. Given my list of all Bad tails of length 40, it suffices to test only those 0.58% of 69 bit numbers ending in one of those tails. And I'd assume there is a record of how many steps it took all the tested 68 bit numbers to stop. Only those probably under 0.2% that took more than 68 steps constitute Bad tails. By testing "only" these trillion (for Americans & other short-scalers: quintillion) problematic cases successfully we'd know that they all stop.
What's a collapsed horse enclosure?
Alas I can derive from any given tail both Good and Bad tails of any length. Because of the automaton rule and how bits tumble down the diagonal to ultimately influence the then lowest bit, they come down as two distinct values. One of them will halve the number, which sometimes gives a Good tail – when that number was less than double the original. The other will again drive the sequence up. Bit l determines step l – not alone in an obvious way, which is why it's hard to predict. But it alone is enough to steer step l.
It's trivial to derive a Bad tail from a Good tail. You only need to flip its first bit. Remember it's Good because that's the minimum length at which it stops. That means the 1st bit, whatever its value, will reach the lowest position as a 0-bit in l - 1 steps. Thus, flipping whatever that came from will make it arrive as a 1-bit, which will make the number grow again.
It's trivial to lengthen any given Bad tail, by enforcing henceforth getting odd numbers: continue beyond l steps, till there is a 0-bit at the end. Replace where it came from in the original number with a 1-bit and start over. This is flipping because continuing beyond l bits meant padding with 0-bits. E.g., '1011' reaches a 0-bit at the end in 5 steps, so start over with '11011'. This will get a final 0-bit in 9 steps. Start over with '100011011', which will end in a 0-bit in 10 steps. Start over with '1100011011'. Note that I've glossed over where we found 1-bits at the end. These are already Bad tails.
This can be optimised with a modified variant of above. It takes only one argument and prepends both '0' and '1' to it but still outside of the diagonal. It exits when we've used up l steps and if the next low bit is a '1'. Here it's the 2nd case that ends not just with '1' but '01111'. Thereby we know that the next four 1-bits are as desired, and the 5th needs to be flipped, i.e. we next prepend '10001'. Doing it semi-graphically is cute but hardwired to 64 bits. It would again need bignum and just counting bits, instead of ever longer sequences. Writing an endless loop that will catapult any Bad tail to the sky is left as an exercise for you:
pl -oA '$a = eval "0b$_"; $l = length; $a, $a|(1<<$l) ' \
'if( $_ < 0 ) { $l = -$_; next }
$n = $_; $b = 2; $p = 85 - $l; echo "---" if $ARGIND;
while( 1 ) {
echo qw(\\ / +)[$b], Form( "%20d %1:64b" ) =~ s/.{$p}\K( *)/"\\" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
if( ++$p > 85 ) { echo "tail too short"; exit if $b; last }
} ' 1100011011pl -oA '$a = eval "0b$_"; $l = length; $a, $a|(1<<$l) ' \
'if( $_ < 0 ) { $l = -$_; next }
$n = $_; $b = 2; $p = 85 - $l; e "---" if $I;
while( 1 ) {
e qw(\\ / +)[$b], F( "%20d %1:64b" ) =~ s/.{$p}\K( *)/"\\" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
if( ++$p > 85 ) { e "tail too short"; exit if $b; last }
} ' 1100011011+ 795 \1100011 0 11 / 1193 10\0101010 0 1 / 1790 110\1111111 0 \ 895 110\1111111 / 1343 10100\111111 / 2015 111110\11111 / 3023 10111100\1111 / 4535 1000110110\111 / 6803 11010100100\11 / 10205 1001111101110\1 / 15308 11101111001100\ tail too short --- + 1819 1\1100011 0 11 / 2729 101\0101010 0 1 / 4094 1111\1111111 0 \ 2047 1111\1111111 / 3071 101111\111111 / 4607 10001111\11111 / 6911 110101111\1111 / 10367 10100001111\111 / 15551 111100101111\11 / 23327 10110110001111\1 / 34991 1000100010101111\ tail too short
Inversely it's trivial to find a Good tail ending in any given Bad tail, by enforcing henceforth getting even numbers: just do the opposite of above. Continue beyond l steps, till you either reach a smaller number or there is a 1-bit at the end. If smaller, pad the original number with that many 0-bits and you're done. Else replace where the 1-bit came from in the original number with a 1-bit (it must have gotten flipped on the way down) and start over. E.g., '1010011011' ends in a 1-bit in 11 steps. Therefore try '11010011011', which gives a 1-bit in 13 steps. Found it, '1011010011011' stops. You either already get final 0-bits or you flip to produce them. Then you're guaranteed to find a Good tail, by repeatedly halving.
As another example, let's try an Ugly with many 1-bits, only inverting the exit condition. This one will end in '1000', i.e. three 0-bits as desired and a 1-bit to be flipped. Thus, you can prepend that same '1000', except it's two bits longer than what's actually needed to stop. Actually you'd first check if there are enough 0-bits to stop – in this case two, since the last number is less than 4x the original:
pl -oA '$a = eval "0b$_"; $l = length; $a, $a|(1<<$l) ' \
'if( $_ < 0 ) { $l = -$_; next }
$n = $_; $b = 2; $p = 85 - $l; echo "---" if $ARGIND;
while( 1 ) {
echo qw(\\ / +)[$b], Form( "%20d %1:64b" ) =~ s/.{$p}\K( *)/"\\" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
if( ++$p > 85 ) { echo "tail too short"; exit if !$b; last }
} ' 110000001111111111111111pl -oA '$a = eval "0b$_"; $l = length; $a, $a|(1<<$l) ' \
'if( $_ < 0 ) { $l = -$_; next }
$n = $_; $b = 2; $p = 85 - $l; e "---" if $I;
while( 1 ) {
e qw(\\ / +)[$b], F( "%20d %1:64b" ) =~ s/.{$p}\K( *)/"\\" . 0 x length $1/er;
last if $_ < $n;
if( $b = $_ & 1 ) { ++($_ += $_ >> 1) } else { $_ >>= 1 }
if( ++$p > 85 ) { e "tail too short"; exit if !$b; last }
} ' 110000001111111111111111+ 12648447 \11000000 1111111111111111 / 18972671 10\01000010 111111111111111 / 28459007 110\11001000 11111111111111 / 42688511 10100\01011010 1111111111111 / 64032767 111101\00010000 111111111111 / 96049151 10110111\00110010 11111111111 / 144073727 1000100101\10011000 1111111111 / 216110591 11001110000\11001010 111111111 / 324165887 1001101010010\01100000 11111111 / 486248831 11100111110111\00100010 1111111 / 729373247 1010110111100101\01101000 111111 / 1094059871 100000100110110000\00111010 11111 / 1641089807 1100001110100010000\10110000 1111 / 2461634711 100100101011100110010\00010010 111 / 3692452067 1101110000010110010110\00111000 11 / 5538678101 101001010001000011000010\10101010 1 / 8308017152 1111011110011001001001000\00000000 \ 4154008576 1111011110011001001001000\0000000 \ 2077004288 1111011110011001001001000\000000 \ 1038502144 1111011110011001001001000\00000 \ 519251072 1111011110011001001001000\0000 \ 259625536 1111011110011001001001000\000 \ 129812768 1111011110011001001001000\00 \ 64906384 1111011110011001001001000\0 \ 32453192 1111011110011001001001000\ tail too short
Note that by prepending 1-bits we get utterly different numbers! I don't conclude anything about any one individual tail – that's mostly found by calculating it through. What I do show pertains to how the whole set of numbers behaves – relative to characteristic endings. Thus, the above is totally different from claiming that any Bad tail will ultimately become Good, just by trying long enough. On the contrary, since Bad tails can be lengthened infinitely, giving ever longer Bad tails, they never die out. Every shorter Bad tail is at the end of infinitely many longer ones.
I would look more mountainous – if I were so inclined. 🙃
TerraformingAbove we did a straight rise to turn any tail into a maximally Bad one, as well as a straight descent to a Good one. But these are just the extremes. Any other silhouette can be crafted, with the limitation that it stops when reaching a smaller number – though for effect we could exceptionally continue towards total stopping… In pixel art it could be rendered proportionally, but in ASCII art the formula gives a slope up almost ¼ less weight than a slope down. Let's do Mounts Lhotse & Everest – sideways for simplicity:
pl '$j = 0; $i = 40; $n = $_ = 0b100000000011011111;
while( 1 ) {
form "%*b %s", $i, $_, ("\\", " /")[$j > $i];
last if $_ < $n;
$j = $i;
if( $_ & 1 ) { ++$i; ++($_ += $_ >> 1) } else { --$i; $_ >>= 1 }
} 'pl '$j = 0; $i = 40; $n = $_ = 0b100000000011011111;
while( 1 ) {
f "%*b %s", $i, $_, ("\\", " /")[$j > $i];
last if $_ < $n;
$j = $i;
if( $_ & 1 ) { ++$i; ++($_ += $_ >> 1) } else { --$i; $_ >>= 1 }
} ' 100000000011011111 \
110000000101001111 \
1001000000111110111 \
1101100001011110011 \
10100010010001101101 \
11110011011010100100 \
1111001101101010010 /
111100110110101001 /
1011011010001111110 \
101101101000111111 /
1000100011101011111 \
1100110101100001111 \
10011010000010010111 \
11100111000011100011 \
101011010100101010101 \
1000000111111000000000 \
100000011111100000000 /
10000001111110000000 /
1000000111111000000 /
100000011111100000 /
10000001111110000 /Cycles?
Another way in which Collatz could be wrong is if there were more cycles. Looking at the odds halved optimisation is equivalent because any unoptimised even cycle element would also be halved. E.g., Collatz' cycle 1-4-2-1 is a superset of the optimised function's cycle 1-2-1. If the tail-theory developed above were directly relevant to cycles, all other numbers ending in '01' would form a cycle too. Instead the way they stop initially diverges: 5-8-4, 9-14-7, 13-20-10, 17-26-13, 21-32-16…
Good Given
A picture doesn't always say more than a thousand words. Back when I thought ternary or base 6 might be helpful, I rendered pretty trees for 011, 0111, 01111, 011111 and 111111, but I couldn't spot anything useful, even though the following info is hidden in there.
Only deriving longer Good tails gives us all tails: for every Bad tail there is only exactly one shortest Good tail lengthening it. This is because I force every lengthening to be a step down, halving the last result. If I flip even only one bit, the next result will be over three times as big. That will then require one or even two more steps to stop.
As we lengthened a Bad tail in such a way that the next prepended bit would drive the sequence down, at each step we also found a longer Bad tail. Either the 0-bit was Bad and we had to flip that, or the 0-bit was Good, and then a 1-bit would give a Bad tail. Either way, at each step we lengthened there was both a Bad extension and another that was itself Good or at least a step down. By the time we found the Good tail, for every step we had also found a longer Bad tail. If we do this repeatedly starting with every shortest Bad tail, with few sequences needing to be calculated, we will raise the length of all explored tails, finding all the Bad ones as a by-product.
E.g., starting with the shortest Bad tail '1' we find a Good tail '01'. Flipping the leading 0-bits there's a new Bad tail '11', which doesn't even require testing. Diving deeper with that, '011' is undecided but goes down. Then '111' must be a Bad (actually Ugly) tail, and I continue with '0011', which is Good, so '1011' must again be Bad. Both new Bad tails must now be dealt with in the same way. Always starting with the shortest ones, gives a different order from my table above but systematically ensures that we cover all tails up to a certain length. Since '0111' goes down, '1111' must be a Bad (actually Ugly). Then the other scenario occurs: '00111' is Bad, so for the 1st time in this paragraph, we must flip the 1st bit to get a Good '10111'. From the previous round we still have the 2nd Bad tail '1011' to deal with, and then from this round one new tail of length 4 and two of length 5: '1111', '00111', '11011'.
Unlike my initial result of a naïve brute-force search over bit-lengths, we're now truly developing this as a tree. As a bounty, the lower part just came to us without calculations. Instead of the order above, sorted by low bits, it's clearer to invert each group around the generating Good tail, so that flipped bits at the tip of each Bad face their Good counterpart. Shown here is only one round, going from an Ugly (where 24 spaces grouped 224 different actual Bad tails) to its shortest Good extension. I.e. by doubling that already huge number of tails, only a single Good one appears (more will from each new Bad at greater lengths):
|
Approximation
We saw that every tail predicts the next l steps a sequence will take – no matter what bits it gets prefixed with. We have one self-contained evolution in the triangles (in the examples) on the right. It drives the separate evolution to the left of the divide. Therefore we can express the effect of the tail after l steps as a factor. Since the tail melts completely within l steps, we can just as well apply that factor to any bit sequence we prefix directly, i.e. appending any tail, l 0-bits are just as good.
What actual number will any prefix with this tail reach after l steps? Let u be the number of steps up a Good or Bad tail takes, i.e. the number of forward slashes, or the cumulated width of red stripes. Then after l steps the result of applying the sequence to any number n with that tail will be roughly n × 3u/2l – slightly more because this ignores the + 1 u times. The divisor 2l is only to get rid of the tail we dutifully appended. If we skip that part, we just have p × 3u where p is the unshifted prefix.
Prediction
More precisely, the number part left of the triangle (in the examples) kind of has its own Collatz evolution, albeit with two major differences for the 1st l steps: whether it gets halved down, or multiplied up, depends not on its low bit left of the divide but still on the overall low bit. And if it gets multiplied, 1 only gets added when there's a carry bit out of the triangle. This being identical, given any tail, for all numbers prepended to it, the evolution to the left is precisely predictable:
We can remember (or recalculate) the result r0 after l steps for the tail with a prefix of 0 as well as r1 for a prefix of 1. Then for any prefix p the result will be rp = r0 + p × (r1 - r0). To demonstrate, for the above tails, I show metadata for both ways: give various prefixes, the result of putting them before the tail, the approximate result from the previous section, the precise prediction from this paragraph, and by how much the approximation was off. I.e. a starting number in the 2nd column reaches the 4th column's after l steps:
pl -o4 '($_, $u, $r0, $r1) = @$_; $l = length; $f = 3 ** $u / 2 ** $l;
$t = eval "0b$_"; $d = $r1 - $r0;
form "tail: ...$_ u:l-factor: %.3f r1-r0: %d", $f, $d;
form "%13b... = %10d %16.3f %12d %5.3f", $_, $n = ($_ << $l) | $t, $a = $n * $f, $b = $r0 + $_ * $d, $b - $a
for 2, 3, 31, 1023, 1024, 4711 ' \
0011 2 2 11 \
01011 3 10 37 \
10111 3 20 47 \
1111100111 6 712 1441 \
000000001111111111 11 692 177839pl -o4 '($_, $u, $r0, $r1) = @$_; $l = length; $f = 3 ** $u / 2 ** $l;
$t = eval "0b$_"; $d = $r1 - $r0;
f "tail: ...$_ u:l-factor: %.3f r1-r0: %d", $f, $d;
f "%13b... = %10d %16.3f %12d %5.3f", $_, $n = ($_ << $l) | $t, $a = $n * $f, $b = $r0 + $_ * $d, $b - $a
for 2, 3, 31, 1023, 1024, 4711 ' \
0011 2 2 11 \
01011 3 10 37 \
10111 3 20 47 \
1111100111 6 712 1441 \
000000001111111111 11 692 177839tail: ...0011 u:l-factor: 0.562 r1-r0: 9
10... = 35 19.688 20 0.312
11... = 51 28.688 29 0.312
11111... = 499 280.688 281 0.312
1111111111... = 16371 9208.688 9209 0.312
10000000000... = 16387 9217.688 9218 0.312
1001001100111... = 75379 42400.688 42401 0.312
tail: ...01011 u:l-factor: 0.844 r1-r0: 27
10... = 75 63.281 64 0.719
11... = 107 90.281 91 0.719
11111... = 1003 846.281 847 0.719
1111111111... = 32747 27630.281 27631 0.719
10000000000... = 32779 27657.281 27658 0.719
1001001100111... = 150763 127206.281 127207 0.719
tail: ...10111 u:l-factor: 0.844 r1-r0: 27
10... = 87 73.406 74 0.594
11... = 119 100.406 101 0.594
11111... = 1015 856.406 857 0.594
1111111111... = 32759 27640.406 27641 0.594
10000000000... = 32791 27667.406 27668 0.594
1001001100111... = 150775 127216.406 127217 0.594
tail: ...1111100111 u:l-factor: 0.712 r1-r0: 729
10... = 3047 2169.202 2170 0.798
11... = 4071 2898.202 2899 0.798
11111... = 32743 23310.202 23311 0.798
1111111111... = 1048551 746478.202 746479 0.798
10000000000... = 1049575 747207.202 747208 0.798
1001001100111... = 4825063 3435030.202 3435031 0.798
tail: ...000000001111111111 u:l-factor: 0.676 r1-r0: 177147
10... = 525311 354985.305 354986 0.695
11... = 787455 532132.305 532133 0.695
11111... = 8127487 5492248.305 5492249 0.695
1111111111... = 268174335 181222072.305 181222073 0.695
10000000000... = 268436479 181399219.305 181399220 0.695
1001001100111... = 1234961407 834540208.305 834540209 0.695This gives a great optimisation for testing many numbers: we only need to remember a Bad tail's r0 and calculate the same prefixed with a 1-bit, giving us r1. Feeding these into the above formula, we get rp for any prefix we prepend. That way we can leapfrog over l steps of Collatz and start right at the unknown part. E.g., we could prepend 8 bits at once, giving us quick access to up to 256 new longer Bad tails for longer numbers (or less as we find Good tails in between, which would short circuit some of those 256).
Say we have a 69 bit Bad tail. Assuming all extensions by 8 bits are Bad, testing naively we would have 256 × (69+8) steps of Collatz to find those derived Bad tails. With this optimisation there are only 69 steps + 256 × (1 multiplication + 1 addition + 8 steps). This counts only my quest for ever longer Bad tails. If you want to test them exhaustively, in this way you can fairly cheaply extend to a great number of bits. Only from there on you'd finally have, sometimes many, more steps, to see if they actually stop.
I have written a Collatz Bad tails script cbt. It's seeded with the 19 8-bit Bad tails and their respective r0. From that it will calculate the same for 16 bits. This output can be compressed and fed back to the script, giving the 24 bits' data, and so on. I have taken this to also 40 bits, which even on an old laptop takes 2 hours, compared to 2 weeks for a full loop. These files can be split and fed in parallel on many computers. However, compressing with brotli -Z takes maybe 100x as long as the actual calculation. A slightly less compact xz -9e, which I used, still takes 10x as long. My SAN had problems with writing the 48 bits results, so I didn't do it. And I only hinted at how to convert the script to BigInt.
Side note: A more compact binary representation, with length encoding rather than fixed sizes, could be made less than half the size of my hex-encoding. And since there are rather few different endings to Bad tails, their low bits could be encoded instead of repeated over and over again. That could remain uncompressed or only lightly compressed to win a lot of time vs. 30% additional disk space as a compromise. Instead of writing out a bigger file every 8 bits, we could repeatedly recurse internally and do the same thing over for another 8 bits. For bigger l, we should also calculate the optimal number of bits to lengthen by, to balance with how many steps it takes to find r1.
I conclude that 6 is less than 5! I now get factorials. 😂
ConclusionGiven my findings, testing a bit deeper to 69 or more bits isn't even interesting. The true frontier is understanding what happens in depth as the Bad tails branch out. And I have proven that at least half of the branches at each level will fan out infinitely and shown how that relates to the appearing Good tails.
Is the notion of a number with an infinite amount of such and such digits mathematically sound?*) If so, any Bad tail, which always leads to one or two longer Bad tails, gives us a subtree with both infinitely many ever longer Good tails and even more infinite counter-examples to the Collatz conjecture. The latter would disprove Collatz – entschuldige bitte, mein Lieber!
On the other hand the correct mathematical notion might be a weaker statement: there's an infinite amount of individually finite numbers. If so, proof by full induction through my method alone isn't possible. Each of those ending in a Bad tail may or may not stop.
However then I have shown a way of efficiently whittling down the amount of numbers worth studying and testing to a relatively decreasing (inversely to increasing l) though huge subset with a big prediction-based optimisation. And I have shown that there can be no upper bound to sequence length, since I can make any Bad tail infinitely longer.
Iceberg's last words: "Ouch — the Titanic!" 😵💫
Caveat LectorCollatz specialist Eric
Daniel