OEIS/3x+1 Problem: Difference between revisions

From tehowiki
Jump to navigation Jump to search
imported>Gfis
Connectivity
imported>Gfis
detailed graph
Line 110: Line 110:
* There is no limit on the length of a segment.
* 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.
: 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 proposition:
Therefore we can continue the modulus table above indefinitely, which leads us to the claim:
* '''All numbers of the form 6 * n - 2 occur exactly once''' in the right part <nowiki>C[i,j], j &gt; 1</nowiki> of the segment directory.
* '''All numbers of the form 6 * n - 2 occur exactly once''' in the right part <nowiki>C[i,j], j &gt; 1</nowiki> of the segment directory.
===Connectivity===
===Connectivity===
We now aim to build a (directed) tree with nodes of the form 6 * n - 2. We take the segment starting at 4:
We now aim to build a (directed) tree with nodes of the form 6 * n - 2. We take the segment starting at 4:
  16 4 10
  4 -&gt; 16 -&gt; 4 -&gt; 10
and for at node x in the right part (x &gt; 4) we connect the segment starting with x to the current segment. We repeat this process iteratively. There are two questions:
and for any node x in the right part (x &gt; 4) we connect the segment starting with x with the current segment. We repeat this process for all additionally connected segments.
* Will we run into cycles?
4 -&gt; 16 -&gt; 4 -&gt; 10
: No, since a cyle would have a node which is entered by two edges, which violates the uniqueness of the nodes in the right part of the segment directory.  
      |          |
* Will we use all segments?
      V          V
: Yes. Suppose otherwise that there is a minimal number which is never reached (an example could be 82 which takes very long to show up).
      64 -&gt; 256  40 -&gt; 160 -&gt; 52 -&gt; 106 -&gt; 34 -&gt; 70 -&gt; 22 -&gt; 46
 
      ...
 
* The process does not reach a cycle.
. We will
: A cyle would contain a node which is entered by two edges. That would violate the uniqueness of the nodes in the right part of the segment directory.  
* The process will never stop.
: All nodes added by a segment are different from those already in the tree.
* The process reaches all segments.
: (This is not shown so far.)
===Collatz Tree===
===Collatz Tree===
Obviously we can replace all compressed segments by the corresponding detailed segments. The claim is that this will lead to the Collatz tree which reaches all numbers.
Once the coverage and the connectivity and cycle-freeness of the segments is established, it is easy to switch back to the full Collatz graph and prove that it is a tree (except for the trivial cycle 4-2-1). We feaze the segment, and we list the intermediate results of the operations in two separate paths:
 
  6*i-2 &micro;  &micro;&micro; &micro;&micro;&delta; &micro;&micro;&delta;&micro; &micro;&micro;&delta;&micro;&delta; &micro;&micro;&delta;&micro;&delta;&micro; ...
In the directory of detailed segments we see that we can quickly get reach all odd numbers:
      &delta;  &delta;&micro&delta;&micro;&micro; &delta;&micro;&micro;&delta; &delta;&micro;&micro;&delta;&micro; &delta;&micro;&micro;&delta;&micro;&delta; ...
  <nowiki>C[i,1]</nowiki> &delta; = ((6*i-2) - 1) / 3 = 2*i - 1 : 1, 3, 5, 7
