OEIS/3x+1 Levels: Difference between revisions
Jump to navigation
Jump to search
imported>Gfis disroot shorts |
imported>Gfis No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
< previous part: [[OEIS/3x%2B1_Connectivity]] | < previous part: [[OEIS/3x%2B1_Connectivity]] ^ up: [[OEIS/3x%2B1_Problem]] | ||
---- | ---- | ||
== | ===Segments lengths=== | ||
The | The '''length''' of a compressed segment is the number of nodes in its right part. The following lengths occur: | ||
* 1 if the segment is constructed by a single ''µµ'' operation only, for left sides ''i ≡ 0, 2 mod 3'' - a '''short''' segment. Such segments are targeted by rule 5 only. | |||
* 3 if the segment is constructed by the 3 operation sequences ''µµ, µµδ, µµσ'' only, for left sides ''i ≡ 1 mod 3'' - a '''medium''' segment. Such segments are targeted by rules 5 and 6 only. | |||
* 5, 7 ... otherwise, also for left sides ''i ≡ 1 mod 3'' - a '''variable''' segment. Such segments are targeted by rules >= 5. Rules >= 9 always target such a variable segment. | |||
''Medium'' and ''variable'' segments are '''longer''' than ''short'' ones. | |||
===Short segments attach to longer segments=== | |||
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. | |||
= | |||
=== | |||
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 | |||
* Source segments with rules 6 and higher are attached to target segments ''3*m + 1'' which are | |||
* 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. | ||
===Medium segments attach to a segment in D or a variable one=== | |||
We examine left sides ''i ≡ 1 mod 3'', but we exclude segment (the root) for the moment. We are concerned with the cases where rules 5 or 6 are applicable, since otherwise the target is variable. | |||
As above, we start with rule 5: | |||
i ≡ 1 mod 3 and i = 4*k + 3 and i > 1 => i ≡ 7 mod 12'' = 7, 19, 31, 43 ... | |||
=> k = 1, 4, 7, 10 ... => targets 2, 5, 8, 11 ... => n ≡ 2 mod 3, | |||
Therefore these targets are short and already in D. | |||
For rule 6 we have: | |||
i ≡ 1 mod 3 and i = 4*k + 1 and i > 1 => i ≡ 1 mod 12'' = 13, 25, 37, 49 ... | |||
=> k = 3, 6, 9, 12 ... => targets (3*k + 1) = 10, 19, 28, 37 ... => n ≡ 1 mod 9 and n > 1 | |||
I rule 5 applies for this target, then it is already in D. If some rule >= 9 applies, the claim of this section is also true. We are left with the cases where rule 6 is applicable again: | |||
i ≡ 1 mod 9 and i = 4*k + 1 and i > 1 => i ≡ 1 mod 36'' = 37, 73, 109, 145 ... | |||
=> k = 9, 18, 27, 36 ... => targets (3*k + 1) = 28, 55, 82, 109 ... => n ≡ 1 mod 27 and n > 1 | |||
==Collisions== | |||
==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. | |||
The '''root''' of such a node with degree > 0 is ''i'' in the formulas above. | |||
====Degree 4 === | |||
Segments with left sides of degree 4 occur at index (compressed left side) 130, 346, ... in steps of 216. The rule is always 9 which is decreasing. | |||
=== Degree 3 ==== | |||
Nodes with degree 3 and even roots occur at index 58, 130, ... in steps of 72. Their rule is 9 which is decreasing. | |||
Odd roots occur at index 22, 94, ... in steps of 72 with the increasing rule 10. For roots 1, 5, 9, 11 ... the target's rule is 6, 5, 6, 5 ... alternating. We are left with nodes of degree 3 and roots 3, 7, 11, 15, ... | |||
---- | ---- | ||
< previous part: [[OEIS/3x%2B1_Connectivity]] | < previous part: [[OEIS/3x%2B1_Connectivity]] ^ up: [[OEIS/3x%2B1_Problem]] | ||
Latest revision as of 20:03, 12 August 2019
< previous part: OEIS/3x+1_Connectivity ^ up: OEIS/3x+1_Problem
Segments lengths
The length of a compressed segment is the number of nodes in its right part. The following lengths occur:
- 1 if the segment is constructed by a single µµ operation only, for left sides i ≡ 0, 2 mod 3 - a short segment. Such segments are targeted by rule 5 only.
- 3 if the segment is constructed by the 3 operation sequences µµ, µµδ, µµσ only, for left sides i ≡ 1 mod 3 - a medium segment. Such segments are targeted by rules 5 and 6 only.
- 5, 7 ... otherwise, also for left sides i ≡ 1 mod 3 - a variable segment. Such segments are targeted by rules >= 5. Rules >= 9 always target such a variable segment.
Medium and variable segments are longer than short ones.
Short segments attach to longer segments
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.
Medium segments attach to a segment in D or a variable one
We examine left sides i ≡ 1 mod 3, but we exclude segment (the root) for the moment. We are concerned with the cases where rules 5 or 6 are applicable, since otherwise the target is variable. As above, we start with rule 5:
i ≡ 1 mod 3 and i = 4*k + 3 and i > 1 => i ≡ 7 mod 12 = 7, 19, 31, 43 ... => k = 1, 4, 7, 10 ... => targets 2, 5, 8, 11 ... => n ≡ 2 mod 3,
Therefore these targets are short and already in D.
For rule 6 we have:
i ≡ 1 mod 3 and i = 4*k + 1 and i > 1 => i ≡ 1 mod 12 = 13, 25, 37, 49 ... => k = 3, 6, 9, 12 ... => targets (3*k + 1) = 10, 19, 28, 37 ... => n ≡ 1 mod 9 and n > 1
I rule 5 applies for this target, then it is already in D. If some rule >= 9 applies, the claim of this section is also true. We are left with the cases where rule 6 is applicable again:
i ≡ 1 mod 9 and i = 4*k + 1 and i > 1 => i ≡ 1 mod 36 = 37, 73, 109, 145 ... => k = 9, 18, 27, 36 ... => targets (3*k + 1) = 28, 55, 82, 109 ... => n ≡ 1 mod 27 and n > 1
Collisions
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. The root of such a node with degree > 0 is i in the formulas above.
=Degree 4
Segments with left sides of degree 4 occur at index (compressed left side) 130, 346, ... in steps of 216. The rule is always 9 which is decreasing.
Degree 3 =
Nodes with degree 3 and even roots occur at index 58, 130, ... in steps of 72. Their rule is 9 which is decreasing. Odd roots occur at index 22, 94, ... in steps of 72 with the increasing rule 10. For roots 1, 5, 9, 11 ... the target's rule is 6, 5, 6, 5 ... alternating. We are left with nodes of degree 3 and roots 3, 7, 11, 15, ...
< previous part: OEIS/3x+1_Connectivity ^ up: OEIS/3x+1_Problem