OEIS/3x+1 Problem: Difference between revisions

From tehowiki
Jump to navigation Jump to search
imported>Gfis
coverage
new section
 
(44 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 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.
 
It is convenient to use abbreviations for the elementary operations which transform a node (element, number) x into y:
 
{| class="wikitable" style="text-align:center"
!Name    !! Mnemonic  !! Distance to 4 !!  Neighbour location    !! Condition         
|-
| x d y  || down      || -1            ||  y = x / 2              || x ≡ 0 mod 2 
|-
| x u y  || up        || -1            ||  y = 3 * x + 1          || (none)             
|-
| x δ y || divide    || +1 ||  y = (x - 1) / 3        || x ≡ 1 mod 3   
|-
| x µ y || multiply  || +1 ||  y = x * 2              || (none)
|}
When moving towards the root (4) of the graph, d/u operations are used, while δ/µ operations are used to move away from the root.
====Detailed Segment Construction====
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 x ≡ 4 mod 6. Then they split into a ''northern'' and a ''southern'' subsegment by applying the following operations:
* northern: µ µ δ µ δ µ δ ...
* southern: δ µ µ δ µ δ µ ...
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 δ operation is not possible.
 
We will call these segments ''detailled'', 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]. We will later come back to more properties of detailed segments.
 
====Compressed Segments====
For the moment we will concentrate on the nodes x &#x2261; 4 mod 6 in the detailed segments (which are highlighted in the directory). For each segment we define a row i in an array <nowiki>C[i,j]</nowiki> as follows:
{| class="wikitable" style="text-align:center"
!C[i,1] !! C[i,2] !! C[i,3] !! C[i,4] !! C[i,5] !! C[i,6] !! C[i,7] !! C[i,8] !! ...         
|-
| 6*i-2
| C[i,1] &micro;&micro; 
| C[i,1] &delta;&micro;&micro; 
| C[i,2] &delta;&micro; 
| C[i,3] &delta;&micro; 
| C[i,4] &delta;&micro; 
| C[i,5] &delta;&micro; 
| C[i,6] &delta;&micro; 
|...
|}
The row for the compressed segment is filled as long as the corresponding node in the detailed segment is &#x2261; 4 mod 6.
 
The segment directories are obviously very structured. The lengths of the compressed segments follow the pattern
4 2 2 4 2 2 m 2 2 4 2 2 4 2 2 n 2 2 4 2 2 ...
with two ''fixed lengths'' 2 and 4 and some ''variable lengths'' m, n ... &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).
 
If we interprete the <nowiki>C[i,j]</nowiki> as 6*p - 2, we observe that factors 3 in p are successively replaced by factors 2 for increasing j &gt;= 2.
====Connectivity of Segments====
We now claim that all numbers of the form 6*p - 2 (<nowiki>C[i,1]</nowiki>, the ''left side'' ) occur exactly once in the ''right side'' <nowiki>C[i,j], j &gt; 1</nowiki>.
 
If this claim were proven, we could begin with the compressed segment for 4, and therein at every node &gt; 4 we  "attach" a unique segment with that starting element. Doing this iteratively we could reach all numbers of the form 6*p - 2.
 
We find the following sequences in the columns of C:
<nowiki>C[i,2]</nowiki> = 24*(i - 1)  + 16
<nowiki>C[i,3]</nowiki> = 24*(i - 1)/3 +  4    if i &#x2261; 1 mod 3 
<nowiki>C[i,4]</nowiki> = 48*(i - 1)/3 + 10    if i &#x2261; 1 mod 3 
<nowiki>C[i,5]</nowiki> = 48*(i - 7)/9 + 34    if i &#x2261; 7 mod 9 
We thereby cover the highlighted numbers of the form 6*p - 2 &lt; 48:
'''4'''  '''10'''  '''16'''  22  '''28'''  '''34'''  '''40'''  46

Latest revision as of 07:50, 2 August 2023

A collection of considerations regarding the Collatz conjecture.

It is splitted into the following parts: