Collatz Streetmap
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
- Jeffry C. Lagarias, Ed.: The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010, ISBN 978-8218-4940-8. MBK78
- OEIS A07165: File of first 10K Collatz sequences, ascending start values, with lengths
- Gottfried Helms: The Collatz-Problem. A view into some 3x+1-trees and a new fractal graphic representation. Univ. Kassel.
- Klaus Brennecke: Collatzfolgen und Schachbrett, on Wikibooks
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).
For better handling (e.g. in Excel), the roads for all starting values 4, 10, 16, 22 ... 4+6*n are listed as rows in an array. The cells 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 | ... | ||||
4 | 5 | 1 | 8 | 2 | 16 | 4 | 5 | 1 | 10 | 2 | 3 | ||||||||
10 | 3 | 3 | 20 | 6 | 40 | 12 | 13 | ||||||||||||
16 | 3 | 5 | 32 | 10 | 64 | 20 | 21 | ||||||||||||
22 | 4 | 7 | 44 | 14 | 88 | 28 | 29 | 9 | 58 | ||||||||||
28 | 3 | 9 | 56 | 18 | 112 | 36 | 37 | ||||||||||||
34 | 3 | 11 | 68 | 22 | 136 | 44 | 45 | ||||||||||||
40 | 9 | 13 | 80 | 26 | 160 | 52 | 53 | 17 | 106 | 34 | 35 | 11 | 70 | 22 | 23 | 7 | 46 | 14 | 15 |
46 | 3 | 15 | 92 | 30 | 184 | 60 | 61 | ||||||||||||
52 | 3 | 17 | 104 | 34 | 208 | 68 | 69 | ||||||||||||
58 | 5 | 19 | 116 | 38 | 232 | 76 | 77 | 25 | 154 | 50 | 51 | ||||||||
64 | 3 | 21 | 128 | 42 | 256 | 84 | 85 | ||||||||||||
70 | 3 | 23 | 140 | 46 | 280 | 92 | 93 | ||||||||||||
76 | 4 | 25 | 152 | 50 | 304 | 100 | 101 | 33 | 202 |
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 pathes 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 length
- The lengths r1 of the roads seem to be finite. The emphasized 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 formula.
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 array "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 are obtained by 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
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 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 ...
The building rule is simple: s2 is always s0 * 4 - 1. When s2 ≡ 0 mod 3, the following columns s3, s4 ... are obtained by /3, *2 steps in alternating sequence, until all factors of 3 have been replaced by a factor 2, so the expansion always terminates.
- Question S1: Does this table contain all positive integers?
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 |
s4 ... s7 | ≡ 2,4,6, 10,12,14 mod 16 |
The numbers divisible by 8 are missing so far.