OEIS/3x+1 Problem: Difference between revisions

From tehowiki
Jump to navigation Jump to search
imported>Gfis
start
imported>Gfis
compressed segments
Line 19: Line 19:
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.
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.


It is convenient to use abbreviations for the elementary operations which transform a node x into y:
It is convenient to use abbreviations for the elementary operations which transform a node (element, number) x into y:


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
Line 28: Line 28:
| x u y  || up        || -1            ||  y = 3 * x + 1          || (none)               
| x u y  || up        || -1            ||  y = 3 * x + 1          || (none)               
|-
|-
| x δ y|| divide    || +1 ||  y = (x - 1) / 3        || x ≡ 1 mod 3     
| x δ y || divide    || +1 ||  y = (x - 1) / 3        || x ≡ 1 mod 3     
|-
|-
| x µ y || multiply || +1 ||  y = x * 2              || (none)
| x µ y || multiply   || +1 ||  y = x * 2              || (none)
|}
|}
When moving towards the root (4) of the graph, d/u operations are used, while δ/µ operations are used to move away from the root.
When moving towards the root (4) of the graph, d/u operations are used, while δ/µ operations are used to move away from the root.
====Railway construction rules====
====Detailled Segment====
* For the ''northern track'':
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 x ≡ 4 mod 6. Then they split into a ''northern'' and a ''southern'' subsegment by applying the following operations:
** µµ leading to town y = 4 * x, then
* northern: µ µ δ µ δ µ δ ...
** δ (if present) µ leading to town z (which, compared with y, has one factor 3 replaced by 2),
* southern: δ µ µ δ µ δ µ ...
** additional δµ paths visiting other towns as long as δ is possible.
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 δ operation is not 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.
We will call these segments ''detailled'', 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]. We will later come back to more properties of detailled segments.  
====Connectivity for villages====


====Compressed Segements====
For the moment we will concentrate on the nodes x ≡ 4 mod 6 in the detailled segments (which are highlighted in the directory). For each segment we define a row i in an array C[i,j] as follows:
{| class="wikitable" style="text-align:center"
!C[i,1] !! C[i,2] !! C[i,3] !! C[i,4] !! C[i,5] !! C[i,6] !! C[i,7] !! ...         
|-
| 6*i-2
| C[i,1] µµ 
| C[i,1] δµµ 
| C[i,2] δµ 
| C[i,2] δµ 
| C[i,3] δµ 
| C[i,3] δµ 
|...
|}
The row for the compressed segment is filled as long as the corresponding node in the detailled segment is ≡ 4 mod 6.
====Street construction rules====
====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:
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:

Revision as of 20:27, 18 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 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.

It is convenient to use abbreviations for the elementary operations which transform a node (element, number) x into y:

Name Mnemonic Distance to 4 Neighbour location Condition
x d y down -1 y = x / 2 x ≡ 0 mod 2
x u y up -1 y = 3 * x + 1 (none)
x δ y divide +1 y = (x - 1) / 3 x ≡ 1 mod 3
x µ y multiply +1 y = x * 2 (none)

When moving towards the root (4) of the graph, d/u operations are used, while δ/µ operations are used to move away from the root.

Detailled Segment

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 x ≡ 4 mod 6. Then they split into a northern and a southern subsegment by applying the following operations:

  • northern: µ µ δ µ δ µ δ ...
  • southern: δ µ µ δ µ δ µ ...

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 δ operation is not possible.

We will call these segments detailled, and a segment directory can easily be created by a Perl program. We will later come back to more properties of detailled segments.

Compressed Segements

For the moment we will concentrate on the nodes x ≡ 4 mod 6 in the detailled segments (which are highlighted in the directory). For each segment we define a row i in an array C[i,j] as follows:

C[i,1] C[i,2] C[i,3] C[i,4] C[i,5] C[i,6] C[i,7] ...
6*i-2 C[i,1] µµ C[i,1] δµµ C[i,2] δµ C[i,2] δµ C[i,3] δµ C[i,3] δµ ...

The row for the compressed segment is filled as long as the corresponding node in the detailled segment is ≡ 4 mod 6.

Street construction rules

The following table shows the rules for the construction of the first 9 columns S[n,1..9] of row n (n = 1, 2, 3 ...) in the street directory:

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.

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.
  • At the starting values 4, 40, 364, 3280, 29524 (OEIS A191681) the street lengths have high values 5, 9, 13, 17, 21 which did not occur before. Those starting values are (9n+1 - 1) / 2, or 4 * Sum(9i, 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:

r1 ≡ 4 mod 6 ≡ 4,10,16,22 mod 24
r2 ≡ 1 mod 2 all odd numbers
r3 ≡ 8 mod 12 ≡ 8,20 mod 24
r4 ≡ 2 mod 4 ≡ 2,6,10,14,18,22 mod 24
r5 ≡ 16 mod 24 ≡ 16 mod 24
r6 ≡ 4 mod 8 ≡ 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:

start value clamp value
4 4
40 76
364 2308
3280 143248

Subset table S

We may build derived table from the table of streets. We take columns r0 and r5 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:

  • s2 is always s0 * 4 - 1.
  • When s2 ≡ 0 mod 3, the following columns s3, s4 ... are obtained by an alternating sequence of steps
    • si+1 = si / 3 and
    • si+2 = si+1 * 2,
    • until all factors 3 in s2 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:

ss ≡ 3 mod 4 half of the odd numbers
s3 ≡ 1 mod 4 other half of odd numbers
s4 ≡ 2 mod 8 ≡ 2,10 mod 16
s5 ≡ 6 mod 8 ≡ 6,14 mod 16
s6 ≡ 12 mod 16 ≡ 12 mod 16
s7 ≡ 4 mod 16 ≡ 4 mod 16
s8 ≡ 8 mod 32 8, 40, 72, ...
s9 ≡ 24 mod 32 24, 56, 88, ...
s10 ≡ 48 mod 64 48, 112, 176, 240 ...
s11 ≡ 16 mod 64 16, 80, ...

This shows that the columns s4 ... s7 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 s8 resp. s9, half of the multiples of 16 are in s10 resp. s11 but ≡ 0,32 mod 64 are missing, etc.

Since s2 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 s0 = 13 rather quickly, but the first 27 completely filled rows involve start numbers s0 up to 1539, and for the first 4831 rows, start values up to 4076811 are involved.