OEIS/3x+1 Connectivity: Difference between revisions

From tehowiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
imported>Gfis
Rules 25, 26
imported>Gfis
mNo edit summary
 
(5 intermediate revisions by the same user not shown)
Line 81: Line 81:
|-
|-
|}
|}
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 a 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.


The last column shows whether the rule is
===Chains of long segments===
* '''decreasing''', that is the left side is to be attached to a segment with a lower index (except for the first segment),
When we attach long segments to each other, we make the following observations:
* '''increasing''' when the target of a left side is a higher segment.
* The target node is always at the '''tail''' of the right part of the target segment (at the last or the last but one node).
===Attachment process===
* (???) If rules >=10 are involved, the left side and the tail are both of the form ''6*i - 2'', that is they have degree 2 (and therefore are shown with yellow/orange/red background in the online directories).
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 following table '''T5''' lists the arithmetic progressions for such segments with degree 2 of the left side and the tail:
* 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.
<!--chaintab.wiki, 2019-08-16, Georg Fischer -->
We now proceed by describing a process which moves source segments from some subset of E to A. In each step, we
{| class="wikitable" style="text-align:left"
* consider the source segments which are still in E,
|-
* and which have some property,
!Rule    !!Left side              !! Increment      !!Tail                  !! Increment      !!Dir.
* 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.  
<!--
|'''5''' ||3<sup>0</sup>*k    + 1||                ||2<sup>0</sup>*k + 3  ||                ||&lt;
|-                                                                           
|'''6''' ||3<sup>1</sup>*k    + 1||                ||2<sup>0</sup>*k + 1  ||                ||&lt;
|-                                                                             
-->                                                                           
|'''9''' ||3<sup>1</sup>*k    + 1|| 8*3<sup>0</sup>||2<sup>3</sup>*k    + 2 || 6*2<sup>0</sup> ||&lt;
|-                                                                                               
|'''10'''||3<sup>2</sup>*k    + 9||-6*3<sup>0</sup>||2<sup>3</sup>*k    + 8 ||-3*2<sup>0</sup> ||'''&gt;'''
|-                                                                                               
|'''13'''||3<sup>2</sup>*k    + 3||12*3<sup>0</sup>||2<sup>4</sup>*k    + 5 || 4*2<sup>0</sup> ||&lt;
|-                                                                                               
|'''14'''||3<sup>3</sup>*k    +15||-1*3<sup>2</sup>||2<sup>4</sup>*k    + 9 ||-2*2<sup>0</sup> ||'''&gt;'''
|-                                                                                               
|'''17'''||3<sup>3</sup>*k    + 6|| 8*3<sup>2</sup>||2<sup>5</sup>*k    + 7 || 6*2<sup>2</sup> ||&lt;
|-                                                                                             
|'''18'''||3<sup>4</sup>*k    + 78||-6*3<sup>2</sup>||2<sup>5</sup>*k  + 31 ||-3*2<sup>2</sup> ||'''&gt;'''
|-                                                                                               
|'''21'''||3<sup>4</sup>*k    + 24||12*3<sup>2</sup>||2<sup>6</sup>*k  + 19 || 4*2<sup>2</sup> ||'''&gt;'''
|-                                                                                               
|'''22'''||3<sup>5</sup>*k  + 132||-1*3<sup>4</sup>||2<sup>6</sup>*k  + 35 ||-2*2<sup>2</sup> ||'''&gt;'''
|-                                                                                               
|'''25'''||3<sup>5</sup>*k  +  51|| 8*3<sup>4</sup>||2<sup>7</sup>*k  + 27 || 6*2<sup>4</sup> ||'''&gt;'''
|-                                                                                               
|'''26'''||3<sup>6</sup>*k  + 699||-6*3<sup>4</sup>||2<sup>7</sup>*k  + 123 ||-3*2<sup>4</sup> ||'''&gt;'''
|-                                                                                                 
|'''29'''||3<sup>6</sup>*k  + 213||12*3<sup>4</sup>||2<sup>8</sup>*k  + 75 || 4*2<sup>4</sup> ||'''&gt;'''
|-                                                                                                 
|'''30'''||3<sup>7</sup>*k  + 1185||-1*3<sup>6</sup>||2<sup>8</sup>*k  + 139 ||-2*2<sup>4</sup> ||'''&gt;'''
|-                                                                                                 
|'''33'''||3<sup>7</sup>*k  +  456|| 8*3<sup>6</sup>||2<sup>9</sup>*k  + 107 || 6*2<sup>6</sup> ||'''&gt;'''
|-                                                                                                 
|'''34'''||3<sup>8</sup>*k  + 6288||-6*3<sup>6</sup>||2<sup>9</sup>*k + 491 ||-3*2<sup>6</sup> ||'''&gt;'''
|-                                                                                                   
|'''37'''||3<sup>8</sup>*k  + 1914||12*3<sup>6</sup>||2<sup>10</sup>*k + 299 || 4*2<sup>6</sup> ||'''&gt;'''
|-                                                                                               
|'''38'''||3<sup>9</sup>*k + 10662||-1*3<sup>8</sup>||2<sup>10</sup>*k + 555 ||-2*2<sup>6</sup> ||'''&gt;'''
|-                                                                                                   
|'''41'''||3<sup>9</sup>*k  + 4101|| ...            ||2<sup>11</sup>*k + 427 || ...c            ||'''&gt;'''
|-                                                                 
|...    ||...                    ||                ||...                   ||                ||'''&gt;'''
|-
|}


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 ''s<sub>i1</sub>, s<sub>i2</sub>, s<sub>i3</sub>, ... '' where any ''s<sub>i</sub>'' can be attached to the previous one. For such chains we can move all segments except the ''s<sub>i1</sub>'' from E to A. Such contractions are defined only for decreasing rules.
Again, the residue conditions become more and more specific with increasing rule number, so it is plausible that it is difficult to build longer chains of such segments.
: For example, if we look at rule 10, we can combine this type of segment only for multiples of 72 (*6 - 2).  


