OEIS/3x+1 Intro
< up: OEIS/3x+1_Problem > next part: OEIS/3x+1_Segments
Abstract
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 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.
Da sieht man den Wald vor lauter Bämen nicht.
German proverb: You cannot see the wood for the trees.
References
- Jeffry C. Lagarias, Ed.: The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010, ISBN 978-8218-4940-8. MBK78
- OEIS A070165: 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, 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 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):
| 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 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 ]
< up: OEIS/3x+1_Problem > next part: OEIS/3x+1_Segments