OEIS/3x+1 Levels: Difference between revisions
Jump to navigation
Jump to search
imported>Gfis No edit summary |
imported>Gfis disroot shorts |
||
| Line 2: | Line 2: | ||
---- | ---- | ||
==Attachment rules== | ==Attachment rules== | ||
The following table '''(T4)''' tells the computation rules for the target position, depending on the modularity condition of the compressed source segment, and listed by increasing column number. We identify and denote these attachment rules by the target column number. We show the first segments (their left side) for ''k = 0, 1, 2, 3''. | The following table '''(T4)''' tells the computation rules for the target position, depending on the modularity condition of the compressed source segment, and listed by increasing column number. We identify and denote these attachment rules by the target column number. We show the first segments (their left side) for ''k = 0, 1, 2, 3''. The formulas are rearrangements of the formulas in table T1. | ||
<!--Generated with | <!--Generated with | ||
<a href="https://github.com/gfis/fasces/blob/master/oeis/collatz/attachtab.pl" target="_blank">segment.pl</a> | <a href="https://github.com/gfis/fasces/blob/master/oeis/collatz/attachtab.pl" target="_blank">segment.pl</a> | ||
at 2019-08-09 | at 2019-08-09 13:01:09;--> | ||
{| class="wikitable" style="text-align:left" | {| class="wikitable" style="text-align:left" | ||
|- | |- | ||
!Rule /<br>column!!Source<br>segments !!First source<br>segments!!Target<br>segments!!First target<br>segments!!Dir. | !Rule /<br>column!!Source<br>segments !!First source<br>segments!!Target<br>segments!!First target<br>segments!!Dir. | ||
|- | |- | ||
|'''5'''||2<sup>0</sup>( | |'''5'''||2<sup>0</sup>*(4*k + 3) ||3, 7, 11, 15||3<sup>0</sup>*k + 1 ||1, 2, 3, 4||< | ||
|- | |- | ||
|'''6'''||2<sup>0</sup>( | |'''6'''||2<sup>0</sup>*(4*k + 1) ||1, 5, 9, 13||3<sup>1</sup>*k + 1||1, 4, 7, 10||< | ||
|- | |- | ||
|'''9'''||2<sup>1</sup>( | |'''9'''||2<sup>1</sup>*(4*k + 1) ||2, 10, 18, 26||3<sup>1</sup>*k + 1||1, 4, 7, 10||< | ||
|- | |- | ||
|'''10'''||2<sup>1</sup>( | |'''10'''||2<sup>1</sup>*(4*k + 3) ||6, 14, 22, 30||3<sup>2</sup>*k + 7||7, 16, 25, 34||'''>''' | ||
|- | |- | ||
|'''13'''||2<sup>2</sup>( | |'''13'''||2<sup>2</sup>*(4*k + 3) ||12, 28, 44, 60||3<sup>2</sup>*k + 7||7, 16, 25, 34||< | ||
|- | |- | ||
|'''14'''||2<sup>2</sup>( | |'''14'''||2<sup>2</sup>*(4*k + 1) ||4, 20, 36, 52||3<sup>3</sup>*k + 7||7, 34, 61, 88||'''>''' | ||
|- | |- | ||
|'''17'''||2<sup>3</sup>( | |'''17'''||2<sup>3</sup>*(4*k + 1) ||8, 40, 72, 104||3<sup>3</sup>*k + 7||7, 34, 61, 88||< | ||
|- | |- | ||
|'''18'''||2<sup>3</sup>( | |'''18'''||2<sup>3</sup>*(4*k + 3) ||24, 56, 88, 120||3<sup>4</sup>*k + 61||61, 142, 223, 304||'''>''' | ||
|- | |- | ||
|'''21'''||2<sup>4</sup>( | |'''21'''||2<sup>4</sup>*(4*k + 3) ||48, 112, 176, 240||3<sup>4</sup>*k + 61||61, 142, 223, 304||'''>''' | ||
|- | |- | ||
|'''22'''||2<sup>4</sup>( | |'''22'''||2<sup>4</sup>*(4*k + 1) ||16, 80, 144, 208||3<sup>5</sup>*k + 61||61, 304, 547, 790||'''>''' | ||
|- | |- | ||
|...||...||...||...||...||... | |...||...||...||...||...||... | ||
| Line 42: | Line 42: | ||
A compressed segement is '''short''' if it is built by a ''µµ'' operation only (they have index ''i ≡ 0, 2 mod 3''), while all other segments (''i ≡ 1 mod 3'') are '''long'''. | A compressed segement is '''short''' if it is built by a ''µµ'' operation only (they have index ''i ≡ 0, 2 mod 3''), while all other segments (''i ≡ 1 mod 3'') are '''long'''. | ||
In a first step we show that all short segments can be moved from subset E to D since they can be attached to a long segment. | In a first step we show that all short segments can be moved from subset E to D since they can be attached to a long segment: | ||
* Source segments with rules 6 and higher are attached to target segments ''3*m + 1'' which are long by definition. | |||
* Rule 5 attaches segments with ''LS = 4*k + 3'' to target segments ''k + 1''. We distinguish 3 cases: | |||
** For ''k = 3*m'' the target is ''3*m + 1'' and therefore long. | |||
** For ''k = 3*m + 1'' the source has ''LS = 4*(3*m + 1) + 3 = 12*m + 7'', which is not short, so rule 5 never applies to these. | |||
** For ''k = 3*m + 2'' the target is ''3*(m + 1)'', to which we attach the source segment, and make it the new source ''3*n''. Then we look for the next target and find that either: | |||
*** a rule >= 6 applies which leads to a long segment, or | |||
*** rule 5 is applicable for a source ''3*n'' which also leads to a long segment. | |||
In total, E no longer contains short segments, since they were all disrooted and moved to D. | |||
---- | ---- | ||
< previous part: [[OEIS/3x%2B1_Connectivity]] ^ up: [[OEIS/3x%2B1_Problem]] | < previous part: [[OEIS/3x%2B1_Connectivity]] ^ up: [[OEIS/3x%2B1_Problem]] | ||
Revision as of 12:21, 9 August 2019
< previous part: OEIS/3x+1_Connectivity ^ up: OEIS/3x+1_Problem
Attachment rules
The following table (T4) tells the computation rules for the target position, depending on the modularity condition of the compressed source segment, and listed by increasing column number. We identify and denote these attachment rules by the target column number. We show the first segments (their left side) for k = 0, 1, 2, 3. The formulas are rearrangements of the formulas in table T1.
| Rule / column |
Source segments |
First source segments |
Target segments |
First target segments |
Dir. |
|---|---|---|---|---|---|
| 5 | 20*(4*k + 3) | 3, 7, 11, 15 | 30*k + 1 | 1, 2, 3, 4 | < |
| 6 | 20*(4*k + 1) | 1, 5, 9, 13 | 31*k + 1 | 1, 4, 7, 10 | < |
| 9 | 21*(4*k + 1) | 2, 10, 18, 26 | 31*k + 1 | 1, 4, 7, 10 | < |
| 10 | 21*(4*k + 3) | 6, 14, 22, 30 | 32*k + 7 | 7, 16, 25, 34 | > |
| 13 | 22*(4*k + 3) | 12, 28, 44, 60 | 32*k + 7 | 7, 16, 25, 34 | < |
| 14 | 22*(4*k + 1) | 4, 20, 36, 52 | 33*k + 7 | 7, 34, 61, 88 | > |
| 17 | 23*(4*k + 1) | 8, 40, 72, 104 | 33*k + 7 | 7, 34, 61, 88 | < |
| 18 | 23*(4*k + 3) | 24, 56, 88, 120 | 34*k + 61 | 61, 142, 223, 304 | > |
| 21 | 24*(4*k + 3) | 48, 112, 176, 240 | 34*k + 61 | 61, 142, 223, 304 | > |
| 22 | 24*(4*k + 1) | 16, 80, 144, 208 | 35*k + 61 | 61, 304, 547, 790 | > |
| ... | ... | ... | ... | ... | ... |
Enrooted and disrooted sets
We want to combine all segments such that they form a single tree with root 4 (or 1 in the compressed case). We define two sets:
- The enrooted set E enumerates all segments for which it is still unknown how they should be attached to other segments. E contains all segments from the segment directory in the beginning.
- The disrooted set D' enumerates all segments which have a known attachment rule, target segment and column where they can be attached. D is empty in the beginning.
We now proceed by describing steps which attach some subset of E to another subset of D. Each step will reduce the number of segments remaining in E. E in infinite, so such reductions may not help much at first sight. Our goal is, however, to end up with subsets in E which can be "summed up", that is we want to find chains of compressed segments c1 = 4, ci1, ci2, ci3, ... where any ci can be attached to the previous one.
Attachment of short segments
A compressed segement is short if it is built by a µµ operation only (they have index i ≡ 0, 2 mod 3), while all other segments (i ≡ 1 mod 3) are long.
In a first step we show that all short segments can be moved from subset E to D since they can be attached to a long segment:
- Source segments with rules 6 and higher are attached to target segments 3*m + 1 which are long by definition.
- Rule 5 attaches segments with LS = 4*k + 3 to target segments k + 1. We distinguish 3 cases:
- For k = 3*m the target is 3*m + 1 and therefore long.
- For k = 3*m + 1 the source has LS = 4*(3*m + 1) + 3 = 12*m + 7, which is not short, so rule 5 never applies to these.
- For k = 3*m + 2 the target is 3*(m + 1), to which we attach the source segment, and make it the new source 3*n. Then we look for the next target and find that either:
- a rule >= 6 applies which leads to a long segment, or
- rule 5 is applicable for a source 3*n which also leads to a long segment.
In total, E no longer contains short segments, since they were all disrooted and moved to D.
< previous part: OEIS/3x+1_Connectivity ^ up: OEIS/3x+1_Problem