We list the resulting subpaths in two rows, and we call this subset graph a ''detailed segment'' (in contrast to the ''compressed segments'' described above), and a '''[http://www.teherba.org/fasces/oeis/collatz/rails.html detailed segment directory]''' can easily be created by a [https://github.com/gfis/fasces/blob/master/oeis/collatz/collatz_rails.pl Perl program].
 
: This straightforward construction of the detailed segments introduces some unpleasant duplications of nodes in the right part. Later we simply suppress such duplicated nodes.
We remain concerned with the numbers
From a segment start of the form 6 * i - 2 we reach the numbers x according to the following table:
  x &#x2261; 0,2 mod 6 resp. x &#x2261; 0, 2, 6, 8, 12, 14, 18, 20 mod 24
The following table lists the operations which are necessary to reach most of these by starting at <nowiki>C[i,1]</nowiki>:
{| class="wikitable" style="text-align:left"                                                     
{| class="wikitable" style="text-align:left"                                                     
|-       
|-       
!Operation !! Expression || Result              !! Condition            !! Coverage
! Number                  !! Operation    !! Remark
|-  
|-  
| &micro;   || (6*i-2)*2 || 12*i - 4          ||                      || 8, 20 mod 24
| x &#x2261; 1, 3, 5 mod 6 || (6 * i - 2) &delta; = 2 * i - 1      || all odd numbers
|-                                                                             
|-                                                                             
| &delta;&micro;  || ((6*i-2-1)/3)*2 || 4*i - 2 ||                   || 2, 6, 10, 14, 18, 22 mod 24
| x &#x2261; 0 mod 6      || (3<sup>p</sub>) &micro;<sup>q</sup> || odd multiples of 3 times powers of 2
|-                                                                             
|-                                                                             
| &delta;&micro;&micro;  || (6*i-2-1)/3*2*2 || 8*i - 4 || i &#x2261; 2 mod 3 || 12 mod 24
| x &#x2261; 8 mod 12      || (6 * i - 2) &micro; || 8, 20, 32, 44, ...
|-                                                                              
| x &#x2261; 2 mod 12      || (6 * i - 2) &delta;&micro; if i &#x2261; 1 mod 3 || 2, 14, 26, 38, ...
|-                                                                                 
|-                                                                                 
|}
|}
The multiples of 12 can be reached from the multiples of 3 (contained in the odd numbers) by a &micro;&micro; operation.
Together this shows that we can reach all numbers &#x2261; 0, 1, 2, 3, 5 mod 6 which are not contained in the right part of the compressed segment directory.
----
We will now construct special portions of paths in the Collatz graph which we call ''segments''. They lead away from the root, and they always start with a node m &#x2261; 4 mod 6. Then they split into a ''northern'' and a ''southern'' subsegment by applying the following operations:
* northern: &micro; &micro; &delta; &micro; &delta; &micro; &delta; ...
* southern: &delta; &micro; &micro; &delta; &micro; &delta; &micro; ...
The two subsegements are built in parallel, and the process is stopped when one of the two new nodes becomes divisible by 3, resp. when a &delta; operation is not possible.


We will call these segments ''detailed'', and a '''[http://www.teherba.org/fasces/oeis/collatz/rails.html  segment directory]''' can easily be created by a [https://github.com/gfis/fasces/blob/master/oeis/collatz/collatz_rails.pl Perl program].
The connections between the segments via the nodes 6 * i - 2 remain unaffected.

Revision as of 21:48, 20 September 2018

Introduction

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 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.

References

Collatz Graph

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.

When m ≡ 0 mod 3, the path will continue with duplications only, since these maintain the divisibility by 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 be concerned with this cycle, and we start with node 4, the root.

Graph Operations

Following Trümper, we use abbreviations for the elementary operations which transform a node (element, number) in the Collatz graph:

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)
σ := δµ step +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. 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 is divisible by 3, resp. when a δ operation is no more possible. We assemble the segments as rows of an infinite array C[i,j], the so-called segment directory. One row i of C is constructed according to the following table:

Column Operation Formula Condition Sequence
C[i,1] 6 * i - 2 4, 10, 16, 22, 28, ...
C[i,2] C[i,1] µµ 24 * (i - 1) + 16 16, 40, 64, 88, 112, ...
C[i,3] C[i,1] δµµ 24 * (i - 1) / 3 + 4 i ≡ 1 mod 3 4, 28, 52, 76, 100, ...
C[i,4] C[i,2] σ 48 * (i - 1) / 3 + 10 i ≡ 1 mod 3 10, 58, 106, 134, ...
C[i,5] C[i,3] σ 48 * (i - 7) / 9 + 34 i ≡ 7 mod 9 34, 82, 130, 178, ...
C[i,6] C[i,2] σσ 96 * (i - 7) / 9 + 70 i ≡ 7 mod 9 70, 166, 262, 358, ...
C[i,7] C[i,3] σσ 96 * (i - 7) / 27 + 22 i ≡ 7 mod 27 22, 118, 214, 310, ...
C[i,8] C[i,2] σσσ 192 * (i - 7) / 27 + 46 i ≡ 7 mod 27 46, 238, 430, 622, ...
C[i,9] C[i,3] σσσ 192 * (i - 61) / 81 + 142 i ≡ 61 mod 81 142, 334, ...
... ... ... ... ...

The first column(s) C[i,1] will be denoted as the left part of the segment (or of the whole directory), while the columns C[i,j], j > 1 will be the right part.

  • All nodes in the segment directory are of the form 6 * n - 2.
This follows from the formula for columns C[i,1..3], and for any higher column numbers from the 3-by-2 replacement property of the σ operation.
  • All segments have a finite length.
At some point the σ operations will have replaced all factors 3 by 2.
  • All nodes in the right part of a segment have the same kernel.
This follows from the formula for columns C[i,1..3], and since the σ operation maintains this property.
  • All nodes in the right part of a segment are different.
For C[i,1..2] 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 (right part of segment starting with 40, kernel 1):
160 = 6 * 33 * 20 - 2
 52 = 6 * 32 * 20 - 2
106 = 6 * 32 * 21 - 2
 34 = 6 * 31 * 21 - 2
 70 = 6 * 31 * 22 - 2
 22 = 6 * 30 * 22 - 2
 46 = 6 * 30 * 23 - 2
  • There is no cycle in a segment.

Segment Lengths

The segment directories are obviously very structured. The lengths of the compressed segments follow the pattern

4 2 2 4 2 2 L1 2 2 4 2 2 4 2 2 L2 2 2 4 2 2 ...

with two fixed lengths 2 and 4 and some variable lengths L1, L2 ... > 4. At the starting values 4, 40, 364, 3280, 29524 (OEIS A191681), the segment lengths have high values 4, 8, 12, 16, 20 which did not occur before. Those starting values are (9n+1 - 1) / 2, or 4 * Sum(9i, 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:

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.

  • 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:

  • All numbers of the form 6 * n - 2 occur exactly once in the right part C[i,j], j > 1 of the segment directory.

Connectivity

We now aim to build a (directed) tree with nodes of the form 6 * n - 2. We take the segment starting at 4:

4 -> 16 -> 4 -> 10

and for any node x in the right part (x > 4) we connect the segment starting with x with the current segment. We repeat this process for all additionally connected segments.

4 -> 16 -> 4 -> 10
      |          |
      V          V
     64 -> 256  40 -> 160 -> 52 -> 106 -> 34 -> 70 -> 22 -> 46 
     ...
  • The process does not reach a cycle.
A cyle would contain a node which is entered by two edges. That would violate the uniqueness of the nodes in the right part of the segment directory.
  • The process will never stop.
All nodes added by a segment are different from those already in the tree.
  • The process reaches all segments.
(This is not shown so far.)

Collatz Tree

Once the coverage and the connectivity and cycle-freeness of the segments is established, it is easy to switch back to the full Collatz graph and prove that it is a tree (except for the trivial cycle 4-2-1). We feaze the segment, and we list the intermediate results of the operations in two separate paths:

6*i-2 µ   µµ  µµδ µµδµ µµδµδ µµδµδµ ...
      δ   δµ  δµµ δµµδ δµµδµ δµµδµδ ... 

We list the resulting subpaths in two rows, and we call this subset graph a detailed segment (in contrast to the compressed segments described above), and a detailed segment directory can easily be created by a Perl program.

This straightforward construction of the detailed segments introduces some unpleasant duplications of nodes in the right part. Later we simply suppress such duplicated nodes.

From a segment start of the form 6 * i - 2 we reach the numbers x according to the following table:

Number Operation Remark
x ≡ 1, 3, 5 mod 6 (6 * i - 2) δ = 2 * i - 1 all odd numbers
x ≡ 0 mod 6 (3p) µq odd multiples of 3 times powers of 2
x ≡ 8 mod 12 (6 * i - 2) µ 8, 20, 32, 44, ...
x ≡ 2 mod 12 (6 * i - 2) δµ if i ≡ 1 mod 3 2, 14, 26, 38, ...

Together this shows that we can reach all numbers ≡ 0, 1, 2, 3, 5 mod 6 which are not contained in the right part of the compressed segment directory.

The connections between the segments via the nodes 6 * i - 2 remain unaffected.