|
|
| (14 intermediate revisions by one other user not shown) |
| Line 1: |
Line 1: |
| ==Abstract==
| | A collection of considerations regarding the '''[https://en.wikipedia.org/wiki/Collatz_conjecture Collatz conjecture]'''. |
| With the operations defined by Collatz for his ''3x + 1'' problem, two sets of special, finite trees are constructed. It is shown that these trees contain all numbers, and that the can be combined to form bigger trees by an iterative process. This process is repeated on four levels, until it is finally shown that all remaining trees can be combined into one tree which contains all natural numbers, and which is free of cycles (except for the cycle 4-2-1).
| |
| ==Introduction==
| |
| '''Collatz sequences''' (also called ''trajectories'') are sequences of integer numbers > 0. For some start value > 0 the elements of a particular sequence are constructed with two simple rules:
| |
| # Even numbers are halved.
| |
| # Odd numbers 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 all start values. 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.
| |
|
| |
|
| Simple visualizations of Collatz sequences show 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: |
| <p align="right">''Da sieht man den Wald vor lauter Bämen nicht.''<br />German proverb: ''You cannot see the wood for the trees.''
| | * [[OEIS/3x%2B1_Intro]] |
| </p>
| | * [[OEIS/3x%2B1_Segments]] |
| ===References===
| | * [[OEIS/3x%2B1_Connectivity]] |
| * 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_Levels]] |
| * OEIS A07165: [http://oeis.org/A070165/a070165.txt File of first 10K Collatz sequences], ascending start values, with lengths
| | * [[OEIS/Attaching segments]] |
| * 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.
| |
| | |
| ==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
| |
| * to ''(n - 1) / 3'' if ''n ≡ 1 mod 3''.
| |
| | |
| The Collatz conjecture claims that the Collatz graph
| |
| * contains all numbers,
| |
| and that it - except for the leading cycle 1 - 2 - 4 - 1 - 2 - 4 ... -
| |
| * has the form of a tree (without cycles). | |
| We will not consider the leading cycle, and we start the graph with node 4, the '''root'''.
| |
| Furthermore we observe that a path can be continued with duplications only once it reaches a node ''n ≡ 0 mod 3''. We omit these trivial continuations.
| |
| ===Graph Operations===
| |
| Following [http://dx.doi.org/10.1155/2014/756917 Trümper], we use abbreviations for the elementary '''operations''' which map a node (element, number) ''n'' in the Collatz graph to the a neighbouring node as shown in the following table (T1):
| |
| {| class="wikitable" style="text-align:center"
| |
| !Name !! Mnemonic !! Distance to root !! Mapping !! Condition
| |
| |-
| |
| | d || "down" || -1 || n ↦ n / 2 || n ≡ 0 mod 2
| |
| |-
| |
| | u || "up" || -1 || n ↦ 3 * n + 1 || (none)
| |
| |-
| |
| | s := ud || "spike" || -2 || n ↦ (3 * n + 1) / 2)|| n ≡ 1 mod 2
| |
| |-
| |
| | δ || "divide" || +1 || n ↦ (n - 1) / 3 || n ≡ 1 mod 3
| |
| |-
| |
| | µ || "multiply" || +1 || n ↦ n * 2 || (none)
| |
| |-
| |
| | σ := δµ|| "squeeze" || +2 ||n ↦ ((n - 1) / 3) * 2|| n ≡ 1 mod 3
| |
| |}
| |
| The operations will be noted as ''infix'' operators, with the source node as left operand and the target node as right operand, for example ''10 δµ 6''. In the following, we will mainly be interested in the reverse mappings (denoted with greek letters) which move away from the root 4 of the graph.
| |
| | |
| ===Motivation: Patterns in sequences with the same length===
| |
| A closer look at the Collatz sequences shows a lot of pairs of adjacent start values which have the same sequence length, for example (from [https://oeis.org/A070165 OEIS A070165]):
| |
| 142/104: 142 d 71 u 214 d 107 u 322 d 161 u 484 d 242 d 121 u 364 ] d 182 ... 4 d 2 d 1
| |
| 143/104: 143 u 430 d 215 u 646 d 323 u 970 d 485 u 1456 d 728 d 364 ] d 182 ... 4 d 2 d 1
| |
| The alternating pattern of operations can be continued to the left with additional pairs of steps:
| |
| n? u [ 62 d 31 u 94 d 47 u 142 d ...
| |
| 126 d [ 63 u 190 d 95 u 286 d 143 u ...
| |
| The pattern stops here since there is no integer ''n'' such that ''n * 3 + 1 = 62''.
| |
| Beginning at some node (364 ≡ 4 mod 6 in the example), these sequences join and follow the same path down to the root 4. The two differing parts of the sequences show a regular pattern. Proceeding from right to left, and thereby using the inverse operations, we see the following operations:
| |
| 364 δ 121 µ 242 µ 484 δ 161 µ 322 δ 107 µ 214 δ 71 µ 142 δ 47 µ 94 δ 31 µ 62
| |
| 364 µ 728 µ 1456 δ 485 µ 970 δ 323 µ 646 δ 215 µ 430 δ 143 µ 286 δ 95 µ 190 δ 63
| |
| | |
| ==Segments==
| |
| These patterns lead us to the construction of special subsets of paths in the Collatz graph which we call '''segments'''. Starting at some node ''n ≡ 4 mod 6'', the ''fork'', two subpaths lead away from the root in a prescribed, finite sequence of operations.
| |
| :The nodes ''n ≡ 4 mod 6'' play a special role because they are the only ones for which both a δ and a µ operation is possible.
| |
| | |
| ===Segment Construction Rules===
| |
| Informally, the segments are constructed beginning at the fork with a few differing operations, followed by a sequence of σ operations in both subpaths.
| |
| | |
| The segment construction process stops when the next node in one of the two subpaths becomes divisible by 3, i.e. when a δ (resp. σ) operation is no more possible. We will show that this is always the case.
| |
| | |
| ===σ replaces 3 by 2===
| |
| The σ operation, when applied to fork nodes of the form ''6i - 2'' with ''i = 3k'', has the interesting property that it maintains the general form ''6n - 2'':
| |
| 6(3k) - 2 σ (2(3k) - 1) * 2 = 12k - 2 = 6(2k) - 2
| |
| That means that σ replaces one factor 3 by a factor 2 (it "squeezes" a 3 into a 2). In the opposite direction, the ''s ("spike")'' operation replaces one factor 2 in ''i'' by a factor 3.
| |
| In the same way we could have used the form ''6n + 4'' with ''i = 3k - 1'':
| |
| 6(3k - 1) + 4 σ (2 * (3k - 1) + 1) * 2 = 12k - 4 + 2 = 6(2k - 1) + 4
| |
| Whether the resulting formulas are more simple may be a matter of taste. We use the previous form ''6n - 2'' in the rest of this article.
| |
| | |
| With this property it is easy to state:
| |
| * (S??) For any possible fork node, the corresponding segment is of finite length.
| |
| :: The length of the segment is proportional to the power of 3 contained in the factor ''i'' of the fork node, which is finite.
| |
| | |
| ===Segment Directory Construction===
| |
| For the presentation of various properties of the segments, we use a linearized notation of the two subpaths.
| |
| We list the segments for all possible fork nodes of the form ''6i - 2, i > 0'' as rows of an infinite array ''<nowiki>C[i, j]</nowiki>'' which we call the '''segment directory'''.
| |
| | |
| The following table '''(T2)''' tells how the columns ''j'' in one row ''i'' of ''C'' must be constructed if the condition is fulfilled:
| |
| {| class="wikitable" style="text-align:left"
| |
| !Column j !! Operation !! Formula !! Condition !! First elements
| |
| |-
| |
| | 1 || <nowiki>C[i, 1]</nowiki> || 6 * i - 2 || || 4, 10, 16, 22, 28 ...
| |
| |-
| |
| | 2 || <nowiki>C[i, 1]</nowiki> µµ || 24 * (i - 1) / 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, 4]</nowiki> σ || 96 * (i - 7) / 9 + 70|| i ≡ 7 mod 9 || 70, 166, 262, 358 ...
| |
| |-
| |
| | 7 || <nowiki>C[i, 5]</nowiki> σ || 96 * (i - 7) / 27 + 22|| i ≡ 7 mod 27 || 22, 118, 214, 310 ...
| |
| |-
| |
| | 8 || <nowiki>C[i, 6]</nowiki> σ || 192 * (i - 7) / 27 + 46|| i ≡ 7 mod 27 || 46, 238, 430, 622 ...
| |
| |-
| |
| | 9 || <nowiki>C[i, 7]</nowiki> σ || 192 * (i - 61) / 81 + 142|| i ≡ 61 mod 81 || 142, 334 ...
| |
| |-
| |
| |...|| ... || ... || ... || ...
| |
| |-
| |
| | j || <nowiki>C[i, j-2]</nowiki> σ || 6 * 2<sup>k+1</sup> * (i - m) / 3<sup>l</sup> + 3 * 2<sup>k</sup> * h - 2 || i ≡ m mod 3<sup>l</sup> || ...
| |
| |-
| |
| |}
| |
| The general formula for a column ''j >= 4'' uses the following parameters:
| |
| * ''k = floor(j / 2)''
| |
| * ''l = floor(j - 1) / 2)''
| |
| * ''m = a(floor((j - 1) / 4)'', where ''a(n)'' is the OEIS sequence ([http://oeis.org/A066443 A066443]: ''a(0) = 1; a(n) = 9 * a(n-1) - 2 for n > 0'' . The values are the indexes 1, 7, 61, 547, 4921 ... of the variable length segments with left sides (4), 40, 364, 3280, 29524 ([http://oeis.org/A191681 OEIS A191681]). The constants appear first in columns 2-4 (in segment 1), 5-8 (in segment 7), 9-12 (in segment 61) and so on
| |
| * ''h = a(j)'', where ''a(n)'' is the OEIS sequence [http://oeis.org/A084101 A084101] with period 4: ''a(0..3) = 1, 3, 3, 1; a(n) = a(n - 4) for n > 3''.
| |
| (This results in ''k = 2, l = 1, m = 1, h = 1 for j = 4''.)
| |
| | |
| The first few lines of the segment directory are the following:
| |
| | |
| <table style="border-collapse: collapse;>
| |
| <tr>
| |
| <td style="text-align:center"> </td>
| |
| <td style="text-align:center"> 1 </td>
| |
| <td style="text-align:center"> 2 </td>
| |
| <td style="text-align:center"> 3 </td>
| |
| <td style="text-align:center"> 4 </td>
| |
| <td style="text-align:center"> 5 </td>
| |
| <td style="text-align:center"> 6 </td>
| |
| <td style="text-align:center"> 7 </td>
| |
| <td style="text-align:center"> 8 </td>
| |
| <td style="text-align:center"> 9 </td>
| |
| <td style="text-align:center"> 10 </td>
| |
| <td style="text-align:center"> 11 </td>
| |
| <td style="text-align:center">...</td>
| |
| <td style="text-align:center">2*j</td>
| |
| <td style="text-align:center">2*j+1</td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border:1px solid gray;text-align:right" > i </td>
| |
| <td style="border:1px solid gray;text-align:right" >6*i‑2</td>
| |
| <td style="border:1px solid gray;text-align:right" >µµ</td>
| |
| <td style="border:1px solid gray;text-align:right" >δµµ</td>
| |
| <td style="border:1px solid gray;text-align:right" >µµσ</td>
| |
| <td style="border:1px solid gray;text-align:right" >δµµσ</td>
| |
| <td style="border:1px solid gray;text-align:right" >µµσσ</td>
| |
| <td style="border:1px solid gray;text-align:right" >δµµσσ</td>
| |
| <td style="border:1px solid gray;text-align:right" >µµσ<sup>3</sup></td>
| |
| <td style="border:1px solid gray;text-align:right" >δµµσ<sup>3</sup></td>
| |
| <td style="border:1px solid gray;text-align:right" >µµσ<sup>4</sup></td>
| |
| <td style="border:1px solid gray;text-align:right" >δµµσ<sup>4</sup></td>
| |
| <td style="border:1px solid gray;text-align:right" >...</td>
| |
| <td style="border:1px solid gray;text-align:right" >µµσ<sup>j-1</sup></td>
| |
| <td style="border:1px solid gray;text-align:right" >δµµσ<sup>j-1</sup></td>
| |
| </tr>
| |
| <tr><td align="center"> 1 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip;"> 4 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;" > 16 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 4 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 10 </td></tr>
| |
| <tr><td align="center"> 2 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip;"> 10 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;" > 40 </td></tr>
| |
| <tr><td align="center"> 3 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip;"> 16 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;" > 64 </td></tr>
| |
| <tr><td align="center"> 4 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip;"> 22 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;" > 88 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 28 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 58 </td></tr>
| |
| <tr><td align="center"> 5 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip;"> 28 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;" > 112 </td></tr>
| |
| <tr><td align="center"> 6 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip;"> 34 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;" > 136 </td></tr>
| |
| <tr><td align="center"> 7 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip;"> 40 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;" > 160 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 52 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 106 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 34 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 70 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 22 </td><td style="border:1px solid gray;text-align:right; background-color:papayawhip; font-weight:bold;"> 46 </td></tr>
| |
| </table>
| |
| | |
| There is a more elaborated '''[http://www.teherba.org/fasces/oeis/collatz/comp.html segment directory]''' with several thousand rows.
| |
| | |
| The segment directory contains an infinite number of little subtrees from which we aim to build the single Collatz tree.
| |
| ===Left Side and Right Part===
| |
| The first column(s) ''<nowiki>C[i, 1]</nowiki>'' will be denoted as the '''left side''' of the segments (or of the whole directory), while the columns ''<nowiki>C[i, j], j > 4</nowiki>'' are called the '''right part'''.
| |
| | |
| ==Coverage==
| |
| ===Coverage of Non-Forks===
| |
| We now show that
| |
| * (C1) All numbers ''n > 0'' are either forks (4 mod 6) or can be reached from forks.
| |
| We investigate the residues modulo 6 in the following table (T5):
| |
| {| class="wikitable" style="text-align:left"
| |
| |-
| |
| !Operation !! Condition !! Target<br>Nodes !! Reverse<br>Op.!!Covered<br>Residues !! Remaining<br>Residues
| |
| |-
| |
| |n = 6i - 2 || || 6i - 2 ||d ||4 mod 6 || 0, 1, 2, 3, 5 mod 6
| |
| |-
| |
| |n δ || || 2i - 1 ||u ||1, 3, 5 mod 6|| 0, 2, 6, 8 mod 12
| |
| |-
| |
| |n µ || || 12i - 4 ||d ||8 mod 12 || 0, 2, 6 mod 12
| |
| |-
| |
| |n δµ<sup>1/sup>||i ≡ 1, 2 mod 3|| 4i - 2 ||d ||2, 6 mod 12 || 0, 12 mod 24
| |
| |-
| |
| |n δµ<sup>2/sup>||i ≡ 2 mod 3 || 8i - 4 ||d ||12 mod 24 || 0 mod 24
| |
| |-
| |
| |n δµ<sup>3/sup>||i ≡ 2 mod 3 || 16i - 8 ||d ||0 mod 24 || (none)
| |
| |-
| |
| |}
| |
| Furthermore, as can be seen from the possible reverse operations:
| |
| * (C2) There is only one subpath from some fork to a specific non-fork.
| |
| | |
| ===Coverage of Forks===
| |
| We want to show:
| |
| * (C3) Any fork node of the form ''6n - 2'' occurs exactly
| |
| ** once in the left part and
| |
| ** once in the right part of the segment directory.
| |
| The first claim is fulfilled by the construction of the segment directory. The following table (T3) shows how the second claim is proven. The modular conditions for the fork nodes are successively narrowed up to arbitrarily high powers of 2.
| |
| | |
| {| 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 ''6m - 2'' occur exactly once in the right part of the segment directory, and once as a left side. There is a bijective mapping between the left sides and the elements of the right parts.
| |
| :: The sequences defined by the columns in the right part all have different modulus conditions. Therefore they are all disjoint. The left sides are disjoint by construction.
| |