OEIS/3x+1 Segments

Segments

These patterns lead us to the construction of special subtrees in the Collatz graph which we call segments. This construction is the main result of this article, and as we will see, it exhibits a nested structure reminding to a ruler. Though the structure is still complicated, it is - in contrast to the Collatz graph - very regular and "predictible" in all it's properties.

Starting at some node of the form 6*i - 2 (the left side, LS), the construction creates two subpaths (the upper branch and the lower branch) which to the right by a prescribed sequence of operations.

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.

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 arranged by increasing left sides in a table S with rows of irregular length, the so-called segment directory].

The reader is encouraged to examine an online example with the first 800 segments at http://teherba.org/fasces/oeis/collatz/double.html. Several variants - which are described later in this article - can be accessed, and trajectories can be followd interactively.

The "double line" presentation form of the segment directory shows the two branches of a segment in one table row. The steps are mapped to columns of the table.

Nodes in the branches 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, orange or red background.

Details of a segment

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

Column j	Branch	Operation	Form of i	Formula	First elements	Covered residues	Remaining residues
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	µµ		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	µµδ	i = 3*k + 1	24*(i - 1)/3 + 5	5, 29, 53, 77	(5 mod 24)
8	lower	δµµδ	i = 3*k + 1	24*(i - 1)/3 + 17	17, 41, 65, 89	(17 mod 24)
9	upper	µµσ	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	µµσδ	i = 9*k + 7	48*(i - 7)/9 + 35	35, 83, 131, 179	(35 mod 48)
12	lower	δµµσδ	i = 9*k + 7	48*(i - 7)/9 + 11	11, 59, 107, 155	(11 mod 38)
13	upper	µµσ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δ	i = 27*k + 7	96*(i - 7)/27 + 23	23, 119, 215, 311	(23 mod 96)
16	lower	δµµσ2δ	i = 27*k + 7	96*(i - 7)/27 + 71	71, 167, 263, 359	(71 mod 96)
17	upper	µµσ3	i = 27*k + 7	192*(i - 7)/27 + 46	46, 238, 430, 622	46 mod 192	94, 142, 190 mod 192
18	lower	δµµσ3	i = 81*k + 61	192*(i - 61)/81 + 142	142, 334, 526, 718	142 mod 192	94, 190, 286, 382 mod 384
19	upper	µµσ3δ	i = 81*k + 61	192*(i - 61)/81 + 143	143, 225, 527, 719	(143 mod 192)
j			i = qj*k + rj	sj*(i - rj)/qj + tj	tj, ...	tj mod sj

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

• q_j = 3^(floor((j - 2) / 4),
• r_j = A066443(floor((j - 2) / 8)) with the OEIS sequence A066443 defined by a(0) = 1; a(n) = 9 * a(n-1) - 2 for n > 0; the terms are the indexes 1, 7, 61, 547, 4921 ... of the variable length segments with left sides 4, 40, 364, 3280, 29524 (OEIS A191681),
• s_j = 3*2^floor((j + 7) / 4),
• t_j = A309523(j) for j >= 3 with the linear recurrent OEIS sequence A309523.

Finite, arbitrary length of the segments

First we have to show that the segment construction process always stops. 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

The mnemonic is that σ "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.

It is also clear that there is no limit on the length of a segment, since we only need to take a segment which has a factor of 3 with a sufficiently high power in its left side. The σ operations will then stretch out to the corresponding length.

Segments do not contain cycles

The modulo conditions of the columns (column "Covered nodes" in T1) ensure that all nodes in a segment are different. Therefore the two branches remain disjoint, and they cannot lead to a cycle inside of the segment. (The question whether cyles could occur when differnt segments are combined is still open).

Coverage of the right part

First we state again that we are not interested in even nodes of the form 3*2*k, because only µ operations can be applied on them. We disregards such nodes.

We see that column 2 contains all odd numbers (i ≡ 1, 3, 5 mod 6). Columns 7, 8, 11, 12, 15, 16, 19, 20 ... also contain subsets of odd numbers, but we disregard these columns, since their terms are duplicated in column 2.

We define the right part of a segment or of the whole segment directory to consist of the terms in columns 2-6, and all higher numbered columns which do not contain odd numbers (that are columns 9, 10, 13, 14, 17, 18 and so on).

We are now interested how the numbers > 0 are distributed over that right part. Corresponding remarks are contained in the last two columns of table T1. We want to show that the nodes in the right part are a permutation of the numbers > 0.

The left sides are in arithmetic progression, and a specific column is computed by a fixed combination of δ and µ operations. Therefore, a column is also in a simple, arithmetic progression. The modulo conditions are all different. The initial terms t_j from OEIS A309523 are also disjoint.

The terms of OEIS A308709 are all disjoint, since that sequence is the set {2^k | k>=0} union {3*2^k | k>=0}, and OEIS A309523 is the set {6*A308709 - 2} union {6*A308709 - 1}.

Together that shows that the terms in the right part are all disjoint.

So far we did not yet cover numbers of the form i ≡ 2, 4 mod 6 (or i ≡ 2, 4, 8, 10 mod 12; 0 mod 6 was excluded above). We proceed by looking into each column in the right part and by observing the modulo conditions of the terms contained in that column.

Column 3 contains numbers of the form i ≡ 8 mod 12, such that 2, 4, 10 mod 12 remain to be covered. Column 4, if it exists, contains numbers of the form i ≡ 2 mod 12. This leaves us with i ≡ 4, 10 mod 12.

As indicated in table T1 above, the modulo conditions in the right part become more and more refined. Since the segment directory contains arbitrarily long segments (respectively arbitrarily many columns), the modulo conditions of any height are finally reached.

Furthermore, since the modulo conditions lead to disjoint subsets of the numbers, it is ensured that any number can occur only once in the right part. In total, the nodes in the right part are a permutation of the numbers which are not divisible by 6.