When we use the verb ''attach'', we do not repeat the more complicated process described above.
The additive constants in T5 follow simple linear recurrences, namely [https://oeis.org/A309791 A309791] for the left side and [https://oeis.org/A309792 A309792] for the tail.


<!--
<!--
===Following a Collatz trajectory===
We now have to explain the chains of expanding segments, and prove their finite length.
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.
-->
-->
===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.
<!--
* The '''disrooted set D''' enumerates all segments which have a known attachment rule, target segment and column where they can be attached.  Set ''D'' is empty in the beginning.
-->
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''.
----
----
&lt; next part: [[OEIS/3x%2B1_Segments]] &nbsp; &nbsp; ^ up: [[OEIS/3x%2B1_Problem]] &nbsp; &nbsp; &gt; next part: [[OEIS/3x%2B1_Levels]]
&lt; next part: [[OEIS/3x%2B1_Segments]] &nbsp; &nbsp; ^ up: [[OEIS/3x%2B1_Problem]] &nbsp; &nbsp; &gt; next part: [[OEIS/3x%2B1_Levels]]

Latest revision as of 07:39, 10 September 2019

< 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 a 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.

Chains of long segments

When we attach long segments to each other, we make the following observations:

  • The target node is always at the tail of the right part of the target segment (at the last or the last but one node).
  • (???) If rules >=10 are involved, the left side and the tail are both of the form 6*i - 2, that is they have degree 2 (and therefore are shown with yellow/orange/red background in the online directories).

The following table T5 lists the arithmetic progressions for such segments with degree 2 of the left side and the tail:

Rule Left side Increment Tail Increment Dir.
9 31*k + 1 8*30 23*k + 2 6*20 <
10 32*k + 9 -6*30 23*k + 8 -3*20 >
13 32*k + 3 12*30 24*k + 5 4*20 <
14 33*k +15 -1*32 24*k + 9 -2*20 >
17 33*k + 6 8*32 25*k + 7 6*22 <
18 34*k + 78 -6*32 25*k + 31 -3*22 >
21 34*k + 24 12*32 26*k + 19 4*22 >
22 35*k + 132 -1*34 26*k + 35 -2*22 >
25 35*k + 51 8*34 27*k + 27 6*24 >
26 36*k + 699 -6*34 27*k + 123 -3*24 >
29 36*k + 213 12*34 28*k + 75 4*24 >
30 37*k + 1185 -1*36 28*k + 139 -2*24 >
33 37*k + 456 8*36 29*k + 107 6*26 >
34 38*k + 6288 -6*36 29*k + 491 -3*26 >
37 38*k + 1914 12*36 210*k + 299 4*26 >
38 39*k + 10662 -1*38 210*k + 555 -2*26 >
41 39*k + 4101 ... 211*k + 427 ...c >
... ... ... >

Again, the residue conditions become more and more specific with increasing rule number, so it is plausible that it is difficult to build longer chains of such segments.

For example, if we look at rule 10, we can combine this type of segment only for multiples of 72 (*6 - 2).

The additive constants in T5 follow simple linear recurrences, namely A309791 for the left side and A309792 for the tail.

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.

< next part: OEIS/3x+1_Segments     ^ up: OEIS/3x+1_Problem     > next part: OEIS/3x+1_Levels

Retrieved from "http://teherba.org/tehowiki/index.php?title=OEIS/3x%2B1_Connectivity&oldid=633"