Collatz Streetmap: Difference between revisions

From tehowiki
Jump to navigation Jump to search
imported>Gfis
completeness of S
imported>Gfis
export to 3x+1 Problem
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
==Introduction==
==Introduction==
When all Collatz sequences are read backwards, they form a graph starting with 1, 2 ..., hopefully without cycles (except for 1,2,4,1,2,4 ...). At each node n in the graph, the path starting at the root (4) and with the last node n can in principle be continued to 2 new nodes by a  
Collatz sequences are sequences of non-negative integer numbers with a simple construction rule: even elements a 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 [https://en.wikipedia.org/wiki/Collatz_conjecture english Wikipedia] states:
* "m"-step: n * 2 (which is always possible), or a
: 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.
* "d"-step: (n - 1) / 3 (which is possible only if n ≡ 1 mod 3).
 
When n mod 3 = 0, the path will continue with m-steps only, since the duplication maintains the divisibility by 3.
When we speak of ''numbers'' in this article, we normally mean natural integer numbers > 0. The zero is sometimes mentioned explicetely.
===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 9: Line 9:
* Gottfried Helms: ''[http://go.helms-net.de/math/collatz/aboutloop/collatzgraphs.htm The Collatz-Problem]''. A view into some 3x+1-trees and a new fractal graphic representation. Univ. Kassel.
* Gottfried Helms: ''[http://go.helms-net.de/math/collatz/aboutloop/collatzgraphs.htm The Collatz-Problem]''. A view into some 3x+1-trees and a new fractal graphic representation. Univ. Kassel.
* Klaus Brennecke: ''[https://de.wikibooks.org/wiki/Collatzfolgen_und_Schachbrett Collatzfolgen und Schachbrett]'', on Wikibooks
* Klaus Brennecke: ''[https://de.wikibooks.org/wiki/Collatzfolgen_und_Schachbrett Collatzfolgen und Schachbrett]'', on Wikibooks
===Collatz graph===
When all Collatz sequences are read backwards, they form the '''Collatz graph''' starting with 1, 2, 4, 8 ... . At each node n > 4 in the graph, the path from the root (4) can be continued
* always to n * 2, and
* sometimes also to (n - 1) / 3. 
When n ≡ 0 mod 3, the path will continue with duplications only, since these maintain the divisibility by 3.
The 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 cylces.
Straightforward visualizations of the Collatz graph show now obvious structure. The sequences for the first dozen of start values seem to be rather harmless, but the sequence for 27 suddenly has 112 elements.
Read on in [[OEIS/3x+1 Problem|3x+1 Problem]].
This article proposes
* a rather regular structure for short portions of the Collatz graph, and
* a corresponding algorithm which
** combines these portions and
** uses them to walk the graph in a systematic, predictable way
* such that the reader could finally be convinced that the algorithm enumerates all numbers.
===Steps===
In order to walk back and forth in the Collatz graph, we will write
a ''step'' b
to denote a move from node (element) a to b. The following table lists such steps:
{| class="wikitable" style="text-align:center"
!Name !! Mnemonic !! Direction !! Operation        !! Condition          !! Remark
|-
| h  || halve    ||  -> root  ||  b = a / 2      || a ≡ 0 mod 2  || next in sequence
|-
| t  || triple  ||  -> root  ||  b = 3 * a + 1  || true                || next in sequence
|-
| m  || multiply ||  root ->  ||  b = a * 2      || true                || inverse of h
|-
| d  || divide  ||  root ->  ||  b = (a - 1) / 3 || a ≡ 1 mod 3  || inverse of t
|}
Steps may be combined, for example
a dm b : b = ((a - 1) / 3) * 2
A starting number and a sequence of step names defines a unique, directed path in the Collatz graph.
=== Trivial paths===
There are two types of paths whose descriptions are very simple:
(n = 2<sup>k</sup>) hhhh ... h 8 h 4 h 2 h 1  - powers of 2
(n &#x2261; 0 mod 3) mmm ... m (n * 2<sup>k</sup>) ... - multiples of 3
==Collatz streets==
===Motivation: Patterns in sequences with same length===
===Motivation: Patterns in sequences with same length===
When Collatz sequences are investigated, there are a lot of pairs of adjacent start values with the same sequence length, and with a characteristical neighbourhood of every other value, for example (from [https://oeis.org/A070165 OEIS A070165]):
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 [https://oeis.org/A070165 OEIS A070165]):
  142/104: [142 m 71 d 214 m 107 d 322 m 161 d 484 m 242 m 121 d | 364, 182, 91, ... 10, 5, 16, 8, 4, 2, 1]
  142/104: [142 h 71 t 214 h 107 t 322 h 161 t 484 h 242 h 121 t 364 | 182, 91, ... 10, 5, 16, 8, 4, 2, 1]
             +1  *6+4    +1  *6+4    +1  *6+4    +1  *6+4  *6+2     =   ...
143/104: [143 t 430 h 215 t 646 h 323 t 970 h 485 t 1456 h 728 h 364 | 182, 91, ... 10, 5, 16, 8, 4, 2, 1]
  143/104: [143 d 430 m 215 d 646 m 323 d 970 m 485 d 1456 m 728 m | 364, 182, 91, ... 10, 5, 16, 8, 4, 2, 1]
             +1  *6+4    +1  *6+4    +1  *6+4    +1  *6+4  *6+2    +0    +0 ...
==Collatz roads==
The third line tells how the second line can be computed from the first.
We define a "road" (with 2 parallel "lanes") as a sequence of pairs of elements (in 2 Collatz sequences with adjacent start values, read from right to left). A road is constructed by taking some n (364 in the example, the last common element of the 2 sequences) with n &#x2261; 4 mod 6, and by applying the steps
Walking from right to left, the step pattern is:
d m m d m d m d ...
d m m d m d m d m
m m d m d m d m ...
  m m d m d m d m d
in alternating sequence, until one of the elements in the pairs becomes divisible by 3. The construction yields one road with an upper lane (left elements of the pairs) and a lower lane (right elements), for example:  
or, in linearized form:
  ''364'': (121,728), (242,''1456''), (''484'',485), (161,''970''), (''322'',323), (107,''646''), (''214'',215), (71,''430''), (''142'',143) ...
d/m m/m m/d d/m m/d d/m m/d d/m m/d ...  
The elements which are &#x2261; 4 mod 6 are emphasized. The construction continues until 63 &#x2261; 0 mod 3:
Informally, a '''street''' is a parallel arrangement of 2 paths stemming from 2 sequences which have a common tail. A street starts with an element &#x2261; 4 mod 6 (364 in the example, before the bar), it proceeds to the left with a d/m and a m/m pair of steps, and then it extends to the left as long as a characteristical, alternating sequence of pairs of steps m/d - d/m - m/d - d/m ... can be continued. In the example, the street can be continued with 4 additional pairs of steps:
... (47,''286''), (''94'',95), (31,''190''), (62,63).
  q t | 62 h 31 t  94 h  47 t 142 h ...
===Roads table R===
126 h | 63 t 190 h  95 t 286 h 143 t ...
For better handling (e.g. in Excel), the roads for all starting values 4, 10, 16, 22 ... n*6+4 are listed as rows of a table. The columns in the rows are numbered r<sub>0</sub>, r<sub>1</sub>, r<sub>2</sub> ...
        +1  *6+4   +1  *6+4    +1 
The construction stops since there is no number q such that q * 3 + 1 = 62.  
===Street directory S===
Though the graph usually has a "chaotic" appearance, the streets exhibit quite some amount of regular structure. This can be seen if we list the paired elements of the streets for all possible starting values 4, 10, 16, 22 ... 6n-2 for n = 1, 2 ... as rows of a table, in reversed direction (extending to the right). The elements &#x2261; 4 mod 6 are highlighted:
<table>
<table>
<tr align="right">
<tr align="right">
<td class="arl">r<sub>0</sub></td>
<td class="arl">c<sub>1</sub></td>
<td class="arl">r<sub>1</sub></td>
<td class="arl">c<sub>2</sub></td>
<td class="arl">r<sub>2</sub></td>
<td class="arl">c<sub>3</sub></td>
<td class="arl">r<sub>3</sub></td>
<td class="arl">c<sub>4</sub></td>
<td class="arl">r<sub>4</sub></td>
<td class="arl">c<sub>5</sub></td>
<td class="arl">r<sub>5</sub></td>
<td class="arl">c<sub>6</sub></td>
<td class="arl">r<sub>6</sub></td>
<td class="arl">c<sub>7</sub></td>
<td class="arl">r<sub>7</sub></td>
<td class="arl">c<sub>8</sub></td>
<td class="arl">r<sub>8</sub></td>
<td class="arl">c<sub>9</sub></td>
<td class="arl">r<sub>9</sub></td>
<td class="arl">c<sub>10</sub></td>
<td class="arl">r<sub>10</sub></td>
<td class="arl">c<sub>11</sub></td>
<td class="arl">r<sub>11</sub></td>
<td class="arl">c<sub>12</sub></td>
<td class="arl">r<sub>12</sub></td>
<td class="arl">c<sub>13</sub></td>
<td class="arl">r<sub>13</sub></td>
<td class="arl">c<sub>14</sub></td>
<td class="arl">r<sub>14</sub></td>
<td class="arl">c<sub>15</sub></td>
<td class="arl">r<sub>15</sub></td>
<td class="arl">...</td>
<td class="arl">...</td>
</tr>
</tr>
<tr align="right">
<tr align="right"><td><strong>4 </strong></td><td class="d1">1</td><td class="d2">8</td><td class="d2">2</td><td><strong>16</strong></td><td><strong>4</strong></td><td class="d5">5</td><td class="d1">1</td><td><strong>10</strong></td><td class="d2">2</td><td class="d3">3</td></tr>
<td class="arr">start</td>
<tr align="right"><td><strong>10</strong></td><td class="d3">3</td><td class="d2">20</td><td class="d0">6</td><td><strong>40</strong></td><td class="d0">12</td><td class="d1">13</td></tr>
<td class="arr">len</td>
<tr align="right"><td><strong>16</strong></td><td class="d5">5</td><td class="d2">32</td><td><strong>10</strong></td><td><strong>64</strong></td><td class="d2">20</td><td class="d3">21</td></tr>
<td class="arr"><strong>d</strong>r<sub>0</sub></td>
<tr align="right"><td><strong>22</strong></td><td class="d1">7</td><td class="d2">44</td><td class="d2">14</td><td><strong>88</strong></td><td><strong>28</strong></td><td class="d5">29</td><td class="d3">9</td><td><strong>58</strong></td></tr>
<td class="arl"><strong>m</strong>r<sub>0</sub></td>
<tr align="right"><td><strong>28</strong></td><td class="d3">9</td><td class="d2">56</td><td class="d0">18</td><td><strong>112</strong></td><td class="d0">36</td><td class="d1">37</td></tr>
<td class="arr"><strong>m</strong>r<sub>2</sub></td>
<tr align="right"><td><strong>34</strong></td><td class="d5">11</td><td class="d2">68</td><td><strong>22</strong></td><td><strong>136</strong></td><td class="d2">44</td><td class="d3">45</td></tr>
<td class="arl"><strong>m</strong>r<sub>3</sub></td>
<tr align="right"><td><strong>40</strong></td><td class="d1">13</td><td class="d2">80</td><td class="d2">26</td><td><strong>160</strong></td><td><strong>52</strong></td><td class="d5">53</td><td class="d5">17</td><td><strong>106</strong></td><td><strong>34</strong></td><td class="d5">35</td><td class="d5">11</td><td><strong>70</strong></td><td><strong>22</strong></td><td class="d5">23</td><td class="d1">7</td><td><strong>46</strong></td><td class="d2">14</td><td class="d3">15</td></tr>
<td class="arr"><strong>m</strong>r<sub>4</sub></td>
<tr align="right"><td><strong>46</strong></td><td class="d3">15</td><td class="d2">92</td><td class="d0">30</td><td><strong>184</strong></td><td class="d0">60</td><td class="d1">61</td></tr>
<td class="arl"><strong>d</strong>r<sub>5</sub></td>
<tr align="right"><td><strong>52</strong></td><td class="d5">17</td><td class="d2">104</td><td><strong>34</strong></td><td><strong>208</strong></td><td class="d2">68</td><td class="d3">69</td></tr>
<td class="arr"><strong>d</strong>r<sub>6</sub></td>
<tr align="right"><td><strong>58</strong></td><td class="d1">19</td><td class="d2">116</td><td class="d2">38</td><td><strong>232</strong></td><td><strong>76</strong></td><td class="d5">77</td><td class="d1">25</td><td><strong>154</strong></td><td class="d2">50</td><td class="d3">51</td></tr>
<td class="arl"><strong>m</strong>r<sub>7</sub></td>
<tr align="right"><td><strong>64</strong></td><td class="d3">21</td><td class="d2">128</td><td class="d0">42</td><td><strong>256</strong></td><td class="d0">84</td><td class="d1">85</td></tr>
<td class="arr"><strong>m</strong>r<sub>8</sub></td>
<tr align="right"><td><strong>70</strong></td><td class="d5">23</td><td class="d2">140</td><td><strong>46</strong></td><td><strong>280</strong></td><td class="d2">92</td><td class="d3">93</td></tr>
<td class="arl"><strong>d</strong>r<sub>9</sub></td>
<tr align="right"><td><strong>76</strong></td><td class="d1">25</td><td class="d2">152</td><td class="d2">50</td><td><strong>304</strong></td><td><strong>100</strong></td><td class="d5">101</td><td class="d3">33</td><td><strong>202</strong></td></tr>
<td class="arr"><strong>d</strong>r<sub>10</sub></td>
<td class="arl"><strong>m</strong>r<sub>11</sub></td>
<td class="arr"><strong>m</strong>r<sub>12</sub></td>
<td class="arl"><strong>d</strong>r<sub>13</sub></td>
<td class="arr">...</td>
</tr>
<tr align="right">
<td class="arr">&#x394;6</td>
<td class="arr"></td>
<td class="arr">&#x394;2</td>
<td class="arr">&#x394;12</td>
<td class="arr">&#x394;4</td>
<td class="arr">&#x394;24</td>
<td class="arr">&#x394;8</td>
<td class="arr">&#x394;8</td>
<td class="arr">3&#x394;8</td>
<td class="arr">3&#x394;48</td>
<td class="arr">3&#x394;16</td>
<td class="arr">3&#x394;16</td>
<td class="arr">9&#x394;16</td>
<td class="arr">9&#x394;96</td>
<td class="arr">9&#x394;32</td>
<td class="arr">9&#x394;32</td>
<td class="arr">...</td>
</tr>
<tr align="right"><td><strong>4</strong></td><td class="arr">5</td><td class="d1">1</td><td class="d2">8</td><td class="d2">2</td><td><strong>16</strong></td><td><strong>4</strong></td><td class="d5">5</td><td class="d1">1</td><td><strong>10</strong></td><td class="d2">2</td><td class="d3">3</td></tr>
<tr align="right"><td><strong>10</strong></td><td class="arr">3</td><td class="d3">3</td><td class="d2">20</td><td class="d0">6</td><td><strong>40</strong></td><td class="d0">12</td><td class="d1">13</td></tr>
<tr align="right"><td><strong>16</strong></td><td class="arr">3</td><td class="d5">5</td><td class="d2">32</td><td><strong>10</strong></td><td><strong>64</strong></td><td class="d2">20</td><td class="d3">21</td></tr>
<tr align="right"><td><strong>22</strong></td><td class="arr">4</td><td class="d1">7</td><td class="d2">44</td><td class="d2">14</td><td><strong>88</strong></td><td><strong>28</strong></td><td class="d5">29</td><td class="d3">9</td><td><strong>58</strong></td></tr>
<tr align="right"><td><strong>28</strong></td><td class="arr">3</td><td class="d3">9</td><td class="d2">56</td><td class="d0">18</td><td><strong>112</strong></td><td class="d0">36</td><td class="d1">37</td></tr>
<tr align="right"><td><strong>34</strong></td><td class="arr">3</td><td class="d5">11</td><td class="d2">68</td><td><strong>22</strong></td><td><strong>136</strong></td><td class="d2">44</td><td class="d3">45</td></tr>
<tr align="right"><td><strong>40</strong></td><td class="arr">9</td><td class="d1">13</td><td class="d2">80</td><td class="d2">26</td><td><strong>160</strong></td><td><strong>52</strong></td><td class="d5">53</td><td class="d5">17</td><td><strong>106</strong></td><td><strong>34</strong></td><td class="d5">35</td><td class="d5">11</td><td><strong>70</strong></td><td><strong>22</strong></td><td class="d5">23</td><td class="d1">7</td><td><strong>46</strong></td><td class="d2">14</td><td class="d3">15</td></tr>
<tr align="right"><td><strong>46</strong></td><td class="arr">3</td><td class="d3">15</td><td class="d2">92</td><td class="d0">30</td><td><strong>184</strong></td><td class="d0">60</td><td class="d1">61</td></tr>
<tr align="right"><td><strong>52</strong></td><td class="arr">3</td><td class="d5">17</td><td class="d2">104</td><td><strong>34</strong></td><td><strong>208</strong></td><td class="d2">68</td><td class="d3">69</td></tr>
<tr align="right"><td><strong>58</strong></td><td class="arr">5</td><td class="d1">19</td><td class="d2">116</td><td class="d2">38</td><td><strong>232</strong></td><td><strong>76</strong></td><td class="d5">77</td><td class="d1">25</td><td><strong>154</strong></td><td class="d2">50</td><td class="d3">51</td></tr>
<tr align="right"><td><strong>64</strong></td><td class="arr">3</td><td class="d3">21</td><td class="d2">128</td><td class="d0">42</td><td><strong>256</strong></td><td class="d0">84</td><td class="d1">85</td></tr>
<tr align="right"><td><strong>70</strong></td><td class="arr">3</td><td class="d5">23</td><td class="d2">140</td><td><strong>46</strong></td><td><strong>280</strong></td><td class="d2">92</td><td class="d3">93</td></tr>
<tr align="right"><td><strong>76</strong></td><td class="arr">4</td><td class="d1">25</td><td class="d2">152</td><td class="d2">50</td><td><strong>304</strong></td><td><strong>100</strong></td><td class="d5">101</td><td class="d3">33</td><td><strong>202</strong></td></tr>
</table>
</table>
There is a more '''[http://www.teherba.org/fasces/oeis/collatz/roads.html elaborated example]''' for elements &lt;= 143248. The zoom factor of the web browser may be reduced (with Ctrl "-", to 25 % for example) such that the structure of the lengths of roads can be seen.
There is a more '''[http://www.teherba.org/fasces/oeis/collatz/roads.html elaborated example]''' for elements &lt;= 143248.  
===Relation to the Collatz graph===
: When this file is displayed in a browser, the zoom factor may be reduced (with Ctrl "-", to 25 % for example) such that the structure of the lengths of streets can be seen.
The Collatz graph is the union of all possible Collatz sequences, read backwards. Apart from the initial cycle 1-2-4-1 it should be a tree, and it should contain all positive numbers.  
====Street construction rules====
The following table shows the rules for the construction of the first 9 columns <nowiki>S[n,1..9]</nowiki> of row n (n = 1, 2, 3 ...) in the street directory:
{| class="wikitable" style="text-align:left"                                                   
|-     
!Column!! Steps !! Expression || Formula                !! Condition            !! Coverage
|-                                                                                                                                   
| 1||      ||      || 6n-2                              ||                      || 4,10,16,22 mod 24
|-
| 2|| d    || (6n-2-1)/3 || 2n-1                        ||                      || all odd numbers
|-                                                                           
| 3|| m    || (6n-2)*2 || 12n-4                         ||                      || 8,20 mod 24
|-                                                                           
| 4|| dm  || ((6n-2-1)/3)*2 || 4n-2                    ||                      || 2,6,10,14,18,22 mod 24
|-                                                                           
| 5|| mm  || (6n-2)*2*2 || 24n-8                      ||                      || 16 mod 24
|-                                                                               
| 6|| dmm  || ((6n-2-1)/3)*2*2 || 8n-4                  ||                      || 4,12,20 mod 24
|-                                                                               
| 7|| mmd  || ((6n-2)*2*2-1)/3 || 8n-3                  ||                      || 5,13,21 mod 24
|-
| 8|| dmmd || ((6n-2-1)/3)*2*2-1)/3 || (8n-5)/3        || n &#x2261; 1 mod 3  || (1,9,17,25 ...)
|-
| 9|| mmdm || ((6n-2)*2*2-1)/3)*2  || 16n-6            || n &#x2261; 1 mod 3  || (10,58,106,154, ...)
|}
The first 6 columns of the table cover the odd numbers and all numbers &#x2261; 2,4,6,8,10,12,16,18,20,22 mod 24.  


Each road contains 2 short paths in the Collatz graph, the root is left of the starting value of the road, and both proceed "upwards" in the tree. In contrast to the usual "chaotic" appearance of the Collatz graph, there is an amount of obvious structure in the road construction.
It is ''not shown'' so far that all multiples of 24 are contained in the table.
====Road lengths====
<!-- ???
* The lengths r<sub>1</sub> of the roads seem to be finite. The highlighted pairs of numbers &#x2261; 4 mod 6 are decreasing to the end of the road.
All odd multiples of 3 are contained in column 2. All multiples of 24 can be reached by duplicating them 3 times (3 m-steps).
* The lengths show a repeating pattern for the start values mod 54. The fixed lengths 3, 4, 5 can probably be explained from the road construction rule.
-->
====Highlighted numbers====
The numbers of the form 6p-2 were highlighted in the example above. They have the special property that, when p &gt; 0 and p &#x2261; 0 mod 3, a dm-step yields a number of the same form, but with one factor 3 in p replaced by 2:
6(3q)-2 dm ((6(3q)-2)-1)/3*2 = (6q-1)*2 = 6(2q)-2
This implies that a dm-step decreases any number by about one third.
====Street lengths &gt; 7====  
* Columns 4(k+1)+1 result by dm-steps from columns 4k+1 for k=1,2,... (and so do columns 4(k+1)+2 result from columns 4k+2). Sequences of dm-steps decrease the numbers. Therefore the lengths of all streets are finite.
* Column 5 is 24n-8, and the lengths depend on the power of 3 contained in that n.
<!--
* The street lengths show a repeating pattern for the start values mod 54. The fixed lengths 3, 4, 5 can probably be explained from the street construction rule.
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
| 4 mod 54
| 4 mod 54
Line 125: Line 163:
| 3
| 3
|}
|}
* At the starting values 4, 40, 364, 3280, 29524 ([http://oeis.org/A191681 OEIS A191681]) the road lengths n<sub>i</sub> have high values 5, 9, 13, 17, 21 which did not occur before. Those starting values are (9<sup>n+1</sup> - 1) / 2, or 4 * Sum(9<sup>i</sup>, i=0..n).
-->
* The pattern of increasing and decreasing lengths is replicated when subsets of the rows (mod 9, 27, 81 ...) are regarded.
* At the starting values 4, 40, 364, 3280, 29524 ([http://oeis.org/A191681 OEIS A191681]) the street lengths have high values 5, 9, 13, 17, 21 which did not occur before. Those starting values are (9<sup>n+1</sup> - 1) / 2, or 4 * Sum(9<sup>i</sup>, i=0..n).
====Coverage====
====Coverage====
The elements of the roads are strongly interconnected, and the table "obviously" shows all positive integers which are not multiples of 24:
The elements of the streets are strongly interconnected, and the table "obviously" shows all positive integers which are not multiples of 24:
{| class="wikitable"
{| class="wikitable"
| r<sub>0</sub> &#x2261; 4 mod 6
| r<sub>1</sub> &#x2261; 4 mod 6
| style="text-align:right" | &#x2261; 4,10,16,22 mod 24
| style="text-align:right" | &#x2261; 4,10,16,22 mod 24
|-
| r<sub>2</sub> &#x2261; 1 mod 2
| all odd numbers
|-
|-
| r<sub>3</sub> &#x2261; 8 mod 12
| r<sub>3</sub> &#x2261; 8 mod 12
Line 144: Line 185:
| r<sub>6</sub> &#x2261; 4 mod 8
| r<sub>6</sub> &#x2261; 4 mod 8
| style="text-align:right" | &#x2261; 4,12,20 mod 24
| style="text-align:right" | &#x2261; 4,12,20 mod 24
|-
| r<sub>2</sub> &#x2261; 1 mod 2
| all odd numbers
|}
|}
All odd multiples of 3 are contained in column r<sub>2</sub>. All multiples of 24 can be reached by duplicating them 3 times (3 m-steps).
 


So if we can show that we reach all start values &#x2261; 4 mod 6, we have a proof that all positive integers are reached.
So if we can show that we reach all start values &#x2261; 4 mod 6, we have a proof that all positive integers are reached.


Starting with 4, it seems possible that a continuous expansion of all numbers &#x2261; 4 mod 6 into roads would finally yield all roads up to some start value. Experiments show that there are limits for the numbers involved. Roads above the ''clamp'' value are not necessary in order to obtain all roads below and including the ''start'' value:
Starting with 4, it seems possible that a continuous expansion of all numbers &#x2261; 4 mod 6 into streets would finally yield all streets up to some start value. Experiments show that there are limits for the numbers involved. Streets above the ''clamp'' value are not necessary in order to obtain all streets below and including the ''start'' value:
{| class="wikitable"
{| class="wikitable"
! start value
! start value
Line 166: Line 204:
|}
|}
==Subset table S==
==Subset table S==
We may build derived table from the table of roads. We take columns r<sub>0</sub> and r<sub>5</sub> ff., and therein we keep the highlighted entries (those which are &#x2261; 4 mod 6) only, add 2 to them and divide them by 6. The resulting subset table S starts as follows:
We may build derived table from the table of streets. We take columns r<sub>0</sub> and r<sub>5</sub> ff., and therein we keep the highlighted entries (those which are &#x2261; 4 mod 6) only, add 2 to them and divide them by 6. The resulting subset table S starts as follows:
  s0  s1  s2  s3  s4  s5  s6  s7  s8  ...
  s0  s1  s2  s3  s4  s5  s6  s7  s8  ...
   n  len   
   n  len   
Line 186: Line 224:
  16  5  63  21  42  14  28
  16  5  63  21  42  14  28
  ...
  ...
This table can be described by simple rules which are hopefully provable from the construction rule for the roads:  
This table can be described by simple rules which are hopefully provable from the construction rule for the streets:  
* s<sub>2</sub> is always s<sub>0</sub> * 4 - 1.  
* s<sub>2</sub> is always s<sub>0</sub> * 4 - 1.  
* When s<sub>2</sub> &#x2261; 0 mod 3, the following columns s<sub>3</sub>, s<sub>4</sub> ... are obtained by an alternating sequence of steps  
* When s<sub>2</sub> &#x2261; 0 mod 3, the following columns s<sub>3</sub>, s<sub>4</sub> ... are obtained by an alternating sequence of steps  
Line 226: Line 264:
| style="text-align:right" | 16, 80, ...
| style="text-align:right" | 16, 80, ...
|}
|}
This shows that the columns s<sub>4</sub> ... s<sub>7</sub> contain all numbers &#x2261; 2,4,6,10,12,14 mod 16, but that &#x2261 0,8 mod 16 are missing so far. The ones &#x2261 8 mod 16  show up in s<sub>8</sub> resp. s<sub>9</sub>, but multiples of 16 would be missing then, etc.
This shows that the columns s<sub>4</sub> ... s<sub>7</sub> contain all numbers &#x2261; 2,4,6,10,12,14 mod 16, but those &#x2261; 0,8 mod 16 are missing so far. The ones &#x2261; 8 mod 16  show up in s<sub>8</sub> resp. s<sub>9</sub>, half of the multiples of 16 are in s<sub>10</sub> resp. s<sub>11</sub> but &#x2261; 0,32 mod 64 are missing, etc.
 
Since s<sub>2</sub> contains arbitray high powers of 3, S has rows of arbitrary length, and for the missing multiples of powers of 2 the exponents can be driven above all limits.
: Thus S contains all positive integers.
===Can S be generated starting at 1?===
===Can S be generated starting at 1?===
We ask for an iterative process which starts with the row of S for index 1:
We ask for an iterative process which starts with the row of S for index 1:

Latest revision as of 19:31, 3 September 2018

Introduction

Collatz sequences are sequences of non-negative integer numbers with a simple construction rule: even elements a 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.

When we speak of numbers in this article, we normally mean natural integer numbers > 0. The zero is sometimes mentioned explicetely.

References

Collatz graph

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

  • always to n * 2, and
  • sometimes also to (n - 1) / 3.

When n ≡ 0 mod 3, the path will continue with duplications only, since these maintain the divisibility by 3.

The 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 cylces.

Straightforward visualizations of the Collatz graph show now obvious structure. The sequences for the first dozen of start values seem to be rather harmless, but the sequence for 27 suddenly has 112 elements.

Read on in 3x+1 Problem.

This article proposes

  • a rather regular structure for short portions of the Collatz graph, and
  • a corresponding algorithm which
    • combines these portions and
    • uses them to walk the graph in a systematic, predictable way
  • such that the reader could finally be convinced that the algorithm enumerates all numbers.

Steps

In order to walk back and forth in the Collatz graph, we will write

a step b

to denote a move from node (element) a to b. The following table lists such steps:

Name Mnemonic Direction Operation Condition Remark
h halve -> root b = a / 2 a ≡ 0 mod 2 next in sequence
t triple -> root b = 3 * a + 1 true next in sequence
m multiply root -> b = a * 2 true inverse of h
d divide root -> b = (a - 1) / 3 a ≡ 1 mod 3 inverse of t

Steps may be combined, for example

a dm b : b = ((a - 1) / 3) * 2 

A starting number and a sequence of step names defines a unique, directed path in the Collatz graph.

Trivial paths

There are two types of paths whose descriptions are very simple:

(n = 2k) hhhh ... h 8 h 4 h 2 h 1  - powers of 2
(n ≡ 0 mod 3) mmm ... m (n * 2k) ... - multiples of 3

Collatz streets

Motivation: Patterns in sequences with 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 h  71 t 214 h 107 t 322 h 161 t 484 h  242 h 121 t 364 | 182, 91, ... 10, 5, 16, 8, 4, 2, 1]
143/104: [143 t 430 h 215 t 646 h 323 t 970 h 485 t 1456 h 728 h 364 | 182, 91, ... 10, 5, 16, 8, 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 can be computed from the first. Walking from right to left, the step pattern is:

d m m d m d m d m 
m m d m d m d m d

or, in linearized form:

d/m m/m m/d d/m m/d d/m m/d d/m m/d ... 

Informally, a street is a parallel arrangement of 2 paths stemming from 2 sequences which have a common tail. A street starts with an element ≡ 4 mod 6 (364 in the example, before the bar), it proceeds to the left with a d/m and a m/m pair of steps, and then it extends to the left as long as a characteristical, alternating sequence of pairs of steps m/d - d/m - m/d - d/m ... can be continued. In the example, the street can be continued with 4 additional pairs of steps:

  q t | 62 h  31 t  94 h  47 t 142 h ...
126 h | 63 t 190 h  95 t 286 h 143 t ...
        +1  *6+4    +1  *6+4    +1  

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

Street directory S

Though the graph usually has a "chaotic" appearance, the streets exhibit quite some amount of regular structure. This can be seen if we list the paired elements of the streets for all possible starting values 4, 10, 16, 22 ... 6n-2 for n = 1, 2 ... as rows of a table, in reversed direction (extending to the right). The elements ≡ 4 mod 6 are highlighted:

c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14 c15 ...
4 182164511023
103206401213
1653210642021
2274414882829958
28956181123637
341168221364445
401380261605253171063435117022237461415
461592301846061
5217104342086869
5819116382327677251545051
6421128422568485
7023140462809293
76251525030410010133202

There is a more elaborated example for elements <= 143248.

When this file is displayed in a browser, the zoom factor may be reduced (with Ctrl "-", to 25 % for example) such that the structure of the lengths of streets can be seen.

Street construction rules

The following table shows the rules for the construction of the first 9 columns S[n,1..9] of row n (n = 1, 2, 3 ...) in the street directory:

Column Steps Expression Formula Condition Coverage
1 6n-2 4,10,16,22 mod 24
2 d (6n-2-1)/3 2n-1 all odd numbers
3 m (6n-2)*2 12n-4 8,20 mod 24
4 dm ((6n-2-1)/3)*2 4n-2 2,6,10,14,18,22 mod 24
5 mm (6n-2)*2*2 24n-8 16 mod 24
6 dmm ((6n-2-1)/3)*2*2 8n-4 4,12,20 mod 24
7 mmd ((6n-2)*2*2-1)/3 8n-3 5,13,21 mod 24
8 dmmd ((6n-2-1)/3)*2*2-1)/3 (8n-5)/3 n ≡ 1 mod 3 (1,9,17,25 ...)
9 mmdm ((6n-2)*2*2-1)/3)*2 16n-6 n ≡ 1 mod 3 (10,58,106,154, ...)

The first 6 columns of the table cover the odd numbers and all numbers ≡ 2,4,6,8,10,12,16,18,20,22 mod 24.

It is not shown so far that all multiples of 24 are contained in the table.

Highlighted numbers

The numbers of the form 6p-2 were highlighted in the example above. They have the special property that, when p > 0 and p ≡ 0 mod 3, a dm-step yields a number of the same form, but with one factor 3 in p replaced by 2:

6(3q)-2 dm ((6(3q)-2)-1)/3*2 = (6q-1)*2 = 6(2q)-2

This implies that a dm-step decreases any number by about one third.

Street lengths > 7

  • Columns 4(k+1)+1 result by dm-steps from columns 4k+1 for k=1,2,... (and so do columns 4(k+1)+2 result from columns 4k+2). Sequences of dm-steps decrease the numbers. Therefore the lengths of all streets are finite.
  • Column 5 is 24n-8, and the lengths depend on the power of 3 contained in that n.
  • At the starting values 4, 40, 364, 3280, 29524 (OEIS A191681) the street lengths have high values 5, 9, 13, 17, 21 which did not occur before. Those starting values are (9n+1 - 1) / 2, or 4 * Sum(9i, i=0..n).

Coverage

The elements of the streets are strongly interconnected, and the table "obviously" shows all positive integers which are not multiples of 24:

r1 ≡ 4 mod 6 ≡ 4,10,16,22 mod 24
r2 ≡ 1 mod 2 all odd numbers
r3 ≡ 8 mod 12 ≡ 8,20 mod 24
r4 ≡ 2 mod 4 ≡ 2,6,10,14,18,22 mod 24
r5 ≡ 16 mod 24 ≡ 16 mod 24
r6 ≡ 4 mod 8 ≡ 4,12,20 mod 24


So if we can show that we reach all start values ≡ 4 mod 6, we have a proof that all positive integers are reached.

Starting with 4, it seems possible that a continuous expansion of all numbers ≡ 4 mod 6 into streets would finally yield all streets up to some start value. Experiments show that there are limits for the numbers involved. Streets above the clamp value are not necessary in order to obtain all streets below and including the start value:

start value clamp value
4 4
40 76
364 2308
3280 143248

Subset table S

We may build derived table from the table of streets. We take columns r0 and r5 ff., and therein we keep the highlighted entries (those which are ≡ 4 mod 6) only, add 2 to them and divide them by 6. The resulting subset table S starts as follows:

s0  s1   s2   s3   s4   s5   s6   s7   s8   ...
 n  len  
 1   3    3    1    2
 2   1    7
 3   1   11
 4   3   15    5   10
 5   1   19
 6   1   23
 7   7   27    9   18    6   12    4    8
 8   1   31
 9   1   35
10   3   39   13   26
11   1   43
12   1   47
13   3   51   17   34
14   1   55
15   1   59
16   5   63   21   42   14   28
...

This table can be described by simple rules which are hopefully provable from the construction rule for the streets:

  • s2 is always s0 * 4 - 1.
  • When s2 ≡ 0 mod 3, the following columns s3, s4 ... are obtained by an alternating sequence of steps
    • si+1 = si / 3 and
    • si+2 = si+1 * 2,
    • until all factors 3 in s2 are replaced by factors 2.

Does S contain all positive integers?

The answer is yes. As above, we can regard the increments in successive columns:

ss ≡ 3 mod 4 half of the odd numbers
s3 ≡ 1 mod 4 other half of odd numbers
s4 ≡ 2 mod 8 ≡ 2,10 mod 16
s5 ≡ 6 mod 8 ≡ 6,14 mod 16
s6 ≡ 12 mod 16 ≡ 12 mod 16
s7 ≡ 4 mod 16 ≡ 4 mod 16
s8 ≡ 8 mod 32 8, 40, 72, ...
s9 ≡ 24 mod 32 24, 56, 88, ...
s10 ≡ 48 mod 64 48, 112, 176, 240 ...
s11 ≡ 16 mod 64 16, 80, ...

This shows that the columns s4 ... s7 contain all numbers ≡ 2,4,6,10,12,14 mod 16, but those ≡ 0,8 mod 16 are missing so far. The ones ≡ 8 mod 16 show up in s8 resp. s9, half of the multiples of 16 are in s10 resp. s11 but ≡ 0,32 mod 64 are missing, etc.

Since s2 contains arbitray high powers of 3, S has rows of arbitrary length, and for the missing multiples of powers of 2 the exponents can be driven above all limits.

Thus S contains all positive integers.

Can S be generated starting at 1?

We ask for an iterative process which starts with the row of S for index 1:

 1:    3    1    2

Then, all additional rows for the elements obtained so far are generated:

 2:    7
 3:   11

These rows are also expanded:

 7:   27    9   18    6   12    4    8
11:   43

Since we want to cover all indexes, we would first generate the rows for lower indexes. This process fills all rows up to s0 = 13 rather quickly, but the first 27 completely filled rows involve start numbers s0 up to 1539, and for the first 4831 rows, start values up to 4076811 are involved.