|
|
| (23 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]] |
| * Manfred Trümper: ''The Collatz Problem in the Light of an Infinite Free Semigroup''. Chinese Journal of Mathematics, Vol. 2014, [http://dx.doi.org/10.1155/2014/756917 Article ID 756917], 21 p.
| | * [[OEIS/3x%2B1_Levels]] |
| ==Collatz Graph==
| | * [[OEIS/Attaching segments]] |
| 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.
| |
| 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 consider the trivial cycle, and we start the graph with node 4, the ''root''.
| |
| Moreover, a trivial path starts when m ≡ 0 mod 3. We call such a path a ''sprout'', and it contains duplications only. A sprout must be added to the graph for any node divisible by 3, therefore we will not consider them for the moment.
| |
| ===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 according to the following table (T1):
| |
| {| 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)
| |
| |-
| |
| | σ := δµ|| squeeze || +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 (it "squeezes" a 3 into a 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 becomes 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''. The columns in one row i of C are constructed as described in the following table (T2):
| |
| {| class="wikitable" style="text-align:left"
| |
| !Column j !! Operation !! Formula !! Condition !! Sequence
| |
| |-
| |
| | 1 || || 6 * i - 2 || || 4, 10, 16, 22, 28, ...
| |
| |-
| |
| | 2 || <nowiki>C[i,1]</nowiki> µµ || 24 * (i - 1) + 16 || || 16, 40, 64, 88, 112, ...
| |
| |-
| |
| | 3 || <nowiki>C[i,1]</nowiki> δµµ || 24 * (i - 1) / 3 + 4 || i ≡ 1 mod 3 || 4, 28, 52, 76, 100, ...
| |
| |-
| |
| | 4 || <nowiki>C[i,2]</nowiki> σ || 48 * (i - 1) / 3 + 10 || i ≡ 1 mod 3 || 10, 58, 106, 134, ...
| |
| |-
| |
| | 5 || <nowiki>C[i,3]</nowiki> σ || 48 * (i - 7) / 9 + 34 || i ≡ 7 mod 9 || 34, 82, 130, 178, ...
| |
| |-
| |
| | 6 || <nowiki>C[i,2]</nowiki> σσ || 96 * (i - 7) / 9 + 70 || i ≡ 7 mod 9 || 70, 166, 262, 358, ...
| |
| |-
| |
| | 7 || <nowiki>C[i,3]</nowiki> σσ || 96 * (i - 7) / 27 + 22 || i ≡ 7 mod 27 || 22, 118, 214, 310, ...
| |
| |-
| |
| | 8 || <nowiki>C[i,2]</nowiki> σσσ || 192 * (i - 7) / 27 + 46 || i ≡ 7 mod 27 || 46, 238, 430, 622, ...
| |
| |-
| |
| | 9 || <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''.
| |
| ::It is easy to create a '''[http://www.teherba.org/fasces/oeis/collatz/comp.html segment directory]''' (up to 30000) by a [https://github.com/gfis/fasces/blob/master/oeis/collatz/collatz_rails.pl Perl program].
| |
| | |
| We make a number of claims for segments:
| |
| * (C1) 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.
| |
| * (C2) All segments have a finite length. | |
| : At some point the σ operations will have replaced all factors 3 by 2.
| |
| * (C3) All nodes in the right part of a segment have the form 6 * (3<sup>n</sup> * 2<sup>m</sup> * f) - 2 with the same "3-2-free" factor f.
| |
| : This follows from the operations for columns <nowiki>C[i,1..3]</nowiki>, and from the fact that the σ operation maintains this property.
| |
| * (C4) 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 (in the segment with left part 40):
| |
| 160 = 6 * (3<sup>3</sup> * 2<sup>0</sup> * 1) - 2
| |
| 52 = 6 * (3<sup>2</sup> * 2<sup>0</sup> * 1) - 2
| |
| 106 = 6 * (3<sup>2</sup> * 2<sup>1</sup> * 1) - 2
| |
| 34 = 6 * (3<sup>1</sup> * 2<sup>1</sup> * 1) - 2
| |
| 70 = 6 * (3<sup>1</sup> * 2<sup>2</sup> * 1) - 2
| |
| 22 = 6 * (3<sup>0</sup> * 2<sup>2</sup> * 1) - 2
| |
| 46 = 6 * (3<sup>0</sup> * 2<sup>3</sup> * 1) - 2
| |
| * (C5) There is no cycle in a segment.
| |
| ===Segment Lengths===
| |
| The segment directory is 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. For the left parts 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 left parts 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, as shown in the following table (T3):
| |
| {| 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.
| |
| * (C6) 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 claim:
| |
| * (C7) '''All numbers of the form 6 * n - 2 occur exactly once''' in the right part of the segment directory.
| |
| : The sequences defined by the columns in the right part all have different modulus conditions. Therefore they are all disjoint.
| |
| ==Segment Connectivity Sieve==
| |
| The segments represent small trees with two branches. We now start an ''Gedankenexperiment'' analogous to [https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel Hilbert's hotel]. We consider simultaneously all rows i > 1 (omitting the root) in C which fulfill some modularity condition (the ''source'' row in C), and we ''attach'' (identify, connect) them to their unique occurrence in the right part of C (''target'' row and column).
| |
| : A technical implementation of the process (which is impossible for infinite sets) would perhaps replace the target node by a pointer to the source segment.
| |
| We ''sieve'' the segments: Once we have attached a set of segments, we strike it out of the list still to be examined. The attachment rules are shown in the following table (T4):
| |
| {| class="wikitable" style="text-align:left"
| |
| |-
| |
| !Source Row i !! Target Row !! Column !! Remaining Rows !! Fraction
| |
| |-
| |
| |i ≡ 3 mod 4 ||((i - 3) / 4) * 3<sup>0</sup> + 1 || 2||i ≡ 0, 1, 2 mod 4 ||3/4
| |
| |-
| |
| |i ≡ 1 mod 4 ||((i - 1) / 4) * 3<sup>1</sup> + 1 || 3||i ≡ 0, 2, 4, 6 mod 8 ||1/2
| |
| |-
| |
| |i ≡ 2 mod 8 ||((i - 2) / 8) * 3<sup>1</sup> + 1 || 4||i ≡ 0, 4, 6 mod 8 ||3/8
| |
| |-
| |
| |i ≡ 6 mod 8 ||((i - 6) / 8) * 3<sup>2</sup> + 7 || 5||i ≡ 0, 4, 8, 12 mod 16 ||1/4
| |
| |-
| |
| |i ≡ 12 mod 16||((i - 12) / 16) * 3<sup>2</sup> + 7 || 6||i ≡ 0, 4, 8 mod 16 ||3/16
| |
| |-
| |
| |i ≡ 4 mod 16||((i - 4) / 16) * 3<sup>3</sup> + 7 || 7||i ≡ 0, 8, 16, 24 mod 32 ||1/8
| |
| |-
| |
| |i ≡ 8 mod 32||((i - 8) / 32) * 3<sup>3</sup> + 7 || 8||i ≡ 0, 16, 24 mod 32 ||3/32
| |
| |-
| |
| |i ≡ 24 mod 32||((i - 24) / 32) * 3<sup>4</sup> + 61|| 9||i ≡ 0, 16, 32, 48 mod 64||1/16
| |
| |-
| |
| |i ≡ 48 mod 64||((i - 48) / 64) * 3<sup>4</sup> + 61||10||i ≡ 0, 16, 32 mod 64 ||3/64
| |
| |-
| |
| |i ≡ 16 mod 64||((i - 16) / 64) * 3<sup>5</sup> + 61||11||i ≡ 0, 32, 64, 96 mod 128 ||1/32
| |
| |-
| |
| | ... || ... || ... || ... || ...
| |
| |-
| |
| |}
| |
| The ellipsis row of this table could be explained in terms of i, but it should be obvious how it can be constructed. The residues of 2<sup>k</sup> in the first column are 3 * 2<sup>k-2</sup>, 1 * 2<sup>k-2</sup> in an alternating sequence. The additive constants in the second column are the indexes of the variable length segments with left parts (4), 40, 364, 3280, 29524 ([http://oeis.org/A191681 OEIS A191681]) mentioned above. They are repeated 4 times since the corresponding lengths "jump" by 4.
| |
| ====Example====
| |
| 82 is a node with a long Collatz sequence. The following list (L1) shows - via the highlighted numbers - how segments are attached:
| |
| 1 2 3 4 5 6 7 8 9 10 11 12
| |
| C[ 14] '''82''' 328
| |
| C[ 16] '''94''' 376 124 250 '''82''' 166
| |
| C[ 61] '''364''' 1456 484 970 322 646 214 430 142 286 '''94''' 190
| |
| C[ 46] '''274''' 1096 '''364''' 730
| |
| C[ 52] '''310''' 1240 412 826 '''274''' 550
| |
| C[ 88] '''526''' 2104 700 1402 466 934 '''310''' 622
| |
| C[223] '''1336''' 5344 1780 3562 1186 2374 790 1582 '''526''' 1054
| |
| C[ 56] '''334''' '''1336 '''
| |
| C[142] '''850''' 3400 1132 2266 754 1510 502 1006 '''334''' 670
| |
| C[160] '''958''' 3832 1276 2554 '''850''' 1702
| |
| C[304] '''1822''' 7288 2428 4858 1618 3238 1078 2158 718 1438 478 '''958 '''
| |
| C[385] '''2308''' 9232 3076 6154 2050 4102 1366 2734 910 '''1822 '''
| |
| C[289] '''1732''' 6928 '''2308''' 4618
| |
| C[217] '''1300''' 5200 '''1732''' 3466
| |
| C[163] '''976''' 3904 '''1300''' 2602
| |
| C[ 41] '''244''' '''976 '''
| |
| C[ 31] '''184''' 736 '''244''' 490
| |
| C[ 8] '''46''' '''184 '''
| |
| C[ 7] '''40''' 160 52 106 34 70 22 '''46 '''
| |
| C[ 2] '''10''' '''40 '''
| |
| C[ 1] '''4''' 16 4 '''10 '''
| |
| ===Segment Tree===
| |
| * (C8) The process does not create any cycle.
| |
| : All involved subtrees are disjoint. The process attaches trees to other trees, the results are trees again.
| |
| * (C9) Any source row will finally be attached to the tree starting at the root segment.
| |
| : Similiar to the arguments for coverage, we have to apply the rules from table T4 one after the other up to a sufficiently high row (corresponding to a sufficiently long variable segment).
| |
| | |
| ==Collatz Tree==
| |
| * (C10) The segment tree is a subgraph of the Collatz graph.
| |
| : The edges of the segment tree carry combined operations µµ, δµµ and σ = δµ.
| |
| So far, numbers of the form x ≡ 0, 1, 2, 3, 5 mod 6 are missing from the segment tree.
| |
| | |
| We insert intermediate nodes into the segment tree by applying operations on the left parts of the segments as shown in the following table (T5):
| |
| {| class="wikitable" style="text-align:left"
| |
| |-
| |
| ! Operation !! Condition !! Resulting Nodes !! Remaining Nodes
| |
| |-
| |
| |δ || || 2 * i - 1 || i ≡ 0, 2, 6, 8 mod 12
| |
| |-
| |
| |µ || || 12 * i - 4 || i ≡ 0, 2, 6 mod 12
| |
| |-
| |
| |δµ || i ≡ 1, 2 mod 3 || 4 * i - 2 || i ≡ 0, 12 mod 24
| |
| |-
| |
| |δµµ || i ≡ 2 mod 3 || 8 * i - 4 || i ≡ 0 mod 24
| |
| |-
| |
| |δµµµ || i ≡ 2 mod 3 || 16 * i - 8 || (none)
| |
| |-
| |
| |}
| |
| The first three rows in T5 care for the intermediate nodes at the beginning of the segment construction with columns 1, 2, 3. Rows 4 and 5 generate the sprouts (starting at multiples of 3) which are not contained in the segment directory.
| |
| | |
| We call such a construction a ''detailed segment'' (in contrast to the ''compressed segments'' described above).
| |
| :: A '''[http://www.teherba.org/fasces/oeis/collatz/rails.html detailed segment directory]''' can be created by the same [https://github.com/gfis/fasces/blob/master/oeis/collatz/collatz_rails.pl Perl program]. In that directory, the two subpaths of a segment are shown in two lines. Only the highlighted nodes are unique.
| |
| | |
| * (C11) The connectivity of the segment tree remains unaffected by the insertions.
| |
| * (C12) With the insertions of T5, the segment tree covers the whole Collatz graph.
| |
| * (C13) '''The Collatz graph is a tree''' (except for the trivial cycle).
| |