|
|
| (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 ≡ -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 δ 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> µµ || 24 * (i - 1) + 16 || || 16, 40, 64, 88, 112, ...
| |
| |-
| |
| | <nowiki>C[i,3]</nowiki> || <nowiki>C[i,1]</nowiki> δµµ || 24 * (i - 1) / 3 + 4 || i ≡ 1 mod 3 || 4, 28, 52, 76, 100, ...
| |
| |-
| |
| | <nowiki>C[i,4]</nowiki> || <nowiki>C[i,2]</nowiki> σ || 48 * (i - 1) / 3 + 10 || i ≡ 1 mod 3 || 10, 58, 106, 134, ...
| |
| |-
| |
| | <nowiki>C[i,5]</nowiki> || <nowiki>C[i,3]</nowiki> σ || 48 * (i - 7) / 9 + 34 || i ≡ 7 mod 9 || 34, 82, 130, 178, ...
| |
| |-
| |
| | <nowiki>C[i,6]</nowiki> || <nowiki>C[i,2]</nowiki> σσ || 96 * (i - 7) / 9 + 70 || i ≡ 7 mod 9 || 70, 166, 262, 358, ...
| |
| |-
| |
| | <nowiki>C[i,7]</nowiki> || <nowiki>C[i,3]</nowiki> σσ || 96 * (i - 7) / 27 + 22 || i ≡ 7 mod 27 || 22, 118, 214, 310, ...
| |
| |-
| |
| | <nowiki>C[i,8]</nowiki> || <nowiki>C[i,2]</nowiki> σσσ || 192 * (i - 7) / 27 + 46 || i ≡ 7 mod 27 || 46, 238, 430, 622, ...
| |
| |-
| |
| | <nowiki>C[i,9]</nowiki> || <nowiki>C[i,3]</nowiki> σσσ || 192 * (i - 61) / 81 + 142|| i ≡ 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 > 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 σ operation.
| |
| * All segments have a finite length.
| |
| : At some point the σ 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> ... > 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 > 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 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 > 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> δ = ((6*i-2) - 1) / 3 = 2*i - 1 : 1, 3, 5, 7
| |
| | |
| We remain concerned with the numbers
| |
| x ≡ 0,2 mod 6 resp. x ≡ 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
| |
| |-
| |
| | µ || (6*i-2)*2 || 12*i - 4 || || 8, 20 mod 24
| |
| |-
| |
| | δµ || ((6*i-2-1)/3)*2 || 4*i - 2 || || 2, 6, 10, 14, 18, 22 mod 24
| |
| |-
| |
| | δµµ || (6*i-2-1)/3*2*2 || 8*i - 4 || i ≡ 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 µµ 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 ≡ 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].
| |