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.
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 | > |
| 25 | 25*(4*k + 1) | ... | 35*k + 61 | ... | > |
| 26 | 25*(4*k + 3) | ... | 36*k + 547 | ... | > |
| ... | ... | ... | ... | ... | > |
The last column shows whether the rule (or the left side, segment, subtree) is
- shrinking, that is the left side is to be attached to a segment with a lower index (or same index for the root segment 1),
- expanding otherwise, that is when the left side is to be attached to a segment with higher index.
Expanding segments result from rules 10, 14, 18, 21 and all following (with a ">" symbol in the last column of the table above). They are all long segments with more than 3 nodes in the right part.
Attachment process
At the beginning we have the infinite set of small subtrees represented by the segments. We want to combine all segments such that they finally form a single tree with root 1 (in the compressed case). We define the enrooted set E to enumerate all segments for which it is still unknown how they should be attached to other segments. Expanding (long) segments may sometimes be attached to each other. As we will see below, the attachment target is always at the end of the segment (it is the last or the last but one node in the right part). Furthermore, we claim that chains of expanding segments always have a finite length, and that we can build those chains.
- Step 0: Set E contains all segments from the segment directory in the beginning.
- Step 1: Build all chains of expanding segments by a process which is described below. The chains must have finite length.
- Step 2: For each such chain, attach the first left side to its target (which is shrinking), and remove all (expanding) segments of the chain. In the end E contains shrinking subtrees only.
- Step 3: For each remaining subtree s > 1 assembled so far in E attach s to its target and then remove it from E. This target of the left side is unique and always exists in some subtree assembled so far in E. A loop cannot be created because any node > 1 is reached by exactly one other node.
- Step 4: The tree above segment 1 is the only one which remains in E.
Chains of expanding segments
We now have to explain the chains of expanding segments, and prove their finite length. First we observe that the target node is always at the end of the right part of the target segment (the last or the last but one node).
< next part: OEIS/3x+1_Segments ^ up: OEIS/3x+1_Problem > next part: OEIS/3x+1_Levels