OEIS/3x+1 Problem: Difference between revisions

From tehowiki
Jump to navigation Jump to search
imported>Gfis
Kernels
new section
 
(38 intermediate revisions by one other user not shown)
Line 1: Line 1:
==Introduction==
A collection of considerations regarding the '''[https://en.wikipedia.org/wiki/Collatz_conjecture Collatz conjecture]'''.  
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 [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.


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.
It is splitted into the following parts:
===References===
* [[OEIS/3x%2B1_Intro]]  
* 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]
* [[OEIS/3x%2B1_Segments]]  
* OEIS A07165: [http://oeis.org/A070165/a070165.txt  File of first 10K Collatz sequences], ascending start values, with lengths
* [[OEIS/3x%2B1_Connectivity]]  
* 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.
* [[OEIS/3x%2B1_Levels]]
* Klaus Brennecke: ''[https://de.wikibooks.org/wiki/Collatzfolgen_und_Schachbrett Collatzfolgen und Schachbrett]'', on Wikibooks
* [[OEIS/Attaching segments]]
==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. 
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 be concerned with this cycle, and we start with node 4, the ''root''.
===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:
 
{| class="wikitable" style="text-align:center"
!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 || (none)             
|-
| δ || divide    || +1            ||  m ↦ (m - 1) / 3    || m ≡ 1 mod 3   
|-
| µ || multiply  || +1            ||  m ↦ m * 2          || (none)
|-
| σ := δµ|| step|| +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. In the opposite direction, the s operation replaces a factor 2 in m by 3.
===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.
* The kernel is not affected by σ and s operations.
==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:
{| class="wikitable" style="text-align:left"
!Column                  !! Operation                                      !! Formula !! Condition !! Sequence         
|-
| <nowiki>C[i,1]</nowiki> ||                                                || 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, ...
|-
| <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, ...
|-
| <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, ... 
|-
| <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, ... 
|-
| <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, ...
|-
| <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, ...
|-
| <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, ...
|-
| <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, ...       
|-
| ... || ... || ... || ... || ...
|-
|}
The first column(s) <nowiki>C[i,1]</nowiki> will be denoted as the ''left part'' of the segment (or of the whole diirectory), while the columns  <nowiki>C[i,j], j &gt; 1</nowiki> will be the ''right part''.
 
* 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.
* All segments have a finite length.
: At some point the &sigma; operations will have replaced all factors 3 by 2.
* Except for the segment starting with 4, all nodes in a segment are different.
:
* There is no cycle in a segment.
 
===Segment Lengths===
The segment directories are obviously very structured. The lengths of the compressed segments follow the pattern
4 2 2 4 2 2 l<sub>1</sub> 2 2 4 2 2 4 2 2 l<sub>2</sub> 2 2 4 2 2 ...
with two ''fixed lengths'' 2 and 4 and some ''variable lengths'' l<sub>1</sub>, l<sub>2</sub> ... &gt; 4. At the starting values 4, 40, 364, 3280, 29524 ([http://oeis.org/A191681 OEIS A191681]), the segment lengths have high values 4, 8, 12, 16, 20 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).
* Claim 2: All nodes in a segment (except for the segment starting with 4) are different.
: This should be provable from the formula for the fixed length portion, and for the variable length portions by the 3-by-2 replacement mentioned above.
* Therefore, the compressed segments themselves do not contain a cycle.
 
===Coverage of Compressed Segments===
* Claim 3: All numbers of the form 6*n - 2 occur exactly once in the ''right side'' <nowiki>C[i,j], j &gt; 1</nowiki>. There is a one-to-one mapping between the ''left side'' <nowiki>C[i,1]</nowiki> and the right side.
 
In the first few columns of C we find the following sequences:
<nowiki>C[i,2]</nowiki> = 24*(i - 1)  + 16                          : 16, 40, 64, 88, 112, ...
<nowiki>C[i,3]</nowiki> = 24*(i - 1)/3 +  4    if i &#x2261; 1 mod 3 :  4, 28, 52, 76, 100, ...
<nowiki>C[i,4]</nowiki> = 48*(i - 1)/3 + 10    if i &#x2261; 1 mod 3 : 10, 58, 106, 134, ...
<nowiki>C[i,5]</nowiki> = 48*(i - 7)/9 + 34    if i &#x2261; 7 mod 9 : 34, 82, 130, 178, ...
We thereby cover the highlighted numbers of the form 6*p - 2:
x &#x2261; '''4''',  '''10''',  '''16''',  ''22'',  '''28''',  '''34''',  '''40''',  ''46'' mod 48
We missed the numbers:
x &#x2261; 22, 46, 70, 94 mod 96
For these, we continue our observations:
<nowiki>C[i,6]</nowiki> = 96*(i - 7)/9  + 70  if i &#x2261; 7 mod 9  : 70, 166, 262, 358, ...
<nowiki>C[i,7]</nowiki> = 96*(i - 7)/27 + 22  if i &#x2261; 7 mod 27 : 22, 118, 214, 310, ...
This leaves us with
x &#x2261; 46, 94, 142, 190 mod 192
Then with
<nowiki>C[i,8]</nowiki> = 192*(i - 7)/27  + 46  if i &#x2261; 7  mod 27 : 46, 238, 430, 622, ...
<nowiki>C[i,9]</nowiki> = 192*(i - 61)/81 + 142  if i &#x2261; 61 mod 81 : 142, 334, ...
we only miss
x &#x2261; 94, 190, 286, 382 mod 384
"and so on": We can always exclude the first and the third element missed so far by looking in the next column of segments with sufficient length.
 
It seems plausible that there is a proof that all numbers of the form 6*p - 2 are finally contained in the right side of C, and the modular conditions make it rather obvious that these numbers are all different.
 
===Compressed Segment Tree Construction===
We now claim that we can construct a tree from the compressed segments by:
* Starting at the segment for 4,
* at every node &gt; 4 we ''attach'' the unique segment with that starting element.
* We repeat this process for all nodes collected in the tree so far.
We cannot enter a cycle, since that would imply a node which is reached by two edges, but such a node would occur more than once in the right side of the segment directory. We saw above that the segments themselves cannot have cycles.
===Collatz Tree===
Obviously we can replace all compressed segments by the corresponding detailed segments. The claim is that this will lead to the Collatz tree which reaches all numbers.
 
In the directory of detailed segments we see that we can quickly get reach all odd numbers:
<nowiki>C[i,1]</nowiki> &delta; = ((6*i-2) - 1) / 3 = 2*i - 1 : 1, 3, 5, 7
 
We remain concerned with the numbers
x &#x2261; 0,2 mod 6 resp. x &#x2261; 0, 2, 6, 8, 12, 14, 18, 20  mod 24
The following table lists the operations which are necessary to reach most of these by starting at <nowiki>C[i,1]</nowiki>:
{| class="wikitable" style="text-align:left"                                                   
|-     
!Operation !! Expression || Result              !! Condition            !! Coverage
|-
| &micro;    || (6*i-2)*2 || 12*i - 4          ||                      || 8, 20 mod 24
|-                                                                           
| &delta;&micro;  || ((6*i-2-1)/3)*2 || 4*i - 2  ||                    || 2, 6, 10, 14, 18, 22 mod 24
|-                                                                           
| &delta;&micro;&micro;  || (6*i-2-1)/3*2*2 || 8*i - 4 || i &#x2261; 2 mod 3 || 12 mod 24
|-                                                                               
|}
The multiples of 12 can be reached from the multiples of 3 (contained in the odd numbers) by a &micro;&micro; operation.
----
We will now construct special portions 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; 4 mod 6. Then they split into a ''northern'' and a ''southern'' subsegment by applying the following operations:
* northern: &micro; &micro; &delta; &micro; &delta; &micro; &delta; ...
* southern: &delta; &micro; &micro; &delta; &micro; &delta; &micro; ...
The two subsegements are built in parallel, and the process is stopped when one of the two new nodes becomes divisible by 3, resp. when a &delta; operation is not possible.
 
We will call these segments ''detailed'', and a '''[http://www.teherba.org/fasces/oeis/collatz/rails.html  segment directory]''' can easily be created by a [https://github.com/gfis/fasces/blob/master/oeis/collatz/collatz_rails.pl Perl program].

Latest revision as of 07:50, 2 August 2023

A collection of considerations regarding the Collatz conjecture.

It is splitted into the following parts: