|
|
| Line 1: |
Line 1: |
| ==Abstract==
| | This article describes an attempt of [mailto:dr.georg.fischer@gmail.com Georg Fischer] to prove the Collatz conjecture. |
| The graph defined by Collatz for his ''3x + 1'' problem is overlaid with a set of small, finite trees with two branches. It is shown that this set of trees not only contains all numbers, but that it defines a permutation of the numbers. Furthermore, rules are defined how some subsets of these trees can be attached to other subsets. It is shown that no cycles can arise, and that finally the process leads to only one set of interconnected subtrees. Therefore, the Collatz graph is a tree which contains all numbers.
| |
| ==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 do not show any 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_Proof]] |
| * OEIS A070165: [http://oeis.org/A070165/a070165.txt File of first 10K Collatz sequences], ascending start values, with lengths
| |
| * 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 - 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 leading cycle, and we start the graph with node 4, the '''root'''.
| |
| Furthermore we observe that a path can only be continued with duplications 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 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 by 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]):
| |
| 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
| |
| 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
| |
| Beginning at some node of the form ''6*i - 2'' (364 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, where nodes of the form ''6*i - 2'' alternate with other nodes, and where the operations ''u'' and ''d'' also alternate.
| |
| This pattern of operations can be continued to the left with additional ''d'' and ''u'' operations:
| |
| 126 d [ 63 u 190 d 95 u 286 d 143 u ...
| |
| n? u [ 62 d 31 u 94 d 47 u 142 d ...
| |
| Finally the pattern stops because there is no integer ''n'' such that ''n * 3 + 1 = 62''.
| |
| | |
| Example (E1) shows the sequences above, read from right to left, with the inverse operations:
| |
| [ 364 µ 728 µ 1456 δ 485 µ 970 δ 323 µ 646 δ 215 µ 430 δ 143 µ 286 δ 95 µ 190 δ 63 ]
| |
| [ 364 δ 121 µ 242 µ 484 δ 161 µ 322 δ 107 µ 214 δ 71 µ 142 δ 47 µ 94 δ 31 µ 62 ]
| |
| ==Segments==
| |
| These patterns lead us to the construction of special subtrees in the Collatz graph which we call '''segments'''. This construction is the main result of this article, and as we will see, it exhibits a nested structure reminding to a ruler. Though the structure is still complicated, it is - in contrast to the Collatz graph - very regular and "predictible" in all it's properties.
| |
| | |
| Starting at some node of the form ''6*i - 2'' (the ''left side'', LS), the construction creates two subpaths (the ''upper branch'' and the ''lower branch'') which to the right by a prescribed sequence of operations.
| |
| :The nodes of the form ''6*i - 2'' play a special role because both a δ and a µ operation can be applied to them. We could also have used ''6*i + 4'' instead, but the formulas seem easier with ''6*i - 2'', therefore we always use this form.
| |
| | |
| Informally, a segment is constructed as follows:
| |
| * Step 1: Start with some node ''6*i - 2'' as the left side (LS).
| |
| * Step 2: Apply δ to the LS to get the first node in the lower branch.
| |
| * Step 3: Apply µ to the LS to get the first node in the upper branch.
| |
| * Steps 4, 5: Apply µ to both branches.
| |
| * In a loop, apply opposite operations to both branches, starting with µ (step 6) on the lower and δ (step 7) on the upper branch, continuing with δ (step 8) on the lower and µ (step 9) on the upper branch, and so on, as long as the next δ operation is possible.
| |
| The construction is such that increasing instances of σ operations are accumulated in each branch.
| |
| | |
| ===Segment directory===
| |
| The resulting set of small trees is arranged by increasing left sides in a table S with rows of irregular length, the so-called '''segment directory]'''.
| |
| :The reader is encouraged to examine an online example with the first 800 segments at [http://teherba.org/fasces/oeis/collatz/double.html http://teherba.org/fasces/oeis/collatz/double.html]. Several variants - which are described later in this article - can be accessed, and trajectories can be followd interactively.
| |
| :The "double line" presentation form of the segment directory shows the two branches of a segment in one table row. The steps are mapped to columns of the table.
| |
| :Nodes in the branches of a segment which have the form ''6*i - 2'' are shown in bold face. If ''i'' also has the form ''6*k - 2'', the node has a yellow, orange or red background.
| |
| ====Details of a segment====
| |
| The following table '''(T1)''' shows various properties of the steps or columns in the segment construction:
| |
| {| class="wikitable" style="text-align:left"
| |
| !Column j || Branch !! Operation !! Form of i !! Formula !! First elements !! Covered residues!! Remaining residues
| |
| |-
| |
| |'''1''' ||(LS) || || ||6*i - 2 ||4, 10, 16, 22 || ||1, 2, 4, 5 mod 6
| |
| |-
| |
| | 2 ||lower||δ || ||2*i - 1 ||1, 3, 5, 7 ||1, 3, 5 mod 6 ||2, 4 mod 6
| |
| |-
| |
| | 3 ||upper||µ || ||12*i - 4 ||8, 20, 32, 44 ||8 mod 12 ||2, 4, 10 mod 12
| |
| |-
| |
| | 4 ||lower||δµ || ||12*(i - 1)/1 + 2 ||2, 14, 16, 38 ||2 mod 12 ||4, 10 mod 12
| |
| |-
| |
| |'''5''' ||upper||µµ || ||24*(i - 1)/1 + 16 ||16, 40, 64, 88 ||16 mod 24 ||4, 10, 22 mod 24
| |
| |-
| |
| |'''6''' ||lower||δµµ ||i = 3*k + 1 ||24*(i - 1)/3 + 4 ||4, 28, 52, 76 ||4 mod 24 ||10, 22, 34, 46 mod 48
| |
| |-
| |
| | 7 ||upper||µµδ ||i = 3*k + 1 ||24*(i - 1)/3 + 5 ||5, 29, 53, 77 ||(5 mod 24) ||
| |
| |-
| |
| | 8 ||lower||δµµδ ||i = 3*k + 1 ||24*(i - 1)/3 + 17 ||17, 41, 65, 89 ||(17 mod 24) ||
| |
| |-
| |
| |'''9''' ||upper||µµσ ||i = 3*k + 1 ||48*(i - 1)/3 + 10 ||10, 58, 106, 154 ||10 mod 48 ||22, 34, 46 mod 48
| |
| |-
| |
| |'''10'''||lower||δµµσ ||i = 9*k + 7 ||48*(i - 7)/9 + 34 ||34, 82, 130, 178 ||34 mod 48 ||22, 46, 70, 94 mod 96
| |
| |-
| |
| |11 ||upper||µµσδ ||i = 9*k + 7 ||48*(i - 7)/9 + 35 ||35, 83, 131, 179 ||(35 mod 48) ||
| |
| |-
| |
| |12 ||lower||δµµσδ ||i = 9*k + 7 ||48*(i - 7)/9 + 11 ||11, 59, 107, 155 ||(11 mod 38) ||
| |
| |-
| |
| |'''13'''||upper||µµσ<sup>2</sup> ||i = 9*k + 7 ||96*(i - 7)/9 + 70 ||70, 166, 262, 358 ||70 mod 96 ||22, 46, 94 mod 96
| |
| |-
| |
| |'''14'''||lower||δµµσ<sup>2</sup> ||i = 27*k + 7 ||96*(i - 7)/27 + 22 ||22, 118, 214, 310 ||22 mod 96 ||46, 94, 142, 190 mod 192
| |
| |-
| |
| |15 ||upper||µµσ<sup>2</sup>δ ||i = 27*k + 7 ||96*(i - 7)/27 + 23 ||23, 119, 215, 311 ||(23 mod 96) ||
| |
| |-
| |
| |16 ||lower||δµµσ<sup>2</sup>δ||i = 27*k + 7 ||96*(i - 7)/27 + 71 ||71, 167, 263, 359 ||(71 mod 96) ||
| |
| |-
| |
| |'''17'''||upper||µµσ<sup>3</sup> ||i = 27*k + 7 ||192*(i - 7)/27 + 46 ||46, 238, 430, 622 ||46 mod 192 ||94, 142, 190 mod 192
| |
| |-
| |
| |'''18'''||lower||δµµσ<sup>3</sup> ||i = 81*k + 61||192*(i - 61)/81 + 142 ||142, 334, 526, 718||142 mod 192 ||94, 190, 286, 382 mod 384
| |
| |-
| |
| |19 ||upper||µµσ<sup>3</sup>δ ||i = 81*k + 61||192*(i - 61)/81 + 143 ||143, 225, 527, 719||(143 mod 192) ||
| |
| |-
| |
| | j || || ||i = q<sub>j</sub>*k + r<sub>j</sub> || s<sub>j</sub>*(i - r<sub>j</sub>)/q<sub>j</sub> + t<sub>j</sub> || t<sub>j</sub>, ... || t<sub>j</sub> mod s<sub>j</sub> ||
| |
| |-
| |
| |}
| |
| The general formula (in the last row of T1) for a column ''j >= 5'' uses the following parameters:
| |
| * ''q<sub>j</sub> = 3^(floor((j - 2) / 4)'',
| |
| * ''r<sub>j</sub> = A066443(floor((j - 2) / 8))'' with the OEIS sequence [http://oeis.org/A066443 A066443] defined by ''a(0) = 1; a(n) = 9 * a(n-1) - 2 for n > 0''; the terms 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]),
| |
| * ''s<sub>j</sub> = 3*2^floor((j + 7) / 4)'',
| |
| * ''t<sub>j</sub> = A309523(j) for j >= 3'' with the linear recurrent OEIS sequence [http://oeis.org/draft/A309523 A309523]. | |
| | |
| ===Finite, arbitrary length of the segments===
| |
| First we have to show that the segment construction process always stops.
| |
| For this purpose, we observe that the σ operation, when applied to left sides of the form ''6*(3*k) - 2'' has the interesting property that it maintains the general form ''6*i - 2'':
| |
| * 6*(3*k) - 2 σ (2*(3*k) - 1) * 2 = 12*k - 2 = 6*(2*k) - 2
| |
| That means that
| |
| :'''σ replaces one factor 3 by a factor 2'''
| |
| The mnemonic is that σ "squeezes" a 3 into a 2. In the opposite direction, the ''s ("spike")'' operation replaces one factor 2 by a factor 3.
| |
| | |
| The branch prolongation in the segment construction process must stop when the successive σ operations have exhausted all factors of 3 in the left side. Therefore, all segments have a finite length.
| |
| | |
| It is also clear that there is no limit on the length of a segment, since we only need to take a segment which has a factor of 3 with a sufficiently high power in its left side. The σ operations will then stretch out to the corresponding length.
| |
| ===Segments do not contain cycles===
| |
| The modulo conditions of the columns (column "Covered nodes" in T1) ensure that all nodes in a segment are different. Therefore the two branches remain disjoint, and they cannot lead to a cycle inside of the segment. (The question whether cyles could occur when differnt segments are combined is still open).
| |
| | |
| ===Coverage of the right part===
| |
| First we state again that we are not interested in even nodes of the form ''3*2*k'', because only µ operations can be applied on them. We disregards such nodes.
| |
| | |
| We see that column 2 contains all odd numbers (''i ≡ 1, 3, 5 mod 6''). Columns 7, 8, 11, 12, 15, 16, 19, 20 ... also contain subsets of odd numbers, but we disregard these columns, since their terms are duplicated in column 2.
| |
| | |
| We define the '''right part''' of a segment or of the whole segment directory to consist of the terms in columns 2-6, and all higher numbered columns which do not contain odd numbers (that are columns 9, 10, 13, 14, 17, 18 and so on).
| |
| | |
| We are now interested how the numbers > 0 are distributed over that right part. Corresponding remarks are contained in the last two columns of table T1. We want to show that the nodes in the right part are a permutation of the numbers > 0.
| |
| | |
| The left sides are in arithmetic progression, and a specific column is computed by a fixed combination of δ and µ operations. Therefore, a column is also in a simple, arithmetic progression. The modulo conditions are all different.
| |
| The initial terms ''t<sub>j</sub>'' from OEIS [https://oeis.org/draft/A309523 A309523] are also disjoint.
| |
| :The terms of OEIS [https://oeis.org/draft/A308709 A308709] are all disjoint, since that sequence is the set ''{2^k | k>=0} union {3*2^k | k>=0}'', and OEIS [https://oeis.org/draft/A309523 A309523] is the set ''{6*A308709 - 2} union {6*A308709 - 1}''.
| |
| Together that shows that the terms in the right part are all disjoint.
| |
| | |
| So far we did not yet cover numbers of the form ''i ≡ 2, 4 mod 6'' (or ''i ≡ 2, 4, 8, 10 mod 12''; ''0 mod 6'' was excluded above). We proceed by looking into each column in the right part and by observing the modulo conditions of the terms contained in that column.
| |
| | |
| Column 3 contains numbers of the form ''i ≡ 8 mod 12'', such that ''2, 4, 10 mod 12'' remain to be covered. Column 4, if it exists, contains numbers of the form ''i ≡ 2 mod 12''. This leaves us with ''i ≡ 4, 10 mod 12''.
| |
| | |
| As indicated in table T1 above, the modulo conditions in the right part become more and more refined. Since the segment directory contains arbitrarily long segments (respectively arbitrarily many columns), the modulo conditions of any height are finally reached.
| |
| | |
| Furthermore, since the modulo conditions lead to disjoint subsets of the numbers, it is ensured that any number can occur only once in the right part.
| |
| In total, the nodes in the right part are a '''permutation of the numbers''' which are not divisible by 6.
| |
| ==Connectivity of the graph==
| |
| With this result we can pick an arbitrary number, start a Collatz trajectory for it, and look in parallel which segments are encountered. We can - easily and uniquely - locate any node of the trajectory in some column in the right part of the segment directory, just be determining the rest modulo 6, 12, 24, 48 ... 6*2^k and looking it up in T1 resp. OEIS [https://oeis.org/draft/A309523 A309523]. Once the column is known, the segmet directory's row index ''i'' (and thereby the left side ''6*i - 2'') can be determined via table T1.
| |
| | |
| By locating the trajectory node uniquely in some segment, we "embed" it in a small, local tree structure. The goal is now to show that the segments can be attached ("connected", "glued" ...) to each other such they form a single tree which maps onto the whole Collatz graph.
| |
| | |
| For the connectivity considerations we classify all nodes by their residue modulo 6, and we state which of the elementary graph operations δ and µ (away from the root) can be applied to such a node ''i''. We observe the following cases:
| |
| * ''i ≡ 1, 3, 5 mod 6'' (odd node): The next operation must be µ.
| |
| * ''i ≡ 0 mod 6'' (2^k * 3): All following operations must be µ.
| |
| * ''i ≡ 2 mod 6'': The next operation must be µ, and the following node is of the form ''j ≡ 4 mod 6''.
| |
| * ''i ≡ 4 mod 6'': The next operation can be
| |
| ** δ, leading to an odd node, or
| |
| ** µ, leading to a node ''j ≡ 2 mod 6''.
| |
| In other words, only nodes of the form ''6*i - 2'' have one incoming and two outgoing edges in the graph. All other nodes have one incoming and one outgoing edge, therefore they are irrelevant for any connectivity questions.
| |
| ==Compressed segments ==
| |
| For the following considerations we replace all nodes which are not of the form ''6*i - 2'' and their two edges by a single edge Furthermore, we map the nodes ''6*i - 2'' to ''i'', and we call the result the '''compressed''' form of the nodes, segments, segment directory or graph.
| |
| : The [http://teherba.org/fasces/oeis/collatz/comp.html online example] of a compressed directory can be found under the same link mentioned above. In this presentation, the nodes of the two branches are merged (interleaved) into one line. The original column numbers of the double line directory are maintained for a consistent reference. Apart from the simplified presentation, it turns out that there is a very simple algorithm which computes such compressed segements, namely the one described in OEIS sequence [https://oeis.org/A322469 A322469].
| |
| | |
| In the following table '''T2''' we show the correspondance between the operations on the nodes ''6*i - 2'' to ''i'' in the double-line directory, and the compressed nodes of A322469:
| |
| {| class="wikitable" style="text-align:left"
| |
| !Column j || Operation on the LS !! Form of i !! Formula !! First elements !! Covered residues!! Remaining residues
| |
| |-
| |
| |'''5''' ||µµ || || ||6*i - 2 ||4, 10, 16, 22 || ||1, 2,
| |
| | |
| , and a proof that the right part of that table is a permutation of the numbers > 0 is given there.
| |
| A322469 uses a very simple set of operations on the nodes which is different from the operations described above, but we can map ours to those of than we did so far.
| |
| | |
| The uncompressed form can easily be recreated from the compressed form.
| |
| | |
| which is labeled by σ or µ<sup>2</sup> respectively.
| |
| ==Following a Collatz trajectory==
| |
| Since we are sure that all numbers occur once in the right part of our segment directory, we can pick any of them and start a Collatz trajectory, hopefully proceeding down to the root (4). We try to trace the trajectory in the segment directory.
| |
| ==Covering the Collatz graph by the right part==
| |
| The fact that all numbers occur at exactly one place in the segment directory is a good indication
| |
| * that the whole Collatz graph can be covered by the right part of the segment directory,
| |
| * that there are no cycles in the graph, and
| |
| * that it really has the form of a tree.
| |
| | |
| Any number ''n'', be it a start value or a
| |