OEIS/3x+1 Levels: Difference between revisions
Jump to navigation
Jump to search
imported>Gfis disroot shorts |
imported>Gfis No edit summary |
||
| Line 33: | Line 33: | ||
|- | |- | ||
|} | |} | ||
=== | ===Attachment process=== | ||
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: | 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 '''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. | * 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 | We now proceed by describing a process which attaches source segments from some subset of E to D. In each step, we | ||
* consider the source segment which are still in E, | |||
* and which have some property, | |||
* and delete those in E and add them to D. | |||
Each step will reduce the number of segments remaining in E. The process does not care whether the target segment is still in E, or already in D. | |||
=== | E is infinite, so such reductions may not help much at first sight. Our goal is, however, to find subsets in E which can be "summed up", that is we look for infinite chains of segments ''s<sub>i1</sub>, s<sub>i2</sub>, s<sub>i3</sub>, ... '' where any ''s<sub>i</sub>'' can be attached to the previous one. For such chains we could move all segments except the ''s<sub>i1</sub>'' from E to D. | ||
A compressed | |||
===Short segments=== | |||
A compressed segment is termed | |||
* '''short''' if it is built by a ''µµ'' operation only (''i ≡ 0, 2 mod 3''), | |||
* '''longer''' for ''i ≡ 1 mod 3''. | |||
* '''medium''' if it is built by ''µµ, µµδ, µµσ '' operations only, and | |||
* '''long''' if it is ''longer'' but not ''medium''. | |||
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 | In a first step of the attachment process we show that all short segments can be moved from subset E to D since they can be attached to a longer segment: | ||
* Source segments with rules 6 and higher are attached to target segments ''3*m + 1'' which are | * Source segments with rules 6 and higher are attached to target segments ''3*m + 1'' which are longer by definition. | ||
* Rule 5 attaches segments with ''LS = 4*k + 3'' to target segments ''k + 1''. We distinguish 3 cases: | * 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 | ** For ''k = 3*m'' the target is ''3*m + 1'' and therefore longer. | ||
** 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 + 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: | ** 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 | *** a rule >= 6 applies which leads to a longer segment, or | ||
*** rule 5 is applicable for a source ''3*n'' which also leads to a | *** rule 5 is applicable for a source ''3*n'' which also leads to a longer segment. | ||
In total, E no longer contains short segments, since they were all disrooted and moved to D. | In total, E no longer contains short segments, since they were all disrooted and moved to D. | ||
===Degrees of nodes=== | |||
The '''degree''' of a node is the maximum number of possible nestings of the form ''6*i - 2'' in the number: | |||
* 0 if the number is not of the form ''6*i - 2'' (white), | |||
* 1 if the number is of the form ''6*i - 2'' (yellow), | |||
* 2 if the number is of the form ''6*(6*i - 2) - 2'' (orange), | |||
* 3 if the number is of the form ''6*(6*(6*i - 2) - 2) - 2'' (light red), | |||
* 4 if the number is of the form ''6*(6*(6*(6*i - 2) - 2) - 2) - 2'' (dark red). | |||
In the segment directories we use warm colors to indicate the degrees. | |||
===Medium Segments=== | |||
===Long segments with only degree 0 in right part=== | |||
If we exclude ''m = 0'' to avoid the first (root) segment containing 1, then these segments have left sides ''9*m + 1'' (10, 19, 27, ...). The left side of every second of them has degree 1. Their highest column is always 9. Rule 5 applies only to the segments of the form ''27*m + 19'' | |||
---- | ---- | ||
< 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 14:05, 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 | > |
| ... | ... | ... | ... | ... | ... |
Attachment process
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 a process which attaches source segments from some subset of E to D. In each step, we
- consider the source segment which are still in E,
- and which have some property,
- and delete those in E and add them to D.
Each step will reduce the number of segments remaining in E. The process does not care whether the target segment is still in E, or already in D.
E is infinite, so such reductions may not help much at first sight. Our goal is, however, to find subsets in E which can be "summed up", that is we look for infinite chains of segments si1, si2, si3, ... where any si can be attached to the previous one. For such chains we could move all segments except the si1 from E to D.
Short segments
A compressed segment is termed
- short if it is built by a µµ operation only (i ≡ 0, 2 mod 3),
- longer for i ≡ 1 mod 3.
- medium if it is built by µµ, µµδ, µµσ operations only, and
- long if it is longer but not medium.
In a first step of the attachment process we show that all short segments can be moved from subset E to D since they can be attached to a longer segment:
- Source segments with rules 6 and higher are attached to target segments 3*m + 1 which are longer 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 longer.
- 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 longer segment, or
- rule 5 is applicable for a source 3*n which also leads to a longer segment.
In total, E no longer contains short segments, since they were all disrooted and moved to D.
Degrees of nodes
The degree of a node is the maximum number of possible nestings of the form 6*i - 2 in the number:
- 0 if the number is not of the form 6*i - 2 (white),
- 1 if the number is of the form 6*i - 2 (yellow),
- 2 if the number is of the form 6*(6*i - 2) - 2 (orange),
- 3 if the number is of the form 6*(6*(6*i - 2) - 2) - 2 (light red),
- 4 if the number is of the form 6*(6*(6*(6*i - 2) - 2) - 2) - 2 (dark red).
In the segment directories we use warm colors to indicate the degrees.
Medium Segments
Long segments with only degree 0 in right part
If we exclude m = 0 to avoid the first (root) segment containing 1, then these segments have left sides 9*m + 1 (10, 19, 27, ...). The left side of every second of them has degree 1. Their highest column is always 9. Rule 5 applies only to the segments of the form 27*m + 19
< previous part: OEIS/3x+1_Connectivity ^ up: OEIS/3x+1_Problem