OEIS/3x+1 Problem: Difference between revisions

From tehowiki
Jump to navigation Jump to search
imported>Gfis
minor
imported>Gfis
T2
Line 14: Line 14:
* always to m * 2, and  
* always to m * 2, and  
* to (m - 1) / 3 if m ≡ 1 mod 3.   
* to (m - 1) / 3 if m ≡ 1 mod 3.   
When m ≡ 0 mod 3, the path will continue with duplications only, since these maintain the divisibility by 3.
The Collatz conjecture claims that the graphs contains all numbers, and that - except for the leading cycle 1 - 2 - 4 - 1 - 2 - 4 ... - it has the form of a tree (without cycles). We will not consider the trivial cycle, and we start the graph with node 4, the ''root''.
 
Moreover, a trivial path starts when m ≡ 0 mod 3. We call such a path  a ''sprout'', and it contains duplications only. A sprout must be added to the graph for any node divisible by 3, therefore we will not consider them for the moment.
The Collatz conjecture claims that the graphs contains all numbers, and that - except for the leading cycle 1 - 2 - 4 - 1 - 2 - 4 ... - it has the form of a tree without cycles. We will not be concerned with this cycle, and we start with node 4, the ''root''.  
===Graph Operations===
===Graph Operations===
Following [http://dx.doi.org/10.1155/2014/756917 Trümper], we use abbreviations for the elementary operations which transform a node (element, number) in the Collatz graph according to the following table (T1):
Following [http://dx.doi.org/10.1155/2014/756917 Trümper], we use abbreviations for the elementary operations which transform a node (element, number) in the Collatz graph according to the following table (T1):
Line 45: Line 44:
-->
-->
==Segment Construction==
==Segment Construction==
We will now construct special subsets of paths in the Collatz graph which we call ''segments''. They lead away from the root, and they always start with a node m &#x2261; -2 mod 6. Then they split and follow two subpaths in a prescribed sequence of operations. The segment construction process is stopped when the next node in one of the two subpaths is divisible by 3, resp. when a &delta; operation is no more possible. We assemble the segments as rows of an infinite array <nowiki>C[i,j]</nowiki>, the so-called ''segment directory''. One row i of C is constructed according to the following table (T2):
We will now construct special subsets of paths in the Collatz graph which we call ''segments''. They lead away from the root, and they always start with a node m &#x2261; -2 mod 6. Then they split and follow two subpaths in a prescribed sequence of operations. The segment construction process is stopped when the next node in one of the two subpaths becomes divisible by 3, resp. when a &delta; operation is no more possible. We assemble the segments as rows of an infinite array <nowiki>C[i,j]</nowiki>, the so-called ''segment directory''. The columns in one row i of C are constructed as described in the following table (T2):
{| class="wikitable" style="text-align:left"
{| class="wikitable" style="text-align:left"
!Column                   !! Operation                                     !! Formula !! Condition !! Sequence           
!Column j                !! Operation               !! Formula                 !! Condition           !! Sequence           
|-
|-
| <nowiki>C[i,1]</nowiki> ||                                                || 6 * i - 2   ||                   || 4, 10, 16, 22, 28, ...
| 1 ||                                                || 6 * i - 2               ||                     || 4, 10, 16, 22, 28, ...
|-
|-
| <nowiki>C[i,2]</nowiki> || <nowiki>C[i,1]</nowiki> &micro;&micro;        || 24 * (i - 1)  + 16      ||                      || 16, 40, 64, 88, 112, ...  
| 2 || <nowiki>C[i,1]</nowiki> &micro;&micro;        || 24 * (i - 1)  + 16      ||                      || 16, 40, 64, 88, 112, ...  
|-
|-
| <nowiki>C[i,3]</nowiki> || <nowiki>C[i,1]</nowiki> &delta;&micro;&micro;  || 24 * (i - 1) / 3 +  4    || i &#x2261; 1 mod 3  ||  4, 28, 52, 76, 100, ...
| 3 || <nowiki>C[i,1]</nowiki> &delta;&micro;&micro;  || 24 * (i - 1) / 3 +  4    || i &#x2261; 1 mod 3  ||  4, 28, 52, 76, 100, ...
|-
|-
| <nowiki>C[i,4]</nowiki> || <nowiki>C[i,2]</nowiki> &sigma;                || 48 * (i - 1) / 3 + 10    || i &#x2261; 1 mod 3  || 10, 58, 106, 134, ...   
| 4 || <nowiki>C[i,2]</nowiki> &sigma;                || 48 * (i - 1) / 3 + 10    || i &#x2261; 1 mod 3  || 10, 58, 106, 134, ...   
|-
|-
| <nowiki>C[i,5]</nowiki> || <nowiki>C[i,3]</nowiki> &sigma;                || 48 * (i - 7) / 9 + 34    || i &#x2261; 7 mod 9  || 34, 82, 130, 178, ...   
| 5 || <nowiki>C[i,3]</nowiki> &sigma;                || 48 * (i - 7) / 9 + 34    || i &#x2261; 7 mod 9  || 34, 82, 130, 178, ...   
|-
|-
| <nowiki>C[i,6]</nowiki> || <nowiki>C[i,2]</nowiki> &sigma;&sigma;        || 96 * (i - 7) / 9 + 70    || i &#x2261; 7 mod 9  || 70, 166, 262, 358, ...  
| 6 || <nowiki>C[i,2]</nowiki> &sigma;&sigma;        || 96 * (i - 7) / 9 + 70    || i &#x2261; 7 mod 9  || 70, 166, 262, 358, ...  
|-
|-
| <nowiki>C[i,7]</nowiki> || <nowiki>C[i,3]</nowiki> &sigma;&sigma;        || 96 * (i - 7) / 27 + 22  || i &#x2261; 7 mod 27  || 22, 118, 214, 310, ...  
| 7 || <nowiki>C[i,3]</nowiki> &sigma;&sigma;        || 96 * (i - 7) / 27 + 22  || i &#x2261; 7 mod 27  || 22, 118, 214, 310, ...  
|-
|-
| <nowiki>C[i,8]</nowiki> || <nowiki>C[i,2]</nowiki> &sigma;&sigma;&sigma;  || 192 * (i - 7) / 27  + 46 || i &#x2261; 7  mod 27 || 46, 238, 430, 622, ...
| 8 || <nowiki>C[i,2]</nowiki> &sigma;&sigma;&sigma;  || 192 * (i - 7) / 27  + 46 || i &#x2261; 7  mod 27 || 46, 238, 430, 622, ...
|-
|-
| <nowiki>C[i,9]</nowiki> || <nowiki>C[i,3]</nowiki> &sigma;&sigma;&sigma;  || 192 * (i - 61) / 81 + 142|| i &#x2261; 61 mod 81 || 142, 334, ...         
| 9 || <nowiki>C[i,3]</nowiki> &sigma;&sigma;&sigma;  || 192 * (i - 61) / 81 + 142|| i &#x2261; 61 mod 81 || 142, 334, ...         
|-
|-
| ... || ... || ... || ... || ...  
| ... || ... || ... || ... || ...  
|-
|-
|}
|}
The first column(s) <nowiki>C[i,1]</nowiki> will be denoted as the ''left part'' of the segment (or of the whole directory), while the columns <nowiki>C[i,j], j &gt; 1</nowiki> will be the ''right part''. We make a number of claims for such segments:
The first column(s) <nowiki>C[i,1]</nowiki> will be denoted as the ''left part'' of the segment (or of the whole directory), while the columns <nowiki>C[i,j], j &gt; 1</nowiki> will be the ''right part''. We make a number of claims for such segments:
* (C1) All nodes in the segment directory are of the form 6 * n - 2.
* (C1) All nodes in the segment directory are of the form 6 * n - 2.
: This follows from the formula for columns <nowiki>C[i,1..3]</nowiki>, and for any higher column numbers from the 3-by-2 replacement property of the &sigma; operation.  
: This follows from the formula for columns <nowiki>C[i,1..3]</nowiki>, and for any higher column numbers from the 3-by-2 replacement property of the &sigma; operation.  
Line 80: Line 79:
-->
-->
* (C4) All nodes in the right part of a segment are different.
* (C4) All nodes in the right part of a segment are different.
: For <nowiki>C[i,1..2]</nowiki> we see that the values modulo 24 are different. For the remaining columns, we see that the exponents of the factors 2 and 3 are different. They are shifted by the &sigma; operations, but they alternate, for example (right part of segment with left part 40):
: For <nowiki>C[i,1..2]</nowiki> we see that the values modulo 24 are different. For the remaining columns, we see that the exponents of the factors 2 and 3 are different. They are shifted by the &sigma; operations, but they alternate, for example (in the segment with left part 40):
  160 = 6 * 3<sup>3</sup> * 2<sup>0</sup> - 2
  160 = 6 * (3<sup>3</sup> * 2<sup>0</sup> * 1) - 2
   52 = 6 * 3<sup>2</sup> * 2<sup>0</sup> - 2
   52 = 6 * (3<sup>2</sup> * 2<sup>0</sup> * 1) - 2
  106 = 6 * 3<sup>2</sup> * 2<sup>1</sup> - 2
  106 = 6 * (3<sup>2</sup> * 2<sup>1</sup> * 1) - 2
   34 = 6 * 3<sup>1</sup> * 2<sup>1</sup> - 2
   34 = 6 * (3<sup>1</sup> * 2<sup>1</sup> * 1) - 2
   70 = 6 * 3<sup>1</sup> * 2<sup>2</sup> - 2
   70 = 6 * (3<sup>1</sup> * 2<sup>2</sup> * 1) - 2
   22 = 6 * 3<sup>0</sup> * 2<sup>2</sup> - 2
   22 = 6 * (3<sup>0</sup> * 2<sup>2</sup> * 1) - 2
   46 = 6 * 3<sup>0</sup> * 2<sup>3</sup> - 2
   46 = 6 * (3<sup>0</sup> * 2<sup>3</sup> * 1) - 2
* (C5) There is no cycle in a segment.
* (C5) There is no cycle in a segment.
===Segment Lengths===
===Segment Lengths===
Line 115: Line 114:
: The sequences defined by the columns in the right part all have differen modulus conditions. Therefore they are all disjoint.  
: The sequences defined by the columns in the right part all have differen modulus conditions. Therefore they are all disjoint.  
==Segment Connectivity Sieve==
==Segment Connectivity Sieve==
The segments are small trees with two branches. We now start an ''Gedankenexperiment'' analogous to [https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel Hilbert's hotel]. We consider simultaneously all rows i &gt; 1 in C fulfilling some modularity condition (the ''source'' row in C), and we ''attach'' (identify, connect) them to their unique occurrence in the right part of C (''target'' row and column).  
The segments represent small trees with two branches. We now start an ''Gedankenexperiment'' analogous to [https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel Hilbert's hotel]. We consider simultaneously all rows i &gt; 1 (omitting the root) in C which fulfill some modularity condition (the ''source'' row in C), and we ''attach'' (identify, connect) them to their unique occurrence in the right part of C (''target'' row and column).  
: A technical implementation of the process (which is impossible for infinite sets) would perhaps replace the target node by a pointer to the source segment.  
: A technical implementation of the process (which is impossible for infinite sets) would perhaps replace the target node by a pointer to the source segment.  
We ''sieve'' the segments: Once we have attached a set of segements, we strike it out of the list still to be examined.  The attachment rules are shown in the following table (T4):
We ''sieve'' the segments: Once we have attached a set of segments, we strike it out of the list still to be examined.  The attachment rules are shown in the following table (T4):
{| class="wikitable" style="text-align:left"
{| class="wikitable" style="text-align:left"
|-
|-
Line 147: Line 146:
* (C8) The process does not create any cycle.
* (C8) The process does not create any cycle.
: All involved subtrees are disjoint. The process attaches tree to other trees, the results are trees again.  
: All involved subtrees are disjoint. The process attaches tree to other trees, the results are trees again.  
* (C9) Any source row can be attached to the root segment.
* (C9) Any source row will finally e attached to the tree starting at the root segment.
: As for the coverage, we have to apply the rules from table T4 one after the other up to a sufficiently high row (corresponding to a sufficiently long variable segment).  
: As for the coverage, we have to apply the rules from table T4 one after the other up to a sufficiently high row (corresponding to a sufficiently long variable segment).  
* (C10) In the end, the graph of attached segments would be one tree starting at 4.
 
<!--
<!--
Example: Segment for 4 with segments for 16 and 10 attached:
Example: Segment for 4 with segments for 16 and 10 attached:
Line 159: Line 158:
-->
-->
==Collatz Tree==
==Collatz Tree==
* (C11) The segment tree is a subgraph of the Collatz graph.
* (C10) The segment tree is a subgraph of the Collatz graph.
: The edges of the segment tree carry combined operations &micro;&micro;, &delta;&micro;&micro; and &sigma; = &delta;&micro;.  
: The edges of the segment tree carry combined operations &micro;&micro;, &delta;&micro;&micro; and &sigma; = &delta;&micro;.  
So far, numbers of the form x &#x2261; 0, 1, 2, 3, 5 mod 6 are missing from the segment tree. We insert intermediate nodes into the segment tree by applying operations on a node of the form 6 * i -2 as shown in the following table (T5):
So far, numbers of the form x &#x2261; 0, 1, 2, 3, 5 mod 6 are missing from the segment tree. We insert intermediate nodes into the segment tree by applying operations on a node of the form 6 * i -2 as shown in the following table (T5):
Line 177: Line 176:
|-
|-
|}
|}
The first 3 rows in T5 care for the intermediate nodes at the beginning of the segment construction with columns 1, 2, 3. Rows 4 and 5 operate on multiples of 3 which are not contained in the segement directory.   
The first three rows in T5 care for the intermediate nodes at the beginning of the segment construction with columns 1, 2, 3. Rows 4 and 5 care for the sprouts (starting at multiples of 3) which are not contained in the segment directory.   
<!--
<!--
We call such a construction a ''detailed segment'' (in contrast to the ''compressed segments'' described above). A '''[http://www.teherba.org/fasces/oeis/collatz/rails.html detailed segment directory]''' can easily be created by a [https://github.com/gfis/fasces/blob/master/oeis/collatz/collatz_rails.pl Perl program].
We call such a construction a ''detailed segment'' (in contrast to the ''compressed segments'' described above). A '''[http://www.teherba.org/fasces/oeis/collatz/rails.html detailed segment directory]''' can easily be created by a [https://github.com/gfis/fasces/blob/master/oeis/collatz/collatz_rails.pl Perl program].
-->
-->
* (C12) The connectivity of the segment tree remains unaffected by the insertions.
* (C11) The connectivity of the segment tree remains unaffected by the insertions.
* (C13) With the insertions of T5, the segment tree covers the whole Collatz graph.
* (C12) With the insertions of T5, the segment tree covers the whole Collatz graph.
* (C14) '''The Collatz graph is a tree (except for the trivial cycle).'''
* (C13) '''The Collatz graph is a tree (except for the trivial cycle).'''

Revision as of 08:30, 24 September 2018

Introduction

Collatz sequences are sequences of non-negative integer numbers with a simple construction rule:

Even elements are halved, and odd elements are multiplied by 3 and then incremented by 1.

Since decades it is unknown whether the final cyle 4 - 2 - 1 is always reached for any start value. This problem is the Collatz conjecture, for which the english Wikipedia states:

It is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani's problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse's algorithm (after Helmut Hasse), or the Syracuse problem; the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers (because the values are usually subject to multiple descents and ascents like hailstones in a cloud), or as wondrous numbers.

Straightforward visualizations of the Collatz sequences no obvious structure. The sequences for the first dozen of start values are rather short, but the sequence for 27 suddenly has 112 elements.

References

  • Jeffry C. Lagarias, Ed.: The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010, ISBN 978-8218-4940-8. MBK78
  • OEIS A07165: File of first 10K Collatz sequences, ascending start values, with lengths
  • Manfred Trümper: The Collatz Problem in the Light of an Infinite Free Semigroup. Chinese Journal of Mathematics, Vol. 2014, Article ID 756917, 21 p.

Collatz Graph

When all Collatz sequences are read backwards, they form the Collatz graph starting with 1, 2, 4, 8 ... . At each node m > 4 in the graph, the path from the root (4) can be continued

  • always to m * 2, and
  • to (m - 1) / 3 if m ≡ 1 mod 3.

The Collatz conjecture claims that the graphs contains all numbers, and that - except for the leading cycle 1 - 2 - 4 - 1 - 2 - 4 ... - it has the form of a tree (without cycles). We will not consider the trivial cycle, and we start the graph with node 4, the root. Moreover, a trivial path starts when m ≡ 0 mod 3. We call such a path a sprout, and it contains duplications only. A sprout must be added to the graph for any node divisible by 3, therefore we will not consider them for the moment.

Graph Operations

Following Trümper, we use abbreviations for the elementary operations which transform a node (element, number) in the Collatz graph according to the following table (T1):

Name Mnemonic Distance to root Mapping Condition
d down -1 m ↦ m / 2 m ≡ 0 mod 2
u up -1 m ↦ 3 * m + 1 (none)
s := ud spike -2 m ↦ (m / 2) * 3 + 1 m ≡ 0 mod 2
δ divide +1 m ↦ (m - 1) / 3 m ≡ 1 mod 3
µ multiply +1 m ↦ m * 2 (none)
σ := δµ squeeze +2 m ↦ ((m - 1) / 3) * 2 m ≡ 1 mod 3

We will mainly be interested in the reverse mappings (denoted with greek letters) which move away from the root of the graph.

3-by-2 Replacement

The σ operation, applied to numbers of the form 6 * m - 2, has an interesting property:

(6 * (3 * n) - 2) σ = 4 * 3 * n - 2 =  6 * (2 * n) - 2

In other words, as long as m contains a factor 3, the σ operation maintains the form 6 * x - 2, and it replaces the factor 3 by 2 (it "squeezes" a 3 into a 2). In the opposite direction, the s operation replaces a factor 2 in m by 3.

Segment Construction

We will now construct special subsets of paths in the Collatz graph which we call segments. They lead away from the root, and they always start with a node m ≡ -2 mod 6. Then they split and follow two subpaths in a prescribed sequence of operations. The segment construction process is stopped when the next node in one of the two subpaths becomes divisible by 3, resp. when a δ operation is no more possible. We assemble the segments as rows of an infinite array C[i,j], the so-called segment directory. The columns in one row i of C are constructed as described in the following table (T2):

Column j Operation Formula Condition Sequence
1 6 * i - 2 4, 10, 16, 22, 28, ...
2 C[i,1] µµ 24 * (i - 1) + 16 16, 40, 64, 88, 112, ...
3 C[i,1] δµµ 24 * (i - 1) / 3 + 4 i ≡ 1 mod 3 4, 28, 52, 76, 100, ...
4 C[i,2] σ 48 * (i - 1) / 3 + 10 i ≡ 1 mod 3 10, 58, 106, 134, ...
5 C[i,3] σ 48 * (i - 7) / 9 + 34 i ≡ 7 mod 9 34, 82, 130, 178, ...
6 C[i,2] σσ 96 * (i - 7) / 9 + 70 i ≡ 7 mod 9 70, 166, 262, 358, ...
7 C[i,3] σσ 96 * (i - 7) / 27 + 22 i ≡ 7 mod 27 22, 118, 214, 310, ...
8 C[i,2] σσσ 192 * (i - 7) / 27 + 46 i ≡ 7 mod 27 46, 238, 430, 622, ...
9 C[i,3] σσσ 192 * (i - 61) / 81 + 142 i ≡ 61 mod 81 142, 334, ...
... ... ... ... ...

The first column(s) C[i,1] will be denoted as the left part of the segment (or of the whole directory), while the columns C[i,j], j > 1 will be the right part. We make a number of claims for such segments:

  • (C1) All nodes in the segment directory are of the form 6 * n - 2.
This follows from the formula for columns C[i,1..3], and for any higher column numbers from the 3-by-2 replacement property of the σ operation.
  • (C2) All segments have a finite length.
At some point the σ operations will have replaced all factors 3 by 2.
  • (C4) All nodes in the right part of a segment are different.
For C[i,1..2] we see that the values modulo 24 are different. For the remaining columns, we see that the exponents of the factors 2 and 3 are different. They are shifted by the σ operations, but they alternate, for example (in the segment with left part 40):
160 = 6 * (33 * 20 * 1) - 2
 52 = 6 * (32 * 20 * 1) - 2
106 = 6 * (32 * 21 * 1) - 2
 34 = 6 * (31 * 21 * 1) - 2
 70 = 6 * (31 * 22 * 1) - 2
 22 = 6 * (30 * 22 * 1) - 2
 46 = 6 * (30 * 23 * 1) - 2
  • (C5) There is no cycle in a segment.

Segment Lengths

The segment directory is obviously very structured. The lengths of the compressed segments follow the pattern

4 2 2 4 2 2 L1 2 2 4 2 2 4 2 2 L2 2 2 4 2 2 ...

with two fixed lengths 2 and 4 and some variable lengths L1, L2 ... > 4. For the left parts 4, 40, 364, 3280, 29524 (OEIS A191681), the segment lengths have high values 4, 8, 12, 16, 20 which did not occur before. Those left parts are (9n+1 - 1) / 2, or 4 * Sum(9i, i = 0..n).

Coverage of the Right Part

We now examine the modular conditions which result from the segment construction table in order to find out how the numbers of the form 6 * n -2 are covered by the right part of the segment directory, as shown in the following table (T3):

Columns j Covered Remaining
2-3 4, 16 mod 24 10, 22, 34, 46 mod 48
3-4 10, 34 mod 48 22, 46, 70, 94 mod 96
5-6 70, 22 mod 96 46, 94, 142, 190 mod 192
7-8 46, 142 mod 192 94, 190, 286, 382 mod 384
... ... ...

We can always exclude the first and the third element remaining so far by looking in the next two columns of segments with sufficient length.

  • (C6) There is no limit on the length of a segment.
We only need to take a segment which, in its right part, has a factor of 3 with a sufficiently high power, and the σ operations will stretch out the segment accordingly.

Therefore we can continue the modulus table above indefinitely, which leads us to the claim:

  • (C7) All numbers of the form 6 * n - 2 occur exactly once in the right part C[i,j], j > 1 of the segment directory.
The sequences defined by the columns in the right part all have differen modulus conditions. Therefore they are all disjoint.

Segment Connectivity Sieve

The segments represent small trees with two branches. We now start an Gedankenexperiment analogous to Hilbert's hotel. We consider simultaneously all rows i > 1 (omitting the root) in C which fulfill some modularity condition (the source row in C), and we attach (identify, connect) them to their unique occurrence in the right part of C (target row and column).

A technical implementation of the process (which is impossible for infinite sets) would perhaps replace the target node by a pointer to the source segment.

We sieve the segments: Once we have attached a set of segments, we strike it out of the list still to be examined. The attachment rules are shown in the following table (T4):

Source Row i Target Row Column Remaining Rows Fraction
i ≡ 3 mod 4 ((i - 3) / 4) * 30 + 1 2 i ≡ 0, 1, 2 mod 4 3/4
i ≡ 1 mod 4 ((i - 1) / 4) * 31 + 1 3 i ≡ 0, 2, 4, 6 mod 8 1/2
i ≡ 2 mod 8 ((i - 2) / 8) * 31 + 1 4 i ≡ 0, 4, 6 mod 8 3/8
i ≡ 6 mod 8 ((i - 6) / 8) * 32 + 7 5 i ≡ 0, 4, 8, 12 mod 16 1/4
i ≡ 12 mod 16 ((i - 12) / 16) * 32 + 7 6 i ≡ 0, 4, 8 mod 16 3/16
i ≡ 4 mod 16 ((i - 4) / 16) * 33 + 7 7 i ≡ 0, 8, 16, 24 mod 32 1/8
i ≡ 8 mod 32 ((i - 8) / 32) * 33 + 7 8 i ≡ 0, 16, 24 mod 32 3/32
i ≡ 24 mod 32 ((i - 24) / 32) * 34 + 61 9 i ≡ 0, 16, 32, 48 mod 64 1/16
i ≡ 48 mod 64 ((i - 48) / 64) * 34 + 61 10 i ≡ 0, 16, 32 mod 64 3/64
... ... ... ... ...

The ellipsis row of this table could be explained in terms of i, but it should be obvious how it can be constructed. The residues of 2k in the first column are 3 * 2k-2, 1 * 2k-2 in an alternating sequence. The additive constants in the second column are the indexes of the variable length segments with left parts (4), 40, 364, 3280, 29524 (OEIS A191681) mentioned above. They are repeated 4 times since the corresponding lengths "jump" by 4.

Segment Tree

  • (C8) The process does not create any cycle.
All involved subtrees are disjoint. The process attaches tree to other trees, the results are trees again.
  • (C9) Any source row will finally e attached to the tree starting at the root segment.
As for the coverage, we have to apply the rules from table T4 one after the other up to a sufficiently high row (corresponding to a sufficiently long variable segment).

Collatz Tree

  • (C10) The segment tree is a subgraph of the Collatz graph.
The edges of the segment tree carry combined operations µµ, δµµ and σ = δµ.

So far, numbers of the form x ≡ 0, 1, 2, 3, 5 mod 6 are missing from the segment tree. We insert intermediate nodes into the segment tree by applying operations on a node of the form 6 * i -2 as shown in the following table (T5):

Operation Condition Resulting Nodes Remaining Nodes
δ 2 * i - 1 i ≡ 0, 2, 6, 8 mod 12
µ 12 * i - 4 i ≡ 0, 2, 6 mod 12
δµ i ≡ 1, 2 mod 3 4 * i - 2 i ≡ 0, 12 mod 24
δµµ i ≡ 2 mod 3 8 * i - 4 i ≡ 0 mod 24
δµµµ i ≡ 2 mod 3 16 * i - 8 (none)

The first three rows in T5 care for the intermediate nodes at the beginning of the segment construction with columns 1, 2, 3. Rows 4 and 5 care for the sprouts (starting at multiples of 3) which are not contained in the segment directory.

  • (C11) The connectivity of the segment tree remains unaffected by the insertions.
  • (C12) With the insertions of T5, the segment tree covers the whole Collatz graph.
  • (C13) The Collatz graph is a tree (except for the trivial cycle).