OEIS/3x+1 Problem

Abstract

The graph defined by Collatz for his 3x + 1 problem is overlaid with a set of small, finite trees with two branches. It is shown that this set of trees not only contains all numbers, but that it defines a permutation of the numbers. Furthermore, rules are defined how some subsets of these trees can be attached to other subsets. It is shown that no cycles can arise, and that finally the process leads to only one set of interconnected subtrees. Therefore, the Collatz graph is a tree which contains all numbers.

Introduction

Collatz sequences (also called trajectories) are sequences of integer numbers > 0. For some start value > 0 the elements of a particular sequence are constructed with two simple rules:

1. Even numbers are halved.
2. Odd numbers are multiplied by 3 and then incremented by 1.

Since decades it is unknown whether the final cyle 4 - 2 - 1 is always reached for all start values. 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.

Simple visualizations of Collatz sequences do not show any obvious structure. The sequences for the first dozen of start values are rather short, but the sequence for 27 suddenly has 112 elements.

Da sieht man den Wald vor lauter Bämen nicht.
German proverb: You cannot see the wood for the trees.

References

• Jeffry C. Lagarias, Ed.: The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010, ISBN 978-8218-4940-8. MBK78
• OEIS A070165: File of first 10K Collatz sequences, ascending start values, with lengths
• Manfred Trümper: The Collatz Problem in the Light of an Infinite Free Semigroup. Chinese Journal of Mathematics, Vol. 2014, Article ID 756917, 21 p.

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
• to (n - 1) / 3 if n ≡ 1 mod 3.

The Collatz conjecture claims that the Collatz graph

• contains all numbers,

and that it - except for the leading cycle 1 - 2 - 4 - 1 - 2 - 4 ... -

• has the form of a tree (without cycles).

We will not consider the leading cycle, and we start the graph with node 4, the root. Furthermore we observe that a path can only be continued with duplications once it reaches a node n ≡ 0 mod 3. We omit these trivial continuations.

Graph Operations

Following Trümper, we use abbreviations for the elementary operations which map a node (element, number) n in the Collatz graph to the neighbouring node as shown in the following table (T1):

Name	Mnemonic	Distance to root	Mapping	Condition
d	"down"	-1	n ↦ n / 2	n ≡ 0 mod 2
u	"up"	-1	n ↦ 3 * n + 1	(none)
s := ud	"spike"	-2	n ↦ (3 * n + 1) / 2)	n ≡ 1 mod 2
δ	"divide"	+1	n ↦ (n - 1) / 3	n ≡ 1 mod 3
µ	"multiply"	+1	n ↦ n * 2	(none)
σ := δµ	"squeeze"	+2	n ↦ ((n - 1) / 3) * 2	n ≡ 1 mod 3

The operations will be noted as infix operators, with the source node as left operand and the target node as right operand, for example 10 δµ 6. In the following, we will mainly be interested in the reverse mappings (denoted by greek letters) which move away from the root 4 of the graph.

Motivation: Patterns in sequences with the same length

A closer look at the Collatz sequences shows a lot of pairs of adjacent start values which have the same sequence length, for example (from OEIS A070165):

143/104: 143 u 430 d 215 u 646 d 323 u 970 d 485 u 1456 d 728 d 364 ] d 182 ... 4 d 2 d 1
142/104: 142 d  71 u 214 d 107 u 322 d 161 u 484 d  242 d 121 u 364 ] d 182 ... 4 d 2 d 1

Beginning at some node of the form 6*i - 2 (364 in the example), these sequences join and follow the same path down to the root 4. The two differing parts of the sequences show a regular pattern, where nodes of the form 6*i - 2 alternate with other nodes, and where the operations u and d also alternate. This pattern of operations can be continued to the left with additional d and u operations:

126 d [ 63 u 190 d  95 u 286 d 143 u ...
 n? u [ 62 d  31 u  94 d  47 u 142 d ...

Finally the pattern stops because there is no integer n such that n * 3 + 1 = 62.

Example (E1) shows the sequences above, read from right to left, with the inverse operations:

[ 364 µ 728 µ 1456 δ 485 µ 970 δ 323 µ 646 δ 215 µ 430 δ 143 µ 286 δ  95 µ 190 δ 63 ]
[ 364 δ 121 µ  242 µ 484 δ 161 µ 322 δ 107 µ 214 δ  71 µ 142 δ  47 µ  94 δ  31 µ 62 ]

Segments

These patterns lead us to the construction of special subtrees in the Collatz graph which we call segments. Starting at some node of the form 6*i - 2 (the left side, LS), two subpaths (the upper branch and the lower branch) continue to the right by a prescribed sequence of operations. The two branches form the right part (RP) of the segment.

The nodes of the form 6*i - 2 play a special role because both a δ and a µ operation can be applied to them. We could also have used 6*i + 4 instead, but the formulas seem easier with 6*i - 2, therefore we always use this form. Later we will consider nodes where 6*i - 2 is transformed to j, where j also may have the form j = 6*k - 2, etc.

Informally, a segment is constructed as follows:

• Step 1: Start with some node 6*i - 2 as the left side (LS).
• Step 2: Apply δ to the LS to get the first node in the lower branch.
• Step 3: Apply µ to the LS to get the first node in the upper branch.
• Steps 4, 5: Apply µ to both branches.
• In a loop, apply opposite operations to both branches, starting with µ (step 6) on the lower and δ (step 7) on the upper branch, continuing with δ (step 8) on the lower and µ (step 9) on the upper branch, and so on, as long as the next δ operation is possible.

The construction is such that increasing instances of σ operations are accumulated in each branch.

Segment directory

The resulting set of small trees is listed in a so-called segment directory (the link shows several thousand subtrees arranged by increasing left side, together with some additional information).

The segment directory shows the segments in rows of a table. The steps are mapped to columns of the table. In order to maintain the subtree structure with two branches, each row contains a pair of columns numbered 3, 5, 7, ... for the upper branch and 2, 4, 6, ... for the lower branch.

Nodes in the right part of a segment which have the form 6*i - 2 are shown in bold face. If i also has the form 6*k - 2, the node has a yellow background.

Details of a segment

The following table (T1) shows various properties of the steps reps. columns in the segment construction:

Column j	Branch	Operation	Form of i	Formula	First elements	Covered nodes	Remaining nodes
1	(LS)			6*i - 2	4, 10, 16, 22		1, 2, 4, 5 mod 6
2	lower	δ		2*i - 1	1, 3, 5, 7	1, 3, 5 mod 6	2, 4 mod 6
3	upper	µ		12*i - 4	8, 20, 32, 44	8 mod 12	2, 4, 10 mod 12
4	lower	σ		12*(i - 1)/1 + 2	2, 14, 16, 38	2 mod 12	4, 10 mod 12
5	upper	µ2		24*(i - 1)/1 + 16	16, 40, 64, 88	16 mod 24	4, 10, 22 mod 24
6	lower	σµ	i = 3*k + 1	24*(i - 1)/3 + 4	4, 28, 52, 76	4 mod 24	10, 22, 34, 46 mod 48
7	upper	µ2δ	i = 3*k + 1	24*(i - 1)/3 + 5	5, 29, 53, 77	(cf. column 2)
8	lower	σµδ	i = 3*k + 1	24*(i - 1)/3 + 17	17, 41, 65, 89	(cf. column 2)
9	upper	µ2σ	i = 3*k + 1	48*(i - 1)/3 + 10	10, 58, 106, 154	10 mod 48	22, 34, 46 mod 48
10	lower	σµσ	i = 9*k + 7	48*(i - 7)/9 + 34	34, 82, 130, 178	34 mod 48	22, 46, 70, 94 mod 96
11	upper	µ2σδ	i = 9*k + 7	48*(i - 7)/9 + 35	35, 83, 131, 179	(cf. column 2)
12	lower	σµσδ	i = 9*k + 7	48*(i - 7)/9 + 11	11, 27, 43, 59	(cf. column 2)
13	upper	µ2σ2	i = 9*k + 7	96*(i - 7)/9 + 70	70, 166, 262, 358	70 mod 96	22, 46, 94 mod 96
14	lower	σµσ2	i = 27*k + 7	96*(i - 7)/27 + 22	22, 118, 214, 310	22 mod 96	46, 94, 142, 190 mod 192
15	upper	µ2σ2δ	i = 27*k + 7	96*(i - 7)/27 + 23	23, 119, 215, 311	(cf. column 2)
16	lower	σµσ2δ	i = 27*k + 7	96*(i - 7)/27 + 71	71, 167, 263, 359	(cf. column 2)
17	upper	µ2σ3	i = 27*k + 7	192*(i - 7)/27 + 46	46, 238, 430, 622	46 mod 96	94, 142, 190 mod 192
18	lower	σµσ3	i = 81*k + 61	192*(i - 61)/81 + 142	142, 334, 526, 718	142 mod 96	94, 190, 286, 382 mod 384
19	upper	µ2σ3δ	i = 81*k + 61	192*(i - 61)/81 + 143	143, 225, 527, 719	(cf. column 2)
j			i = m*k + n	p*(i - n)/m + q

The general formula (in the last row of T1) for a column j >= 5 uses the following parameters:

• m = 3^(floor((j - 2) / 4)
• n is an element of the OEIS sequence (A066443: a(0) = 1; a(n) = 9 * a(n-1) - 2 for n > 0 . The values are the indexes 1, 7, 61, 547, 4921 ... of the variable length segments with left sides 4, 40, 364, 3280, 29524 (OEIS A191681).
• p = 3*2^floor((j + 7) / 4)
• q is the first term appearing in the corresponding column, as resulting from the application of the δ and µ operations

First we have to show that the segment construction process always stops.

σ replaces 3 by 2

For this purpose, we observe that the σ operation, when applied to left sides of the form 6*(3*k) - 2 has the interesting property that it maintains the general form 6*i - 2:

6*(3*k) - 2 σ (2*(3*k) - 1) * 2 = 12*k - 2 = 6*(2*k) - 2

That means that σ replaces one factor 3 by a factor 2 (it "squeezes" a 3 into a 2). In the opposite direction, the s ("spike") operation replaces one factor 2 by a factor 3.

The branch prolongation in the segment construction process must stop when the successive σ operations have exhausted all factors of 3 in the left side. Therefore, all segments have a finite length.

---

Segment Directory Construction

For a convenient presentation of various properties of the segments, we linearize the notation for the subtrees by interleaving the two branches. Example (E2) then becomes:

364 1456 484 970 322 646 214 430 142 286 94 190

For the possible left sides of the form 6i - 2, i > 0 we list the linearized form of the segments as rows of an array C[i, j] which we call the segment directory. The rows are indexed (numbered) by i. They have a varying number of columns j > 0. The columns with even numbers correspond to the nodes in the upper branch, while the odd columns j >= 3 correspond to the nodes in the lower branch. The following example (E3) shows the first few rows of the segment directory, together with the segment with index i = 61 for left side 364 from example (E2) above:

1	4	16	4	10
2	10	40
3	16	64
4	22	88	28	58
5	28	112
6	34	136
7	40	160	52	106	34	70	22	46
...
61	364	1456	484	970	322	646	214	430	142	286	94	190
...

There is a more elaborated segment directory with several thousand rows.

Properties of the Segment Directory

As for the segments, we denote the set of nodes in C[i, 1] as the left side of C, and the set of nodes in C[i, j], j >= 2 as the right part of the segment directory. We make a number of observations and claims for the segment directory C:

• (C1) All nodes in the segment directory have the form 6n - 2.

This follows from the construction by table (T1).

• (C4) All nodes in the right part of a particular segment are
  • different among themselves, and
  • different from the left side of that segment (except for the first segment for the root 4).

For C[i, 1..2] we see that the values modulo 24 are different. For the remaining columns, we see that the exponents of the factors 2 and 3 are different. They are shifted by the σ operations, but they alternate, for example (in the segment with left part 40):

160 = 6 * (33 * 20 * 1) - 2
 52 = 6 * (32 * 20 * 1) - 2
106 = 6 * (32 * 21 * 1) - 2
 34 = 6 * (31 * 21 * 1) - 2
 70 = 6 * (31 * 22 * 1) - 2
 22 = 6 * (30 * 22 * 1) - 2
 46 = 6 * (30 * 23 * 1) - 2

• (C5) There is no cycle in a segment (except for the first segment for the root 4).
• (C??) There is no limit on the length of a segment.

We only need to take a segment which, in its right part, has a factor of 3 with a sufficiently high power, and the σ operations will stretch out the segment accordingly.

Coverage

Coverage of Non-left sides

We now show that

• (C??) All numbers n > 0 are either left sides (≡ 4 mod 6), or there is a unique path from a left side to n.

Table (T5) shows the residues modulo 6 for some left side (source) node n = 6i - 2:

Source	Operation	Target	Reached Nodes	Remaining Nodes
6i - 2	(none)	6i - 2	4 mod 6	0, 1, 2, 3, 5 mod 6
6i - 2	δ	2i - 1	1, 3, 5 mod 6	0, 2, 6, 8 mod 12
6(3k + 1) - 2	δµ	12k + 2	2 mod 12	0, 6, 8 mod 12
6i - 2	µ	12i - 4	8 mod 12	0 mod 6

The second row reaches all odd multiples of 3. All even multiples of 3 can be reached from there by one or more µ operation.

• (C??) There is only one subpath from some left side to a specific non-left side.

Coverage of left sides

We want to show:

• (C??) Any left side of the form 6n - 2 occurs exactly
  • once in the left side and
  • once in the right part of the segment directory.
  • There is a bijective mapping between the left sides and the elements of the right parts.

The nodes in the left side are different by the construction of the segment directory. The following table (T3) shows the uniqueness in the columns of the right part. The sequence in one specific column has a particular modulus condition which is different from the ones in all other columns. Therefore the columns all contain disjoint sets of numbers:

Column j	Operation	Expression	Covered	Remaining
1		n = 6i - 2	(none)	4, 10, 16, 22 mod 24
2	µµ	24i - 8	16 mod 24	4, 10, 22 mod 24
3	δµµ	8i - 4, i = 3k + 1	4 mod 24	10, 22, 34, 46 mod 48
4	µµσ1		10 mod 48	22, 34, 46 mod 48
5	δµµσ1		34 mod 48	22, 46, 70, 94 mod 96
6	µµσ2		70 mod 96	22, 46, 94 mod 96
7	δµµσ2		22 mod 96	46, 94, 142, 190 mod 192
8	µµσ3		46 mod 96	94, 142, 190 mod 192
9	δµµσ3		142 mod 192	94, 190, 286, 382 mod 384
10	µµσ4		94??? mod 192	190, 286, 382 mod 384
11	δµµσ4		190 mod 192	286, 382, 670, 766 mod 768
...	...	...	...	...

We can always exclude one of the elements remaining so far by looking in the next column of segments with sufficient length.

• (S??) All source segments are either
  • contracting, or
  • k is even and the target segment is contracting, or
  • k is odd and the target segment has degree 2 and left side ≡ 94 mod 108.

From the attachment table (T4) we see:

• Segments with odd index i ≡ 1,3,5,7 mod 8 follow rule 5 or 6 and are contracting.

Only rules 5, 6 can have odd i.

• i ≡ 2 mod 8 follow rule 9 and are contracting.

Directly from (T4)

k even ->  target row odd -> rule 5/6
6 mod 8 follows rule 10. Split it in:
6 mod 16  (k = 2m, even)    : target row 18m+7 (odd) follows rule 5/6. 
14 mod 16 (k = 2m + 1, odd) : target row 18m+16 = 6(3m + 3) - 2 super.
Rule 14: 2^2(4k+1) |-> 3^3*k+7 = 54m + 34 = 6(9m + 6) - 2 super
Rule 18: |-> 3^4*k + 61 = 162m + 81 + 61 = 6(27m + 24) - 2 super
(A066443 = 1,7,61 ...) = 9 * odd - 2
3^m*k + 9 * odd - 2 -> 18n - 2  -> 16 mod 18 or 94 mod 108 (
t16_18 = degree2 landing segments 94, 202, 310 ... (16, 34, 52, 70 ...)
3^m*k with at least a factor 9 starts in rule 10 for odd k

Degree 2

• (D1) At most one supernode can occur in the right part of a segment, and if so, it is the last or the last-but-one entry.

We cannot continue a supernode 6(6i - 2) - 2 with a δµ operation:

(6(6i - 2) - 2 - 1) / 3 * 2 = 4(6i - 2) - 2 = 24i - 10 &#x2261 2 mod 6

The result is no node of the form 6i - 2.

• All supernodes with odd i follow rules 5 or 6.
• All other source rows either are a supernode, follow a rule 5 or 6, or their target is a supernode.
• If the target is a supernode, then k is odd???
• Index 7 mod 18 has degree 2,3 only in last of right part, column >= 10 for degree2, column = 10 for degree 3, rule 5/6
• Index 13 mod 18 has degree >= 2 only in last of right part, column 9; 49 mod 54 has degree >= 3; 49 mod 162 has degree = 4

t7_13_18: right part only, follows rule 5/6
t10_18: left side only
prove these "only", and "both" = lhs + last only

Degree 3

i ≡ 22 mod 36 for lhs with degree 3
if i ≡ 58 mod 72 then rule = 9, else 10
if i ≡ 94 mod 144 then rule 10 and yellow itarget 634 mod 972 (critical)
if i ≡ 130 mod 216 then lhs = degree 4, rule 9