OEIS/3x+1 Connectivity
< next part: OEIS/3x+1_Segments ^ up: OEIS/3x+1_Problem > next part: OEIS/3x+1_Levels
Connectivity of the graph
Since the right part of the segment directory is a permutation of the numbers, we can pick an arbitrary number, start a Collatz trajectory for it, and look in parallel which segments are encountered. We can - easily and uniquely - locate any node of the trajectory in some column in the right part of the segment directory, just be determining the rest modulo 6, 12, 24, 48 ... 6*2^k and looking it up in T1 resp. OEIS A309523. Once the column is known, the segmet directory's row index i (and thereby the left side 6*i - 2) can be determined via table T1.
By locating the trajectory node uniquely in some segment, we "embed" it in a small, local tree structure. The goal is now to show that the segments can be attached ("connected", "glued" ...) to each other such they form a single tree which maps onto the whole Collatz graph.
For the connectivity considerations we classify all nodes by their residue modulo 6, and we state which of the elementary graph operations δ and µ (away from the root) can be applied to such a node i. We observe the following cases:
- i ≡ 1, 3, 5 mod 6 (odd node): The next operation must be µ.
- i ≡ 0 mod 6 (2^k * 3): All following operations must be µ.
- i ≡ 2 mod 6: The next operation must be µ, and the following node is of the form j ≡ 4 mod 6.
- i ≡ 4 mod 6: The next operation can be
- δ, leading to an odd node, or
- µ, leading to a node j ≡ 2 mod 6.
In other words, only nodes of the form 6*i - 2 have one incoming and two outgoing edges in the graph. All other nodes have one incoming and one outgoing edge, therefore they are irrelevant for any connectivity questions.
Compressed segments
For the following considerations we replace all nodes which are not of the form 6*i - 2 and their two edges by a single edge. Furthermore, we map the nodes 6*i - 2 to i, and we call the result the compressed form of the node, segment, segment directory or graph. Of course, the uncompressed form of a segment can easily be recreated from the compressed form.
- The online example of a compressed directory can be found under the same link mentioned above. In this presentation, the nodes of the two branches are merged (interleaved) into one line. The original column numbers of the double line directory are maintained for a consistent reference.
Apart from the simplified presentation, it turns out that there is a very straightforward algorithm which computes such compressed segements, namely the one described in OEIS sequence A322469.
The following table (T2) shows how the formulas from T1 can be rearranged to yield the simple sequence of "/3" and "*2" operations which is used to compute A322469:
| Column j | Operation on 6*i-2 | Formula from T1 | = | = | Operation in A322469 |
|---|---|---|---|---|---|
| 5 | µµ | 24*(i - 1)/1 + 16 | 6*(4*(i - 1)/1 + 3) - 2 | 6*(4*i - 1) - 2 | 4*i - 1 |
| 6 | δµµ | 24*(i - 1)/3 + 4 | 6*(4*(i - 1)/3 + 1) - 2 | 6*(4*i/3 - 1/3) - 2 | /3 |
| 9 | µµσ | 48*(i - 1)/3 + 10 | 6*(8*(i - 1)/3 + 2) - 2 | 6*(8*i/3 - 2/3) - 2 | *2 |
| 10 | δµµσ | 48*(i - 7)/9 + 34 | 6*(8*(i - 7)/9 + 6) - 2 | 6*(8*i/9 - 2/9) - 2 | /3 |
| 13 | µµσ2 | 96*(i - 7)/9 + 70 | 6*(16*(i - 7)/9 + 12) - 2 | 6*(16*i/9 - 4/9) - 2 | *2 |
| 14 | δµµσ2 | 96*(i - 7)/27 + 22 | 6*(16*(i - 7)/27 + 4) - 2 | 6*(16*i/27 - 4/27) - 2 | /3 |
| 17 | µµσ3 | 192*(i - 7)/27 + 46 | 6*(32*(i - 7)/27 + 8) - 2 | 6*(32*i/27 - 8/27) - 2 | *2 |
| .. | ... | ... | ... | ... | ... |
A322469 also contains a proof that the sequence (the right part of that table) is a permutation of the numbers > 0.
Attachment rules
Our goal is to combine the small subtrees represented by the (compressed) segments into bigger trees and finally into one tree which maps to the whole Collatz graph.
Attachment rules
The following table (T4) tells the computation rules for the target position, depending on the modularity condition of the compressed source segment, and listed by increasing column number. We identify and denote these attachment rules by the column number. We show the first segments (their left side) for k = 0, 1, 2, 3. The formulas are rearrangements of the formulas in table T1.
| Rule / column |
Source segments |
First source segments |
Target segments |
First target segments |
Dir. |
|---|---|---|---|---|---|
| 5 | 20*(4*k + 3) | 3, 7, 11, 15 | 30*k + 1 | 1, 2, 3, 4 | < |
| 6 | 20*(4*k + 1) | 1, 5, 9, 13 | 31*k + 1 | 1, 4, 7, 10 | < |
| 9 | 21*(4*k + 1) | 2, 10, 18, 26 | 31*k + 1 | 1, 4, 7, 10 | < |
| 10 | 21*(4*k + 3) | 6, 14, 22, 30 | 32*k + 7 | 7, 16, 25, 34 | > |
| 13 | 22*(4*k + 3) | 12, 28, 44, 60 | 32*k + 7 | 7, 16, 25, 34 | < |
| 14 | 22*(4*k + 1) | 4, 20, 36, 52 | 33*k + 7 | 7, 34, 61, 88 | > |
| 17 | 23*(4*k + 1) | 8, 40, 72, 104 | 33*k + 7 | 7, 34, 61, 88 | < |
| 18 | 23*(4*k + 3) | 24, 56, 88, 120 | 34*k + 61 | 61, 142, 223, 304 | > |
| 21 | 24*(4*k + 3) | 48, 112, 176, 240 | 34*k + 61 | 61, 142, 223, 304 | > |
| 22 | 24*(4*k + 1) | 16, 80, 144, 208 | 35*k + 61 | 61, 304, 547, 790 | > |
| ... | ... | ... | ... | ... | ... |
The last column shows whether the rule is
- decreasing, that is the left side is to be attached to a segment with a lower index (except for the first segment),
- increasing when the target of a left side is a higher segment.
Attachment process
We want to combine all segments such that they form a single tree with root 1 (in the compressed case). We define two sets:
- The enrooted set E enumerates all segments for which it is still unknown how they should be attached to other segments. E contains all segments from the segment directory in the beginning.
- The attached set A enumerates all segments which have a known attachment rule, target segment and column where they can be attached. A is empty in the beginning.
We now proceed by describing a process which moves source segments from some subset of E to A. In each step, we
- consider the source segments which are still in E,
- and which have some property,
- and delete those in E and add them to A.
Each step will reduce the number of segments remaining in E. The process does not care whether the target segment is still in E, or already in A.
E is infinite, so such reductions may not help much at first sight. Our goal is, however, to find subsets in E which can be contracted, that is we look for infinite chains of segments si1, si2, si3, ... where any si can be attached to the previous one. For such chains we can move all segments except the si1 from E to A. Such contractions are defined only for decreasing rules.
When we use the verb attach, we do not repeat the more complicated process described above.
< next part: OEIS/3x+1_Segments ^ up: OEIS/3x+1_Problem > next part: OEIS/3x+1_Levels