Collatz Streetmap

From tehowiki
Revision as of 19:31, 26 August 2018 by imported>Gfis (completeness of S)
Jump to navigation Jump to search

Introduction

When all Collatz sequences are read backwards, they form a graph starting with 1, 2 ..., hopefully without cycles (except for 1,2,4,1,2,4 ...). At each node n in the graph, the path starting at the root (4) and with the last node n can in principle be continued to 2 new nodes by a

  • "m"-step: n * 2 (which is always possible), or a
  • "d"-step: (n - 1) / 3 (which is possible only if n ≡ 1 mod 3).

When n mod 3 = 0, the path will continue with m-steps only, since the duplication maintains the divisibility by 3.

References

Motivation: Patterns in sequences with same length

When Collatz sequences are investigated, there are a lot of pairs of adjacent start values with the same sequence length, and with a characteristical neighbourhood of every other value, for example (from OEIS A070165):

142/104: [142 m  71 d 214 m 107 d 322 m 161 d 484 m  242 m 121 d | 364, 182, 91, ... 10, 5, 16, 8, 4, 2, 1]
           +1  *6+4    +1  *6+4    +1  *6+4    +1   *6+4  *6+2      =    =  ...
143/104: [143 d 430 m 215 d 646 m 323 d 970 m 485 d 1456 m 728 m | 364, 182, 91, ... 10, 5, 16, 8, 4, 2, 1]

Collatz roads

We define a "road" (with 2 parallel "lanes") as a sequence of pairs of elements (in 2 Collatz sequences with adjacent start values, read from right to left). A road is constructed by taking some n (364 in the example, the last common element of the 2 sequences) with n ≡ 4 mod 6, and by applying the steps

d m m d m d m d ... 
m m d m d m d m ...

in alternating sequence, until one of the elements in the pairs becomes divisible by 3. The construction yields one road with an upper lane (left elements of the pairs) and a lower lane (right elements), for example:

364: (121,728), (242,1456), (484,485), (161,970), (322,323), (107,646), (214,215), (71,430), (142,143) ...

The elements which are ≡ 4 mod 6 are emphasized. The construction continues until 63 ≡ 0 mod 3:

... (47,286), (94,95), (31,190), (62,63).

Roads table R

For better handling (e.g. in Excel), the roads for all starting values 4, 10, 16, 22 ... n*6+4 are listed as rows of a table. The columns in the rows are numbered r0, r1, r2 ...

r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 ...
start len dr0 mr0 mr2 mr3 mr4 dr5 dr6 mr7 mr8 dr9 dr10 mr11 mr12 dr13 ...
Δ6 Δ2 Δ12 Δ4 Δ24 Δ8 Δ8 3Δ8 3Δ48 3Δ16 3Δ16 9Δ16 9Δ96 9Δ32 9Δ32 ...
45182164511023
1033206401213
16353210642021
22474414882829958
283956181123637
3431168221364445
4091380261605253171063435117022237461415
4631592301846061
52317104342086869
58519116382327677251545051
64321128422568485
70323140462809293
764251525030410010133202

There is a more elaborated example for elements <= 143248. The zoom factor of the web browser may be reduced (with Ctrl "-", to 25 % for example) such that the structure of the lengths of roads can be seen.

Relation to the Collatz graph

The Collatz graph is the union of all possible Collatz sequences, read backwards. Apart from the initial cycle 1-2-4-1 it should be a tree, and it should contain all positive numbers.

Each road contains 2 short paths in the Collatz graph, the root is left of the starting value of the road, and both proceed "upwards" in the tree. In contrast to the usual "chaotic" appearance of the Collatz graph, there is an amount of obvious structure in the road construction.

Road lengths

  • The lengths r1 of the roads seem to be finite. The highlighted pairs of numbers ≡ 4 mod 6 are decreasing to the end of the road.
  • The lengths show a repeating pattern for the start values mod 54. The fixed lengths 3, 4, 5 can probably be explained from the road construction rule.
