Collatz Streetmap

Introduction

Collatz sequences are sequences of non-negative integer numbers with a simple construction rule: even elements a halved, and odd elements are multiplied by 3 and then incremented by 1. Since many years it is unknown whether the final cyle 4 - 2 - 1 is always for any start value. This problem is the Collatz conjecture., for which the english Wikipedia states: It is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani's problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse's algorithm (after Helmut Hasse), or the Syracuse problem; the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers (because the values are usually subject to multiple descents and ascents like hailstones in a cloud), or as wondrous numbers.

Whenever we speak of numbers in this article, we mean natural, positive integer numbers (without 0).

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

Collatz graph

When all Collatz sequences are read backwards, they form the Collatz graph starting with 1, 2, 4, 8 ... . At each node n > 4 in the graph, the path from the root (4) can be continued

• always to n * 2, and
• sometimes also to (n - 1) / 3.

When n ≡ 0 mod 3, the path will continue with duplications only, since these maintain the divisibility by 3.

The conjecture claims that the graphs contains all numbers, and that - except for the leading cycle 1 - 2 - 4 - 1 - 2 - 4 ... - it has the form of a tree without cylces.

Straightforward visualizations of the Collatz graph show now obvious structure. The sequences for the first dozen of start values seem to be rather harmless, but the sequence for 27 suddenly has 112 elements.

This article proposes

• a rather regular structure for short portions of the Collatz graph, and
• a corresponding algorithm which
  • combines these portions and
  • uses them to walk the graph in a systematic, predictable way
• such that the reader could finally be convinced that the algorithm enumerates all numbers.

Steps

In order to walk back and forth in the Collatz graph, we need to describe how to move from one node in the graph to another. We will write

a s b

when use step s to move from node (element) a in the Collatz graph/sequence to node b. The following table lists the steps which we will use:

Name	Mnemonic	Direction	Operation	Condition	Remark
h	halve	-> root	b = a / 2	a ≡ 0 mod 2	next in sequence
t	triple	-> root	b = 3 * a + 1	true	next in sequence
m	multiply	root ->	b = a * 2	true	next up in tree
d	divide	root ->	b = (a - 1) / 3	a ≡ 1 mod 3	next up in tree

Collatz roads

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, for example (from OEIS A070165):

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

The third line shows the relation between the values in the first two lines.

Informally, a road is a parallel arrangement of 2 pathes stemming from 2 sequences which have a common tail. In the example above, the road starts with an element ≡ 4 mod 6 (the 364 before the bar), followed by t/h and h/h steps, and the road then extends to the left as long as a characteristical, alternating sequence of pairs of steps ht - th - ht - th ... can be continued. In the example, the road can be continued to the left with 4 additional steps, but the construction then stops since there is no number q such that q * 3 + 1 = 62:

  q t | 62 h  31 t  94 h  47 t 142 h ...
126 h | 63 t 190 h  95 t 286 h 143 t ...
        +1  *6+4    +1  *6+4    +1  

Roads table R

For easier handling (e.g. in Excel) we list the roads for all starting values 4, 10, 16, 22 ... n*6+4 as rows of a table, in reversed direction (extending to the right). The columns of the rows are numbered r₀, r₁, r₂ ...

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

The roads contain 2 parallel, short, interrelated paths in the Collatz graph. Though the graph usually has a "chaotic" appearance, the roads exhibit quite some amount of regular structure.

There is a more elaborated example for elements <= 143248.

When this file is displayed in a browser, the zoom factor may be reduced (with Ctrl "-", to 25 % for example) such that the structure of the lengths of roads can be seen.

Road lengths

• The lengths r₁ 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 n_i have high values 5, 9, 13, 17, 21 which did not occur before. Those starting values are (9ⁿ⁺¹ - 1) / 2, or 4 * Sum(9ⁱ, 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 r₂. 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 r₀ and r₅ 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:

• s₂ is always s₀ * 4 - 1.
• When s₂ ≡ 0 mod 3, the following columns s₃, s₄ ... are obtained by an alternating sequence of steps
  • s_i+1 = s_i / 3 and
  • s_i+2 = s_i+1 * 2,
  • until all factors 3 in s₂ 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 s₄ ... s₇ contain all numbers ≡ 2,4,6,10,12,14 mod 16, but those ≡ 0,8 mod 16 are missing so far. The ones ≡ 8 mod 16 show up in s₈ resp. s₉, half of the multiples of 16 are in s₁₀ resp. s₁₁ but ≡ 0,32 mod 64 are missing, etc.

Since s₂ contains arbitray high powers of 3, S has rows of arbitrary length, and for the missing multiples of powers of 2 the exponents can be driven above all limits.

Thus S contains all positive integers.

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 s₀ = 13 rather quickly, but the first 27 completely filled rows involve start numbers s₀ up to 1539, and for the first 4831 rows, start values up to 4076811 are involved.