|
|
| (42 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.
| |
| ==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 ''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]. We will later come back to more properties of detailed segments.
| |
| | |
| ===Compressed Segments===
| |
| For the moment we will concentrate on the nodes x ≡ 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] µµ
| |
| | C[i,1] δµµ
| |
| | C[i,2] δµ
| |
| | C[i,3] δµ
| |
| | C[i,4] δµ
| |
| | C[i,5] δµ
| |
| | C[i,6] δµ
| |
| |...
| |
| |}
| |
| The row for the compressed segment is filled as long as the corresponding node in the detailed segment is ≡ 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 ... > 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 >= 2.
| |
| | |
| ===Coverage of Compressed Segments===
| |
| We now claim that
| |
| * (1) All numbers of the form 6*p - 2 occur exactly once in the ''right side'' <nowiki>C[i,j], j > 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 ≡ 1 mod 3 : 4, 28, 52, 76, 100, ...
| |
| <nowiki>C[i,4]</nowiki> = 48*(i - 1)/3 + 10 if i ≡ 1 mod 3 : 10, 58, 106, 134, ...
| |
| <nowiki>C[i,5]</nowiki> = 48*(i - 7)/9 + 34 if i ≡ 7 mod 9 : 34, 82, 130, 178, ...
| |
| We thereby cover the highlighted numbers of the form 6*p - 2:
| |
| x ≡ '''4''', '''10''', '''16''', ''22'', '''28''', '''34''', '''40''', ''46'' mod 48
| |
| We missed the numbers:
| |
| x ≡ 22, 46, 70, 94 mod 96
| |
| For these, we continue our observations:
| |
| <nowiki>C[i,6]</nowiki> = 96*(i - 7)/9 + 70 if i ≡ 7 mod 9 : 70, 166, 262, 358, ...
| |
| <nowiki>C[i,7]</nowiki> = 96*(i - 7)/27 + 22 if i ≡ 7 mod 27 : 22, 118, 214, 310, ...
| |
| This leaves us with
| |
| x ≡ 46, 94, 142, 190 mod 192
| |
| Then with
| |
| <nowiki>C[i,8]</nowiki> = 192*(i - 7)/27 + 46 if i ≡ 7 mod 27 : 46, 238, 430, 622, ...
| |
| <nowiki>C[i,9]</nowiki> = 192*(i - 61)/81 + 142 if i ≡ 61 mod 81 : 142, 334, ...
| |
| we only miss
| |
| x ≡ 94, 190, 286, 382 mod 384
| |
| "and so on": We can always exclude the first and the third element missed so far by looking at the next column of segements with sufficient length.
| |
| | |
| It seems plausible that there is a proof by induction 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.
| |
| | |
| ===Connectivity of Compressed Segments===
| |
| We now claim that we can construct a tree from the compressed segments by:
| |
| * Starting at the segment for 4,
| |
| * at every node >4 we ''attach'' the unique segment with that starting element.
| |
| * We repeat this process for all nodes collected in the tree so far.
| |
| ===Are there Cycles?===
| |