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.

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.

---

< next part: OEIS/3x+1_Segments         > next part: OEIS/3x+1_Proof