OEIS/Collatz Story: Difference between revisions

From tehowiki
Jump to navigation Jump to search
imported>Gfis
Playground for 3x+1 Problem
imported>Gfis
save
Line 2: Line 2:
'''Collatz sequences''' (also called  ''trajectories'') are sequences of integer numbers > 0. For any start value > 0 the elements of the sequence are constructed with two simple rules:
'''Collatz sequences''' (also called  ''trajectories'') are sequences of integer numbers > 0. For any start value > 0 the elements of the sequence are constructed with two simple rules:
# Even numbers are halved.
# Even numbers are halved.
# Odd numbers are multiplied by 3 and then incremented by 1.  
# Odd numbers 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 all start values. This problem is the '''Collatz conjecture''', for which the [https://en.wikipedia.org/wiki/Collatz_conjecture english Wikipedia] states:  
Since decades it is unknown whether the final cyle 4 - 2 - 1 is always reached for all start values. This problem is the '''Collatz conjecture''', for which the [https://en.wikipedia.org/wiki/Collatz_conjecture 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.
: 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 Collatz sequences show no obvious structure. The sequences for the first dozen of start values are rather short, but the sequence for 27 suddenly has 112 elements.  
Straightforward visualizations of Collatz sequences show 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===
===References===
* Jeffry C. Lagarias, Ed.: ''The Ultimate Challenge: The 3x+1 Problem'', Amer. Math. Soc., 2010, ISBN 978-8218-4940-8. [http://www.ams.org/bookpages/mbk-78 MBK78]
* Jeffry C. Lagarias, Ed.: ''The Ultimate Challenge: The 3x+1 Problem'', Amer. Math. Soc., 2010, ISBN 978-8218-4940-8. [http://www.ams.org/bookpages/mbk-78 MBK78]
Line 13: Line 13:
==Collatz Graph==
==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
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  
* always to m * 2, and
* to (m - 1) / 3 if m ≡ 1 mod 3.
* to (m - 1) / 3 if m ≡ 1 mod 3.
The Collatz conjecture claims that the graphs contains all numbers, and that - except for the trivial, 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'''.  
The Collatz conjecture claims that the graphs contains all numbers, and that - except for the trivial, 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, another trivial type of 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.
Moreover, another trivial type of 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===
===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):
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
!Name    !! Mnemonic  !! Distance to root !!  Mapping            !! Condition        
!Name    !! Mnemonic  !! Distance to root !!  Mapping            !! Condition
|-
|-
| d      || down      || -1            ||  m ↦ m / 2          || m ≡ 0 mod 2
| d      || down      || -1            ||  m ↦ m / 2          || m ≡ 0 mod 2
|-
|-
| u      || up        || -1            ||  m ↦ 3 * m + 1      || (m ≡ 1 mod 2)            
| u      || up        || -1            ||  m ↦ 3 * m + 1      || (m ≡ 1 mod 2)
|-
|-
| s := ud || spike    || -2            ||  m ↦ (3 * m + 1) / 2) || m ≡ 1 mod 2            
| s := ud || spike    || -2            ||  m ↦ (3 * m + 1) / 2) || m ≡ 1 mod 2
|-
|-
| δ || divide    || +1            ||  m ↦ (m - 1) / 3    || m ≡ 1 mod 3    
| δ || divide    || +1            ||  m ↦ (m - 1) / 3    || m ≡ 1 mod 3
|-
|-
| µ || multiply  || +1            ||  m ↦ m * 2          || (none)
| µ || multiply  || +1            ||  m ↦ m * 2          || (none)
|-
|-
| σ := δµ|| squeeze || +2 ||  m ↦ ((m - 1) / 3) * 2 || m ≡ 1 mod 3  
| σ := δµ|| 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.
We will mainly be interested in the reverse mappings (denoted with greek letters) which move away from the root of the graph.
Line 38: Line 38:
The σ operation, applied to numbers of the form 6 * m - 2, has an interesting property:
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
  (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.  
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.
<!--
<!--
=== Trivial paths===
=== Trivial paths===
Line 45: Line 45:
  (n &#x2261; 0 mod 3) uuu ... u (n * 2<sup>k</sup>) ... - multiples of 3
  (n &#x2261; 0 mod 3) uuu ... u (n * 2<sup>k</sup>) ... - multiples of 3
===Kernels===
===Kernels===
By the ''kernel'' of a number n = 6 * m - 2 we denote the "2-3-free" factor of m, that is the factor which remains when all powers of 2 and 3 have been removed from m.  
By the ''kernel'' of a number n = 6 * m - 2 we denote the "2-3-free" factor of m, that is the factor which remains when all powers of 2 and 3 have been removed from m.
* The kernel is not affected by &sigma; and s operations.
* The kernel is not affected by &sigma; and s operations.
-->
-->
Line 53: Line 53:
  143/104: 143 u 430 d 215 u 646 d 323 u 970 d 485 u 1456 d 728 d 364 ] 182, 91, ... 4, 2, 1
  143/104: 143 u 430 d 215 u 646 d 323 u 970 d 485 u 1456 d 728 d 364 ] 182, 91, ... 4, 2, 1
             +1  *6+4    +1  *6+4    +1  *6+4    +1  *6+4  *6+2    +0    +0 ...
             +1  *6+4    +1  *6+4    +1  *6+4    +1  *6+4  *6+2    +0    +0 ...
The third line tells how the second line could be computed from the first.  
The third line tells how the second line could be computed from the first.
Walking from right to left, the step pattern is:
Walking from right to left, the step pattern is:
  &delta; &micro; &micro; &delta; &micro; &delta; &micro; &delta; &micro;  
  &delta; &micro; &micro; &delta; &micro; &delta; &micro; &delta; &micro;
  &micro; &micro; &delta; &micro; &delta; &micro; &delta; &micro; &delta;
  &micro; &micro; &delta; &micro; &delta; &micro; &delta; &micro; &delta;
The alternating pattern of operations can be continued to the left with 4 additional pairs of steps:
The alternating pattern of operations can be continued to the left with 4 additional pairs of steps:
   q? u [ 62 d  31 u  94 d  47 u 142 d ...
   q? u [ 62 d  31 u  94 d  47 u 142 d ...
  126 d [ 63 u 190 d  95 u 286 d 143 u ...
  126 d [ 63 u 190 d  95 u 286 d 143 u ...
         +1  *6+4    +1  *6+4    +1
         +1  *6+4    +1  *6+4    +1
The pattern stops here since there is no number q such that q * 3 + 1 = 62.  
The pattern stops here since there is no number q such that q * 3 + 1 = 62.


==Segment Construction==
==Segment Construction==
These patterns lead us to the construction of 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''.  
These patterns lead us to the construction of 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''.
: Informally, and in the two examples above, we consider the terms betweeen the square brackets. For the moment, we only take those which are which are &#x2261; 4 mod 6 (for "compressed" segments, below there are also "detailed" segments where we take all). We start at the right and with the lower line, and we interleave the terms &#x2261; 4 mod 6 of the two lines to get a segment.  
: Informally, and in the two examples above, we consider the terms betweeen the square brackets. For the moment, we only take those which are which are &#x2261; 4 mod 6 (for "compressed" segments, below there are also "detailed" segments where we take all). We start at the right and with the lower line, and we interleave the terms &#x2261; 4 mod 6 of the two lines to get a segment.
The columns in one row i of the array C are constructed as described in the following table (T2):
The columns in one row i of the array C are constructed as described in the following table (T2):
{| class="wikitable" style="text-align:left"
{| class="wikitable" style="text-align:left"
!Column j                !! Operation                !! Formula                  !! Condition            !! Sequence        
!Column j                !! Operation                !! Formula                  !! Condition            !! Sequence
|-
|-
| 1 ||                                                || 6 * i - 2                ||                      || 4, 10, 16, 22, 28, ...
| 1 ||                                                || 6 * i - 2                ||                      || 4, 10, 16, 22, 28, ...
|-
|-
| 2 || <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, ...
|-
|-
| 3 || <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, ...
|-
|-
| 4 || <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, ...
|-
|-
| 5 || <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, ...
|-
|-
| 6 || <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, ...
|-
|-
| 7 || <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, ...
|-
|-
| 8 || <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, ...
|-
|-
| 9 || <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, ...
|-
|-
| ... || ... || ... || ... || ...  
| ... || ... || ... || ... || ...
|-
|-
|}
|}
Line 140: Line 140:
We make a number of claims for segments:
We make a number of claims for 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.
* (C2) All segments have a finite length.
* (C2) All segments have a finite length.
: At some point the &sigma; operations will have replaced all factors 3 by 2.
: At some point the &sigma; operations will have replaced all factors 3 by 2.
* (C3) All nodes in the right part of a segment have the form 6 * (3<sup>n</sup> * 2<sup>m</sup> * f) - 2 with the same "3-2-free" factor f.
* (C3) All nodes in the right part of a segment have the form 6 * (3<sup>n</sup> * 2<sup>m</sup> * f) - 2 with the same "3-2-free" factor f.
: This follows from the operations for columns <nowiki>C[i,1..3]</nowiki>, and from the fact that the &sigma; operation maintains this property.  
: This follows from the operations for columns <nowiki>C[i,1..3]</nowiki>, and from the fact that the &sigma; operation maintains this property.
* (C4) All nodes in the right part of a particular segment are  
* (C4) All nodes in the right part of a particular segment are
** different among themselves, and  
** different among themselves, and
** different from the left side of that segment (except for the first segment for the root 4).
** different from the left side of that segment (except for the first segment for the root 4).
: 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):
: 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):
Line 164: Line 164:
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):
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):
{| class="wikitable" style="text-align:left"
{| class="wikitable" style="text-align:left"
!Columns j  !! Covered !! Remaining        
!Columns j  !! Covered !! Remaining
|-
|-
| 2-3 ||  4, 16 mod 24 || 10, 22, 34, 46 mod 48
| 2-3 ||  4, 16 mod 24 || 10, 22, 34, 46 mod 48
Line 176: Line 176:
| ... ||  ... || ...
| ... ||  ... || ...
|}
|}
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.  
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.
* (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 &sigma; operations will stretch out the segment accordingly.
: We only need to take a segment which, in its right part, has a factor of 3 with a sufficiently high power, and the &sigma; operations will stretch out the segment accordingly.
Therefore we can continue the modulus table above indefinitely, which leads us to the claim:
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 of the segment directory, and once as a left side. There is a bijective mapping between the left sides and the elements of the right parts.
* (C7) '''All numbers of the form 6 * n - 2 occur exactly once''' in the right part of the segment directory, and once as a left side. There is a bijective mapping between the left sides and the elements of the right parts.
: The sequences defined by the columns in the right part all have different modulus conditions. Therefore they are all disjoint.  
: The sequences defined by the columns in the right part all have different modulus conditions. Therefore they are all disjoint.
==Forest directory==
==Forest Directory==
We construct a ''forest directory'' F which initially is a copy of the segment directory C. F lists all the small trees with two branches which are represented by the right parts in the segment directory. These trees are ''labelled'' by the left sides.  
Before we construct the Collatz tree, we first create a dynamic ''forest directory'' F. Initially, F very similiar to C - in fact, it is with a copy of the segment compressed directory. F lists all the small trees (c.f. (C5)) with two branches which are represented by the right parts of the segments. These trees are ''labelled'' by the left sides.
Then we start a ''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 segment) in F which fulfill some modularity condition (the ''source'' row in F), and we ''attach'' (identify, connect) them to their unique occurrence in the right part of F (''target'' row and column).  
===Tree attachment rules===
We operate on F as follows. Given a row i &gt; 1 (omitting the root segment) which fulfills some modularity condition (the ''source'' row), we may ''attach'' (identify, connect) it to the unique occurrence of its label in the right part of F (''target'' row and column). Afterwards, we erase row i in F.
* (C8) The attachment process does not create any new cycle (in addition to the one in the root segment).
* (C8) The attachment process does not create any new cycle (in addition to the one in the root segment).
: Let tree t1 with label n1 and right part R1 be attached to node n1 in the right part R2 of the unique tree t2 which is labelled by n2. t1 and t2 are disjoint trees, therefore the result of such a single attachment step is a tree again (t2', still labelled by n2).  
: Let tree t1 with label n1 and right part R1 be attached to node n1 in the right part R2 of the unique tree t2 which is labelled by n2. t1 and t2 are disjoint trees by (C4), therefore the result of such a single attachment step is a tree again (t2', still labelled by n2).
: A technical implementation of the process (which is impossible for infinite sets) would perhaps replace the target node by a pointer to the source tree.
 
We ''sieve'' the trees in F: Whenever we attach t1 to n1 in t2, we remove the row for n1 resp. t1 in F.  The attachment rules are shown in the following table '''(T4)''':
The following table '''(T4)''' shows where source rows must be attached to target rows and columns:
{| class="wikitable" style="text-align:left"
{| class="wikitable" style="text-align:left"
|-
|-
!Source Row i       !! First left<br>sides  !! Target<br>Row !! Target<br>Column      !! Remaining Rows                !! Fraction
!Source<br>rows i   !!First source<br>rows !! Target<br>rows||Target<br>column                    !!First<br>target rows!!New<br>pos.!! Remaining<br>rows        !! Remaining<br>Fraction
|-                    
|-                                                                                          
|i &#x2261; 3 mod 4  || 16, 40, 64, 88 ...   || ((i -  3) /  4) * 3<sup>0</sup> + 1 || 2||i &#x2261; 0, 1, 2 mod 4       ||3/4
|i &#x2261; 3 mod 4  ||3, 7, 11, 15 ...     ||3<sup>0</sup> * (i -  3) /  4 + 1|| '''2'''||1, 2, 3, 4 ...      || &lt; ||i &#x2261; 0, 1, 2 mod 4       ||3/4
|-                                                            
|-                                                                                      
|i &#x2261; 1 mod 4  || (4), 28, 52, 76 ...   ||((i -  1) /  4) * 3<sup>1</sup> + 1 || 3||i &#x2261; 0, 2, 4, 6 mod 8   ||1/2
|i &#x2261; 1 mod 4  ||(1), 5, 9, 13 ...   ||3<sup>1</sup> * (i -  1) /  4 + 1|| '''3'''||(1), 4, 7, 10 ...    || &lt;(=) ||i &#x2261; 0, 2, 4, 6 mod 8 ||1/2
|-                                                            
|-                                                                                      
|i &#x2261; 2 mod 8  || 10, 58, 106, 154 ... || ((i -  2) /  8) * 3<sup>1</sup> + 1 || 4||i &#x2261; 0, 4, 6 mod 8       ||3/8
|i &#x2261; 2 mod 8  ||2, 10, 18, 26 ...   ||3<sup>1</sup> * (i -  2) /  8 + 1|| '''4'''||1, 4, 7, 10 ...      || &lt; ||i &#x2261; 0, 4, 6 mod 8       ||3/8
|-                                                            
|-                                                                                      
|i &#x2261; 6 mod 8  || 34, 82, 130, 178 ... || ((i -  6) /  8) * 3<sup>2</sup> + 7 || 5||i &#x2261; 0, 4, 8, 12 mod 16 ||1/4
|i &#x2261; 6 mod 8  ||6, 14, 22, 30 ...   ||3<sup>2</sup> * (i -  6) /  8 + 7|| '''5'''||7, 16, 25, 34 ...    || &gt; ||i &#x2261; 0, 4, 8, 12 mod 16   ||1/4
|-                                                            
|-                                                                                      
|i &#x2261; 12 mod 16|| 70, 166, 262, 358 ... || ((i - 12) / 16) * 3<sup>2</sup> + 7 || 6||i &#x2261; 0, 4, 8 mod 16     ||3/16
|i &#x2261; 12 mod 16||12, 28, 44, 60 ...   ||3<sup>2</sup> * (i - 12) / 16 + 7|| '''6'''||7, 16, 25, 34 ...    || &lt; ||i &#x2261; 0, 4, 8 mod 16       ||3/16
|-                                                            
|-                                                                                      
|i &#x2261; 4  mod 16|| 22, 118, 214, 310 ... || ((i -  4) / 16) * 3<sup>3</sup> + 7 || 7||i &#x2261; 0, 8, 16, 24 mod 32 ||1/8
|i &#x2261; 4  mod 16||4, 20, 36, 52 ...   ||3<sup>3</sup> * (i -  4) / 16 + 7|| '''7'''||7, 34, 61, 88 ...    || &gt; ||i &#x2261; 0, 8, 16, 24 mod 32 ||1/8
|-                                                            
|-                                                                                      
|i &#x2261; 8  mod 32|| 46, 238, 430, 682 ... || ((i -  8) / 32) * 3<sup>3</sup> + 7 || 8||i &#x2261; 0, 16, 24 mod 32   ||3/32
|i &#x2261; 8  mod 32||8, 40, 72, 104 ...   ||3<sup>3</sup> * (i -  8) / 32 + 7|| '''8'''||7, 34, 61, 88 ...    || &lt; ||i &#x2261; 0, 16, 24 mod 32     ||3/32
|-                                                            
|-                                                                                    
|i &#x2261; 24 mod 32|| 142, 334 ...         || ((i - 24) / 32) * 3<sup>4</sup> + 61|| 9||i &#x2261; 0, 16, 32, 48 mod 64||1/16
|i &#x2261; 24 mod 32||24, 56, 88, 120 ... ||3<sup>4</sup> * (i - 24) / 32 + 61|| '''9'''||61, 142, 223, 304 ...|| &gt; ||i &#x2261; 0, 16, 32, 48 mod 64 ||1/16
|-                                                            
|-                                                                                    
|i &#x2261; 48 mod 64|| 286, 670 ...         || ((i - 48) / 64) * 3<sup>4</sup> + 61||10||i &#x2261; 0, 16, 32 mod 64   ||3/64
|i &#x2261; 48 mod 64||48, 112, 176, 240 ...||3<sup>4</sup> * (i - 48) / 64 + 61||'''10'''||61, 142, 223, 304 ...|| &gt; ||i &#x2261; 0, 16, 32 mod 64     ||3/64
|-                                                            
|-                                                                                    
|i &#x2261; 16 mod 64|| 94, 478 ...           || ((i - 16) / 64) * 3<sup>5</sup> + 61||11||i &#x2261; 0, 32, 64, 96 mod 128 ||1/32
|i &#x2261; 16 mod 64||16, 80, 144, 208 ... ||3<sup>5</sup> * (i - 16) / 64 + 61||'''11'''||61, 304, 547, 790 ...|| &gt; ||i &#x2261; 0, 32, 64, 96 mod 128||1/32
|-                    
|-                                                                                    
| ...                || ...                               || ... || ...                       || ...
| ...                || ...                 || ...                              ||        || ...                 || &gt; || ...                           || ...
|-                    
|-
|}
|}
It should be obvious how the next rows of this table should be filled: The residues of 2<sup>k</sup> in the first column are 3 * 2<sup>k-2</sup>, 1 * 2<sup>k-2</sup> 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 ([http://oeis.org/A191681 OEIS A191681]) mentioned above. They are repeated 4 times since the corresponding lengths "jump" by 4.
It should be obvious how the next rows of this infinite table should be filled:  
It should be noted that it does not matter in which order the single attachment steps are performed.
* The residues of 2<sup>k</sup> in the first column are 3 * 2<sup>k-2</sup>, 1 * 2<sup>k-2</sup> 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 ([http://oeis.org/A191681 OEIS A191681]) mentioned above. They are repeated 4 times since the corresponding lengths "jump" by 4.
We denote the attachment rules by the - bold - target column number.
It does not matter in which order the single attachment steps are performed.
A technical implementation of the process (which is impossible for infinite sets) would perhaps replace the target node by a pointer to the source tree.
===Reduction of T4===
We will now use the rules of T4 to combine trees in the forest directory and thus to erase rows successively. 
===Rows to be attached to higher rows===
Source rows i &#x2261; 24 mod 32, the source rows are always attached to a target row with a higher number.
Then we start a ''gedankenexperiment'' analogous to [https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel Hilbert's hotel]. We consider simultaneously all
 
 
 
We ''sieve'' the trees in F: Whenever we attach t1 to n1 in t2, we remove the row for n1 resp. t1 in F. 
===Tree connectivity===
===Tree connectivity===
* (C9) The tree of any source row with arbitrarily large left side n1 will eventually be be attached to another tree which contains n1 in its node set.
* (C9) The tree of any source row with arbitrarily large left side n1 will eventually be be attached to another tree which contains n1 in its node set.
: Similiar to the arguments for coverage of segments, 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).  
: Similiar to the arguments for coverage of segments, 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).
* (C9a) In the end, all subtrees will be attached to the root segment.
* (C9a) In the end, all subtrees will be attached to the root segment.
: Suppose there is a set U of subtrees left which are not connected to the root segment. We consider the subtree t in U  with the smallest label. We know that it should have been attached - to where? Either to the root segment, or to another tree in U. ''Is this  already a contradiction?''  
: Suppose there is a set U of subtrees left which are not connected to the root segment. We consider the subtree t in U  with the smallest label. We know that it should have been attached - to where? Either to the root segment, or to another tree in U. ''Is this  already a contradiction?''
:If not, then in both cases the number of trees is reduced by 1. We repeat the argument until there is only one subtree t left in U. The label of t is not contained in t's node set, so it must be contained in the node set of the tree already attached to the root segment, and that is the node where t must also be attached.
:If not, then in both cases the number of trees is reduced by 1. We repeat the argument until there is only one subtree t left in U. The label of t is not contained in t's node set, so it must be contained in the node set of the tree already attached to the root segment, and that is the node where t must also be attached.
: And if U is infinite? Then the two trees attached to the root segment would have a finite number of nodes. Then they have leaves which have no tree attached to them. But by T4 we could always determine the subtree which should have been attached, so we have a contradiction.
: And if U is infinite? Then the two trees attached to the root segment would have a finite number of nodes. Then they have leaves which have no tree attached to them. But by T4 we could always determine the subtree which should have been attached, so we have a contradiction.
Line 228: Line 242:
==The Collatz Tree==
==The Collatz Tree==
* (C10) The compressed tree is a subgraph of the Collatz graph.
* (C10) The compressed tree is a subgraph of the Collatz graph.
: The edges of the compressed tree carry combined operations &micro;&micro;, &delta;&micro;&micro; and &sigma; = &delta;&micro;.  
: The edges of the compressed 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 compressed tree.  
So far, numbers of the form x &#x2261; 0, 1, 2, 3, 5 mod 6 are missing from the compressed tree.


We insert intermediate nodes into the compressed tree by applying operations on the left parts of the segments as shown in the following table (T5):
We insert intermediate nodes into the compressed tree by applying operations on the left parts of the segments as shown in the following table (T5):
Line 235: Line 249:
|-
|-
! Operation            !! Condition            !! Resulting Nodes !! Remaining Nodes
! Operation            !! Condition            !! Resulting Nodes !! Remaining Nodes
|-                    
|-
|&delta;              ||                      || 2 * i - 1      || i &#x2261; 0, 2, 6, 8 mod 12
|&delta;              ||                      || 2 * i - 1      || i &#x2261; 0, 2, 6, 8 mod 12
|-                    
|-
|&micro;              ||                      || 12 * i - 4      || i &#x2261; 0, 2, 6 mod 12
|&micro;              ||                      || 12 * i - 4      || i &#x2261; 0, 2, 6 mod 12
|-                    
|-
|&delta;&micro;        || i &#x2261; 1, 2 mod 3 || 4 * i - 2      || i &#x2261; 0, 12 mod 24
|&delta;&micro;        || i &#x2261; 1, 2 mod 3 || 4 * i - 2      || i &#x2261; 0, 12 mod 24
|-
|-
Line 247: Line 261:
|-
|-
|}
|}
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 generate the sprouts (starting at multiples of 3) which are not contained in the segment 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 generate 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).  
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  be created by the same [https://github.com/gfis/fasces/blob/master/oeis/collatz/collatz_rails.pl Perl program]. In that directory, the two subpaths of a segment are shown in two lines. Only the highlighted nodes are unique.
:: A '''[http://www.teherba.org/fasces/oeis/collatz/rails.html detailed segment directory]''' can  be created by the same [https://github.com/gfis/fasces/blob/master/oeis/collatz/collatz_rails.pl Perl program]. In that directory, the two subpaths of a segment are shown in two lines. Only the highlighted nodes are unique.



Revision as of 13:00, 7 November 2018

Introduction

Collatz sequences (also called trajectories) are sequences of integer numbers > 0. For any start value > 0 the elements of the sequence are constructed with two simple rules:

  1. Even numbers are halved.
  2. Odd numbers 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 all start values. 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 Collatz sequences show 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 trivial, 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, another trivial type of 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 (m ≡ 1 mod 2)
s := ud spike -2 m ↦ (3 * m + 1) / 2) m ≡ 1 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.

Motivation: Patterns in sequences with the same length

A closer look at the Collatz sequences shows a lot of pairs of adjacent start values which have the same sequence length, for example (from OEIS A070165):

142/104: 142 d  71 u 214 d 107 u 322 d 161 u 484 d  242 d 121 u 364 ] 182, 91, ... 4, 2, 1
143/104: 143 u 430 d 215 u 646 d 323 u 970 d 485 u 1456 d 728 d 364 ] 182, 91, ... 4, 2, 1
           +1  *6+4    +1  *6+4    +1  *6+4    +1   *6+4  *6+2    +0    +0 ...

The third line tells how the second line could be computed from the first. Walking from right to left, the step pattern is:

δ µ µ δ µ δ µ δ µ
µ µ δ µ δ µ δ µ δ

The alternating pattern of operations can be continued to the left with 4 additional pairs of steps:

 q? u [ 62 d  31 u  94 d  47 u 142 d ...
126 d [ 63 u 190 d  95 u 286 d 143 u ...
        +1  *6+4    +1  *6+4    +1

The pattern stops here since there is no number q such that q * 3 + 1 = 62.

Segment Construction

These patterns lead us to the construction of 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.

Informally, and in the two examples above, we consider the terms betweeen the square brackets. For the moment, we only take those which are which are ≡ 4 mod 6 (for "compressed" segments, below there are also "detailed" segments where we take all). We start at the right and with the lower line, and we interleave the terms ≡ 4 mod 6 of the two lines to get a segment.

The columns in one row i of the array 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 side of the segment (or of the whole directory), while the columns C[i,j], j > 1 will be the right part. The first few lines of the segment directory are the following:

1 2 3 4 5 6 7 8 9 10 11 ... 2*j 2*j+1
  i   6*i‑2 µµ δµµ µµσ δµµσ µµσσ δµµσσ µµσ3 δµµσ3 µµσ4 δµµσ4 ... µµσj-1 δµµσj-1
  1    4  16  4  10 
  2   10  40 
  3   16  64 
  4   22  88  28  58 
  5   28  112 
  6   34  136 
  7   40  160  52  106  34  70  22  46 

There is a more elaborated segment directory with 5000 rows.

Properties of the segment directory

We make a number of claims for 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.
  • (C3) All nodes in the right part of a segment have the form 6 * (3n * 2m * f) - 2 with the same "3-2-free" factor f.
This follows from the operations for columns C[i,1..3], and from the fact that the σ operation maintains this property.
  • (C4) All nodes in the right part of a particular segment are
    • different among themselves, and
    • different from the left side of that segment (except for the first segment for the root 4).
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 (except for the first segment for the root 4).

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 of the segment directory, and once as a left side. There is a bijective mapping between the left sides and the elements of the right parts.
The sequences defined by the columns in the right part all have different modulus conditions. Therefore they are all disjoint.

Forest Directory

Before we construct the Collatz tree, we first create a dynamic forest directory F. Initially, F very similiar to C - in fact, it is with a copy of the segment compressed directory. F lists all the small trees (c.f. (C5)) with two branches which are represented by the right parts of the segments. These trees are labelled by the left sides.

Tree attachment rules

We operate on F as follows. Given a row i > 1 (omitting the root segment) which fulfills some modularity condition (the source row), we may attach (identify, connect) it to the unique occurrence of its label in the right part of F (target row and column). Afterwards, we erase row i in F.

  • (C8) The attachment process does not create any new cycle (in addition to the one in the root segment).
Let tree t1 with label n1 and right part R1 be attached to node n1 in the right part R2 of the unique tree t2 which is labelled by n2. t1 and t2 are disjoint trees by (C4), therefore the result of such a single attachment step is a tree again (t2', still labelled by n2).

The following table (T4) shows where source rows must be attached to target rows and columns:

Source
rows i
First source
rows
Target
rows
Target
column
First
target rows
New
pos.
Remaining
rows
Remaining
Fraction
i ≡ 3 mod 4 3, 7, 11, 15 ... 30 * (i - 3) / 4 + 1 2 1, 2, 3, 4 ... < i ≡ 0, 1, 2 mod 4 3/4
i ≡ 1 mod 4 (1), 5, 9, 13 ... 31 * (i - 1) / 4 + 1 3 (1), 4, 7, 10 ... <(=) i ≡ 0, 2, 4, 6 mod 8 1/2
i ≡ 2 mod 8 2, 10, 18, 26 ... 31 * (i - 2) / 8 + 1 4 1, 4, 7, 10 ... < i ≡ 0, 4, 6 mod 8 3/8
i ≡ 6 mod 8 6, 14, 22, 30 ... 32 * (i - 6) / 8 + 7 5 7, 16, 25, 34 ... > i ≡ 0, 4, 8, 12 mod 16 1/4
i ≡ 12 mod 16 12, 28, 44, 60 ... 32 * (i - 12) / 16 + 7 6 7, 16, 25, 34 ... < i ≡ 0, 4, 8 mod 16 3/16
i ≡ 4 mod 16 4, 20, 36, 52 ... 33 * (i - 4) / 16 + 7 7 7, 34, 61, 88 ... > i ≡ 0, 8, 16, 24 mod 32 1/8
i ≡ 8 mod 32 8, 40, 72, 104 ... 33 * (i - 8) / 32 + 7 8 7, 34, 61, 88 ... < i ≡ 0, 16, 24 mod 32 3/32
i ≡ 24 mod 32 24, 56, 88, 120 ... 34 * (i - 24) / 32 + 61 9 61, 142, 223, 304 ... > i ≡ 0, 16, 32, 48 mod 64 1/16
i ≡ 48 mod 64 48, 112, 176, 240 ... 34 * (i - 48) / 64 + 61 10 61, 142, 223, 304 ... > i ≡ 0, 16, 32 mod 64 3/64
i ≡ 16 mod 64 16, 80, 144, 208 ... 35 * (i - 16) / 64 + 61 11 61, 304, 547, 790 ... > i ≡ 0, 32, 64, 96 mod 128 1/32
... ... ... ... > ... ...

It should be obvious how the next rows of this infinite table should be filled:

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

We denote the attachment rules by the - bold - target column number. It does not matter in which order the single attachment steps are performed. A technical implementation of the process (which is impossible for infinite sets) would perhaps replace the target node by a pointer to the source tree.

Reduction of T4

We will now use the rules of T4 to combine trees in the forest directory and thus to erase rows successively.

Rows to be attached to higher rows

Source rows i ≡ 24 mod 32, the source rows are always attached to a target row with a higher number. Then we start a gedankenexperiment analogous to Hilbert's hotel. We consider simultaneously all


We sieve the trees in F: Whenever we attach t1 to n1 in t2, we remove the row for n1 resp. t1 in F.

Tree connectivity

  • (C9) The tree of any source row with arbitrarily large left side n1 will eventually be be attached to another tree which contains n1 in its node set.
Similiar to the arguments for coverage of segments, 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).
  • (C9a) In the end, all subtrees will be attached to the root segment.
Suppose there is a set U of subtrees left which are not connected to the root segment. We consider the subtree t in U with the smallest label. We know that it should have been attached - to where? Either to the root segment, or to another tree in U. Is this already a contradiction?
If not, then in both cases the number of trees is reduced by 1. We repeat the argument until there is only one subtree t left in U. The label of t is not contained in t's node set, so it must be contained in the node set of the tree already attached to the root segment, and that is the node where t must also be attached.
And if U is infinite? Then the two trees attached to the root segment would have a finite number of nodes. Then they have leaves which have no tree attached to them. But by T4 we could always determine the subtree which should have been attached, so we have a contradiction.

We denote the final tree resulting from the sieving process by compressed tree.

The Collatz Tree

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

So far, numbers of the form x ≡ 0, 1, 2, 3, 5 mod 6 are missing from the compressed tree.

We insert intermediate nodes into the compressed tree by applying operations on the left parts of the segments 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 generate 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 detailed segment directory can be created by the same Perl program. In that directory, the two subpaths of a segment are shown in two lines. Only the highlighted nodes are unique.
  • (C11) The connectivity of the compressed tree remains unaffected by the insertions.
  • (C12) With the insertions of T5, the compressed tree covers the whole Collatz graph.
  • (C13) The Collatz graph is a tree (except for the trivial cycle 4-2-1).