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.
- 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 simple algorithm which computes such compressed segements, namely the one described in OEIS sequence A322469.
The following table (T2) shows the correspondance between the operations on the nodes 6*i - 2 in the double-line directory, and the compressed nodes i of A322469:
| Column j | Operation on 6*i-2 | Segment 61 | Column | Operation on 4*n-1 | Compressed Seg.61 | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 5 | µµ | - | 6 | δµµ | - | 9 | µµσ | - | 10 | δµµσ | - |
, and a proof that the right part of that table is a permutation of the numbers > 0 is given there. A322469 uses a very simple set of operations on the nodes which is different from the operations described above, but we can map ours to those of than we did so far.
The uncompressed form can easily be recreated from the compressed form.
which is labeled by σ or µ2 respectively.
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). 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