|
|
| (47 intermediate revisions by one other user not shown) |
| Line 1: |
Line 1: |
| previous version in [[Collatz Streetmap]]
| | A collection of considerations regarding the '''[https://en.wikipedia.org/wiki/Collatz_conjecture Collatz conjecture]'''. |
| ==Introduction==
| |
| Collatz sequences are sequences of non-negative integer numbers with a simple construction rule: even elements a 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.
| |
|
| |
|
| When we speak of ''numbers'' in this article, we normally mean natural integer numbers > 0. The zero is sometimes mentioned explicetely.
| | 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 n > 4 in the graph, the path from the root (4) can be continued
| |
| * always to n * 2, and
| |
| * sometimes also to (n - 1) / 3.
| |
| When n ≡ 0 mod 3, the path will continue with duplications only, since these maintain the divisibility by 3.
| |
| | |
| The 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 cylces.
| |
| | |
| Straightforward visualizations of the Collatz graph show no obvious structure. The sequences for the first dozen of start values seem to be rather harmless, but the sequence for 27 suddenly has 112 elements.
| |
| ==The 3x+1 Story==
| |
| Many years ago there was a big country with a ''capital'' city and infinitely many other, numbered ''locations''. The capital (with number 1) had incorporated locations 2 and 4. There were ''towns'' which had numbers of the form ''6 * n - 2'', and (less interesting) ''villages''.
| |
| ===Road net===
| |
| The country had an established net of one-way ''roads'' between the locations. Each location ''x'' had between 2 and 4 roads coming from a neighbour location or leading to one, which were named as follows:
| |
| {| class="wikitable" style="text-align:center"
| |
| !Name !! Mnemonic !! Direction !! Neighbour location !! Condition
| |
| |-
| |
| | d || down || east -> west || y = x / 2 || x ≡ 0 mod 2
| |
| |-
| |
| | u || up || east -> west || y = 3 * x + 1 || (none)
| |
| |-
| |
| | δ|| divide || west -> east || y = (x - 1) / 3 || x ≡ 1 mod 3
| |
| |-
| |
| | µ|| multiply || west -> east || y = x * 2 || (none)
| |
| |}
| |
| Some villages (those numbered x ≡ 0 mod 3) were lined up on a straight path leading to the far east. Other villages (numbered x = 2<sup>n</sup>) lay on a straight path directly leading to the capital.
| |
| ===The Problem===
| |
| During the time people in many locations found out that they could travel to the capital using this road net, but they felt not happy with it. While a path of 11 roads had to be used to travel from village 26 to the capital, people of village 27 had to use a path of 112 roads to get there. There were rumors that there were distant villages which were not connected to the road net at all. They had the same 2-4 roads, but these would form a cycle.
| |
| | |
| A better transportation network was highly desired, and there were even prizes set up for a solution. Many proposals were made, but none was accepted.
| |
| ===The Railway Proposal===
| |
| It was known that often two locations were connected to the capital by the same number of roads, for example 142 and 143 both needed a path of 104 roads, and starting at town 364, they could even use the same path.
| |
| | |
| An retired engineer had the idea to make use of this fact, and he came up with a rather strange proposal. Each town ''x'' should start to build a double-track ''railway'' alongside the road net, but only special types of roads would be followed.
| |
| ====Railway construction rules====
| |
| * For the ''northern track'':
| |
| ** µµ leading to town y = 4 * x, then
| |
| ** δ (if present) µ leading to town z (which, compared with y, has one factor 3 replaced by 2),
| |
| ** additional δµ paths visiting other towns as long as δ is possible.
| |
| * For the ''southern track'':
| |
| ** δ, which is always possible out of a town,
| |
| ** µµ leading to
| |
| *** a village ≡ 0 mod 3, in which case the construction stops, otherwise
| |
| *** a town z,
| |
| ** additional δµ paths visiting other towns as long as δ is possible.
| |
| It was obvious that such railways could be started from every town, and that there would be only a finite number of δµ paths (until all factors of 3 were exhausted).
| |
| ====Railway directory====
| |
| Therefore the engineer could attach a complete '''[http://www.teherba.org/fasces/oeis/collatz/roads.html railway directory]''' to his proposal. There, any double-track railway started at the blue town in column 1, followed in the same row by the northern track. The southern track was showed in the next row. All towns were highlighted.
| |
| | |
| The proposal also included a number of claims which should convince people that the railway net would more reliably transport them from any location to the capital.
| |
| ====Connectivity for villages====
| |
| | |
| ====Street construction rules====
| |
| The following table shows the rules for the construction of the first 9 columns <nowiki>S[n,1..9]</nowiki> of row n (n = 1, 2, 3 ...) in the street directory:
| |
| {| class="wikitable" style="text-align:left"
| |
| |-
| |
| !Column!! Steps !! Expression || Formula !! Condition !! Coverage
| |
| |-
| |
| | 1|| || || 6n-2 || || 4,10,16,22 mod 24
| |
| |-
| |
| | 2|| d || (6n-2-1)/3 || 2n-1 || || all odd numbers
| |
| |-
| |
| | 3|| m || (6n-2)*2 || 12n-4 || || 8,20 mod 24
| |
| |-
| |
| | 4|| dm || ((6n-2-1)/3)*2 || 4n-2 || || 2,6,10,14,18,22 mod 24
| |
| |-
| |
| | 5|| mm || (6n-2)*2*2 || 24n-8 || || 16 mod 24
| |
| |-
| |
| | 6|| dmm || ((6n-2-1)/3)*2*2 || 8n-4 || || 4,12,20 mod 24
| |
| |-
| |
| | 7|| mmd || ((6n-2)*2*2-1)/3 || 8n-3 || || 5,13,21 mod 24
| |
| |-
| |
| | 8|| dmmd || ((6n-2-1)/3)*2*2-1)/3 || (8n-5)/3 || n ≡ 1 mod 3 || (1,9,17,25 ...)
| |
| |-
| |
| | 9|| mmdm || ((6n-2)*2*2-1)/3)*2 || 16n-6 || n ≡ 1 mod 3 || (10,58,106,154, ...)
| |
| |}
| |
| The first 6 columns of the table cover the odd numbers and all numbers ≡ 2,4,6,8,10,12,16,18,20,22 mod 24.
| |
| | |
| It is ''not shown'' so far that all multiples of 24 are contained in the table.
| |
| <!-- ???
| |
| All odd multiples of 3 are contained in column 2. All multiples of 24 can be reached by duplicating them 3 times (3 m-steps).
| |
| -->
| |
| ====Highlighted numbers====
| |
| The numbers of the form 6p-2 were highlighted in the example above. They have the special property that, when p > 0 and p ≡ 0 mod 3, a dm-step yields a number of the same form, but with one factor 3 in p replaced by 2:
| |
| 6(3q)-2 dm ((6(3q)-2)-1)/3*2 = (6q-1)*2 = 6(2q)-2
| |
| This implies that a dm-step decreases any number by about one third.
| |
| ====Street lengths > 7====
| |
| * Columns 4(k+1)+1 result by dm-steps from columns 4k+1 for k=1,2,... (and so do columns 4(k+1)+2 result from columns 4k+2). Sequences of dm-steps decrease the numbers. Therefore the lengths of all streets are finite.
| |
| * Column 5 is 24n-8, and the lengths depend on the power of 3 contained in that n.
| |
| <!--
| |
| * The street lengths show a repeating pattern for the start values mod 54. The fixed lengths 3, 4, 5 can probably be explained from the street construction rule.
| |
| {| class="wikitable" style="text-align:center"
| |
| | 4 mod 54
| |
| | 10 mod 54
| |
| | 16 mod 54
| |
| | 22 mod 54
| |
| | 28 mod 54
| |
| | 34 mod 54
| |
| | 40 mod 54
| |
| | 46 mod 54
| |
| | 52 mod 54
| |
| |-
| |
| | 5
| |
| | 3
| |
| | 3
| |
| | 4
| |
| | 3
| |
| | 3
| |
| | n
| |
| | 3
| |
| | 3
| |
| |}
| |
| -->
| |
| * At the starting values 4, 40, 364, 3280, 29524 ([http://oeis.org/A191681 OEIS A191681]) the street lengths have high values 5, 9, 13, 17, 21 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====
| |
| The elements of the streets are strongly interconnected, and the table "obviously" shows all positive integers which are not multiples of 24:
| |
| {| class="wikitable"
| |
| | r<sub>1</sub> ≡ 4 mod 6
| |
| | style="text-align:right" | ≡ 4,10,16,22 mod 24
| |
| |-
| |
| | r<sub>2</sub> ≡ 1 mod 2
| |
| | all odd numbers
| |
| |-
| |
| | r<sub>3</sub> ≡ 8 mod 12
| |
| | style="text-align:right" | ≡ 8,20 mod 24
| |
| |-
| |
| | r<sub>4</sub> ≡ 2 mod 4
| |
| | style="text-align:right" | ≡ 2,6,10,14,18,22 mod 24
| |
| |-
| |
| | r<sub>5</sub> ≡ 16 mod 24
| |
| | style="text-align:right" | ≡ 16 mod 24
| |
| |-
| |
| | r<sub>6</sub> ≡ 4 mod 8
| |
| | style="text-align:right" | ≡ 4,12,20 mod 24
| |
| |}
| |
| | |
| | |
| So if we can show that we reach all start values ≡ 4 mod 6, we have a proof that all positive integers are reached.
| |
| | |
| Starting with 4, it seems possible that a continuous expansion of all numbers ≡ 4 mod 6 into streets would finally yield all streets up to some start value. Experiments show that there are limits for the numbers involved. Streets above the ''clamp'' value are not necessary in order to obtain all streets below and including the ''start'' value:
| |
| {| class="wikitable"
| |
| ! start value
| |
| ! clamp value
| |
| |- style="text-align:right"
| |
| | 4 || 4
| |
| |- style="text-align:right"
| |
| | 40 || 76
| |
| |- style="text-align:right"
| |
| | 364 || 2308
| |
| |- style="text-align:right"
| |
| | 3280 || 143248
| |
| |}
| |
| ==Subset table S==
| |
| We may build derived table from the table of streets. We take columns r<sub>0</sub> and r<sub>5</sub> ff., and therein we keep the highlighted entries (those which are ≡ 4 mod 6) only, add 2 to them and divide them by 6. The resulting subset table S starts as follows:
| |
| s0 s1 s2 s3 s4 s5 s6 s7 s8 ...
| |
| n len
| |
| 1 3 3 1 2
| |
| 2 1 7
| |
| 3 1 11
| |
| 4 3 15 5 10
| |
| 5 1 19
| |
| 6 1 23
| |
| 7 7 27 9 18 6 12 4 8
| |
| 8 1 31
| |
| 9 1 35
| |
| 10 3 39 13 26
| |
| 11 1 43
| |
| 12 1 47
| |
| 13 3 51 17 34
| |
| 14 1 55
| |
| 15 1 59
| |
| 16 5 63 21 42 14 28
| |
| ...
| |
| This table can be described by simple rules which are hopefully provable from the construction rule for the streets:
| |
| * s<sub>2</sub> is always s<sub>0</sub> * 4 - 1.
| |
| * When s<sub>2</sub> ≡ 0 mod 3, the following columns s<sub>3</sub>, s<sub>4</sub> ... are obtained by an alternating sequence of steps
| |
| ** s<sub>i+1</sub> = s<sub>i</sub> / 3 and
| |
| ** s<sub>i+2</sub> = s<sub>i+1</sub> * 2,
| |
| ** until all factors 3 in s<sub>2</sub> are replaced by factors 2.
| |
| | |
| ===Does S contain all positive integers?===
| |
| The answer is yes. As above, we can regard the increments in successive columns:
| |
| {| class="wikitable"
| |
| | s<sub>s</sub> ≡ 3 mod 4
| |
| | style="text-align:right" | half of the odd numbers
| |
| |-
| |
| | s<sub>3</sub> ≡ 1 mod 4
| |
| | style="text-align:right" | other half of odd numbers
| |
| |-
| |
| | s<sub>4</sub> ≡ 2 mod 8
| |
| | style="text-align:right" | ≡ 2,10 mod 16
| |
| |-
| |
| | s<sub>5</sub> ≡ 6 mod 8
| |
| | style="text-align:right" | ≡ 6,14 mod 16
| |
| |-
| |
| | s<sub>6</sub> ≡ 12 mod 16
| |
| | style="text-align:right" | ≡ 12 mod 16
| |
| |-
| |
| | s<sub>7</sub> ≡ 4 mod 16
| |
| | style="text-align:right" | ≡ 4 mod 16
| |
| |-
| |
| | s<sub>8</sub> ≡ 8 mod 32
| |
| | style="text-align:right" | 8, 40, 72, ...
| |
| |-
| |
| | s<sub>9</sub> ≡ 24 mod 32
| |
| | style="text-align:right" | 24, 56, 88, ...
| |
| |-
| |
| | s<sub>10</sub> ≡ 48 mod 64
| |
| | style="text-align:right" | 48, 112, 176, 240 ...
| |
| |-
| |
| | s<sub>11</sub> ≡ 16 mod 64
| |
| | style="text-align:right" | 16, 80, ...
| |
| |}
| |
| This shows that the columns s<sub>4</sub> ... s<sub>7</sub> contain all numbers ≡ 2,4,6,10,12,14 mod 16, but those ≡ 0,8 mod 16 are missing so far. The ones ≡ 8 mod 16 show up in s<sub>8</sub> resp. s<sub>9</sub>, half of the multiples of 16 are in s<sub>10</sub> resp. s<sub>11</sub> but ≡ 0,32 mod 64 are missing, etc.
| |
| | |
| Since s<sub>2</sub> contains arbitray high powers of 3, S has rows of arbitrary length, and for the missing multiples of powers of 2 the exponents can be driven above all limits.
| |
| : Thus S contains all positive integers.
| |
| ===Can S be generated starting at 1?===
| |
| We ask for an iterative process which starts with the row of S for index 1:
| |
| 1: 3 1 2
| |
| Then, all additional rows for the elements obtained so far are generated:
| |
| 2: 7
| |
| 3: 11
| |
| These rows are also expanded:
| |
| 7: 27 9 18 6 12 4 8
| |
| 11: 43
| |
| Since we want to cover all indexes, we would first generate the rows for lower indexes. This process fills all rows up to s<sub>0</sub> = 13 rather quickly, but the first 27 completely filled rows involve start numbers s<sub>0</sub> up to 1539, and for the first 4831 rows, start values up to 4076811 are involved.
| |