4 mod 54 10 mod 54 16 mod 54 22 mod 54 28 mod 54 34 mod 54 40 mod 54 46 mod 54 52 mod 54
5 3 3 4 3 3 n 3 3
  • At the starting values 4, 40, 364, 3280, 29524 (OEIS A191681) the road lengths ni have high values 5, 9, 13, 17, 21 which did not occur before. Those starting values are (9n+1 - 1) / 2, or 4 * Sum(9i, i=0..n).
  • The pattern of increasing and decreasing lengths is replicated when subsets of the rows (mod 9, 27, 81 ...) are regarded.

Coverage

The elements of the roads are strongly interconnected, and the table "obviously" shows all positive integers which are not multiples of 24:

r0 ≡ 4 mod 6 ≡ 4,10,16,22 mod 24
r3 ≡ 8 mod 12 ≡ 8,20 mod 24
r4 ≡ 2 mod 4 ≡ 2,6,10,14,18,22 mod 24
r5 ≡ 16 mod 24 ≡ 16 mod 24
r6 ≡ 4 mod 8 ≡ 4,12,20 mod 24
r2 ≡ 1 mod 2 all odd numbers

All odd multiples of 3 are contained in column r2. All multiples of 24 can be reached by duplicating them 3 times (3 m-steps).

So if we can show that we reach all start values ≡ 4 mod 6, we have a proof that all positive integers are reached.

Starting with 4, it seems possible that a continuous expansion of all numbers ≡ 4 mod 6 into roads would finally yield all roads up to some start value. Experiments show that there are limits for the numbers involved. Roads above the clamp value are not necessary in order to obtain all roads below and including the start value:

start value clamp value
4 4
40 76
364 2308
3280 143248

Subset table S

We may build derived table from the table of roads. We take columns r0 and r5 ff., and therein we keep the highlighted entries (those which are ≡ 4 mod 6) only, add 2 to them and divide them by 6. The resulting subset table S starts as follows:

s0  s1   s2   s3   s4   s5   s6   s7   s8   ...
 n  len  
 1   3    3    1    2
 2   1    7
 3   1   11
 4   3   15    5   10
 5   1   19
 6   1   23
 7   7   27    9   18    6   12    4    8
 8   1   31
 9   1   35
10   3   39   13   26
11   1   43
12   1   47
13   3   51   17   34
14   1   55
15   1   59
16   5   63   21   42   14   28
...

This table can be described by simple rules which are hopefully provable from the construction rule for the roads:

  • s2 is always s0 * 4 - 1.
  • When s2 ≡ 0 mod 3, the following columns s3, s4 ... are obtained by an alternating sequence of steps
    • si+1 = si / 3 and
    • si+2 = si+1 * 2,
    • until all factors 3 in s2 are replaced by factors 2.

Does S contain all positive integers?

The answer is yes. As above, we can regard the increments in successive columns:

ss ≡ 3 mod 4 half of the odd numbers
s3 ≡ 1 mod 4 other half of odd numbers
s4 ≡ 2 mod 8 ≡ 2,10 mod 16
s5 ≡ 6 mod 8 ≡ 6,14 mod 16
s6 ≡ 12 mod 16 ≡ 12 mod 16
s7 ≡ 4 mod 16 ≡ 4 mod 16
s8 ≡ 8 mod 32 8, 40, 72, ...
s9 ≡ 24 mod 32 24, 56, 88, ...
s10 ≡ 48 mod 64 48, 112, 176, 240 ...
s11 ≡ 16 mod 64 16, 80, ...

This shows that the columns s4 ... s7 contain all numbers ≡ 2,4,6,10,12,14 mod 16, but that &#x2261 0,8 mod 16 are missing so far. The ones &#x2261 8 mod 16 show up in s8 resp. s9, but multiples of 16 would be missing then, etc.

Can S be generated starting at 1?

We ask for an iterative process which starts with the row of S for index 1:

 1:    3    1    2

Then, all additional rows for the elements obtained so far are generated:

 2:    7
 3:   11

These rows are also expanded:

 7:   27    9   18    6   12    4    8
11:   43

Since we want to cover all indexes, we would first generate the rows for lower indexes. This process fills all rows up to s0 = 13 rather quickly, but the first 27 completely filled rows involve start numbers s0 up to 1539, and for the first 4831 rows, start values up to 4076811 are involved.