|
|
| (36 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 || m ≡ 0 mod 2
| |
| |-
| |
| | δ || 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 directory), 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.
| |
| * All nodes in the right part of a segment have the same kernel.
| |
| : This follows from the formula for columns <nowiki>C[i,1..3]</nowiki>, and since the σ operation maintains this property.
| |
| * All nodes in the right part of a segment are different.
| |
| : For <nowiki>C[i,1..2]</nowiki> we see that the values modulo 24 are different. For the remaining columns, we see that the exponents of the factors 2 and 3 are different. They are shifted by the σ operations, but they alternate, for example (right part of segment starting with 40, kernel 1):
| |
| 160 = 6 * 3<sup>3</sup> * 2<sup>0</sup> - 2
| |
| 52 = 6 * 3<sup>2</sup> * 2<sup>0</sup> - 2
| |
| 106 = 6 * 3<sup>2</sup> * 2<sup>1</sup> - 2
| |
| 34 = 6 * 3<sup>1</sup> * 2<sup>1</sup> - 2
| |
| 70 = 6 * 3<sup>1</sup> * 2<sup>2</sup> - 2
| |
| 22 = 6 * 3<sup>0</sup> * 2<sup>2</sup> - 2
| |
| 46 = 6 * 3<sup>0</sup> * 2<sup>3</sup> - 2
| |
| * 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).
| |
| ===Coverage of the Right Part===
| |
| We now examine the modular conditions which result from the segment construction table in order to find out how the numbers of the form 6 * n -2 are covered by the right part of the segment directory:
| |
| {| class="wikitable" style="text-align:left"
| |
| !Columns j !! Covered !! Remaining
| |
| |-
| |
| | 2-3 || 4, 16 mod 24 || 10, 22, 34, 46 mod 48
| |
| |-
| |
| | 3-4 || 10, 34 mod 48 || 22, 46, 70, 94 mod 96
| |
| |-
| |
| | 5-6 || 70, 22 mod 96 || 46, 94, 142, 190 mod 192
| |
| |-
| |
| | 7-8 || 46, 142 mod 192 || 94, 190, 286, 382 mod 384
| |
| |-
| |
| | ... || ... || ...
| |
| |}
| |
| We can always exclude the first and the third element remaining so far by looking in the next two columns of segments with sufficient length.
| |
| * There is no limit on the length of a segment.
| |
| : We only need to take a segment which, in its right part, has a factor of 3 with a sufficiently high power, and the σ operations will stretch out the segment accordingly.
| |
| Therefore we can continue the modulus table above indefinitely, which leads us to the proposition:
| |
| * '''All numbers of the form 6 * n - 2 occur exactly once''' in the right part <nowiki>C[i,j], j > 1</nowiki> of the segment directory.
| |
| ===Connectivity===
| |
| We now aim to build a (directed) tree with nodes of the form 6 * n - 2. We take the segment starting at 4:
| |
| 16 4 10
| |
| and for at node x in the right part (x > 4) we connect the segment starting with x to the current segment. We repeat this process iteratively. There are two questions:
| |
| * Will we run into cycles?
| |
| : No, since a cyle would have a node which is entered by two edges, which violates the uniqueness of the nodes in the right part of the segment directory.
| |
| * Will we use all segments?
| |
| : Yes. Suppose otherwise that there is a minimal number which is never reached (an example could be 82 which takes very long to show up).
| |
| | |
| | |
| . We will
| |
| ===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].
| |