OEIS/3x+1 Connectivity
< next part: OEIS/3x+1_Segments > next part: OEIS/3x+1_Proof
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.
Following a Collatz trajectory
Since we are sure that all numbers occur once in the right part of our segment directory, we can pick any of them and start a Collatz trajectory, hopefully proceeding down to the root (4). In parallel, we try to trace the trajectory in the segment directory.
Covering the Collatz graph by the right part
The fact that all numbers occur at exactly one place in the segment directory is a good indication
- that the whole Collatz graph can be covered by the right part of the segment directory,
- that there are no cycles in the graph, and
- that it really has the form of a tree.
Any number n, be it a start value or a
< next part: OEIS/3x+1_Segments > next part: OEIS/3x+1_Proof