OEIS/3x+1 Levels - Revision history

imported>Gfis at 20:03, 12 August 2019

2019-08-12T20:03:37Z

← Older revision		Revision as of 20:03, 12 August 2019
Line 31:		Line 31:
	i ≡ 1 mod 9 and i = 4*k + 1 and i > 1 => i ≡ 1 mod 36'' = 37, 73, 109, 145 ...		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		=> k = 9, 18, 27, 36 ... => targets (3*k + 1) = 28, 55, 82, 109 ... => n ≡ 1 mod 27 and n > 1
			==Collisions==

	===Degrees of nodes===		==Degrees of nodes==
	The '''degree''' of a node is the maximum number of possible nestings of the form ''6*i - 2'' in the number:		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),		* 0 if the number is not of the form ''6*i - 2'' (white),
Line 40:		Line 41:
	* 4 if the number is of the form ''6(6(6(6i - 2) - 2) - 2) - 2'' (dark red).		* 4 if the number is of the form ''6(6(6(6i - 2) - 2) - 2) - 2'' (dark red).
	In the segment directories we use warm colors to indicate the degrees.		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]]     ^ up: [[OEIS/3x%2B1_Problem]]		< previous part: [[OEIS/3x%2B1_Connectivity]]     ^ up: [[OEIS/3x%2B1_Problem]]

imported>Gfis at 15:44, 12 August 2019

2019-08-12T15:44:06Z

@@ Line 1: / Line 1: @@
-&lt; previous part: [[OEIS/3x%2B1_Connectivity]] &nbsp; &nbsp; &nbsp; &nbsp; ^ up: [[OEIS/3x%2B1_Problem]]
+&lt; previous part: [[OEIS/3x%2B1_Connectivity]] &nbsp; &nbsp; ^ up: [[OEIS/3x%2B1_Problem]]
 ----
 ===Segments lengths===
 The '''length''' of a compressed segment is the number of nodes in its right part. The following lengths occur:
@@ Line 86: / Line 42: @@
 ----
-&lt; previous part: [[OEIS/3x%2B1_Connectivity]] &nbsp; &nbsp; &nbsp; &nbsp; ^ up: [[OEIS/3x%2B1_Problem]]
+&lt; previous part: [[OEIS/3x%2B1_Connectivity]] &nbsp; &nbsp; ^ up: [[OEIS/3x%2B1_Problem]]

imported>Gfis: Medium, rule 6

2019-08-09T16:09:03Z

Medium, rule 6

← Older revision		Revision as of 16:09, 9 August 2019
Line 45:		Line 45:
	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.		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.

	===~~Short segments~~===		===Segments lengths===
	~~A compressed segment is termed~~		The '''length''' of a compressed segment is the number of nodes in its right part. The following lengths occur:
	* '''~~short~~''' if it is ~~built~~ by a ''µµ'' operation only (''i ≡ 0, 2 mod 3''),		* 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.
	* '''~~longer~~''' ~~for ''i ≡ 1 mod 3''~~.		* 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.
	* ~~'''medium'''~~ if it is ~~built~~ by ''µµ, µµδ, µµσ '' ~~operations~~ only, and		* 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.
	* '''~~long~~''' ~~if it is~~ ''longer'' ~~but not~~ ''~~medium~~''.		''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:		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.		* Source segments with rules 6 and higher are attached to target segments ''3*m + 1'' which are longer by definition.
Line 61:		Line 61:
	*** rule 5 is applicable for a source ''3*n'' which also leads to a longer segment.		*** 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

	===Degrees of nodes===		===Degrees of nodes===
Line 70:		Line 84:
	* 4 if the number is of the form ''6(6(6(6i - 2) - 2) - 2) - 2'' (dark red).		* 4 if the number is of the form ''6(6(6(6i - 2) - 2) - 2) - 2'' (dark red).
	In the segment directories we use warm colors to indicate the degrees.		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 ''9m + 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 ''27m + 19''


	----		----
	< previous part: [[OEIS/3x%2B1_Connectivity]]         ^ up: [[OEIS/3x%2B1_Problem]]		< previous part: [[OEIS/3x%2B1_Connectivity]]         ^ up: [[OEIS/3x%2B1_Problem]]

imported>Gfis at 14:05, 9 August 2019

2019-08-09T14:05:10Z

← Older revision		Revision as of 14:05, 9 August 2019
Line 33:		Line 33:
	\|-		\|-
	\|}		\|}
	===~~Enrooted and disrooted sets~~===		===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 ~~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 ''c<sub>1</sub> = 4, c<sub>i1</sub>, c<sub>i2</sub>, c<sub>i3</sub>, ... '' where any ''c<sub>i</sub>'' can be attached to the previous one~~.		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.

	===~~Attachment of short~~ segments===		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 ~~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'''.
			===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 ~~long~~ segment:		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 ~~long~~ by definition.		* 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 = 3m'' the target is ''3m + 1'' and therefore ~~long~~.		** For ''k = 3m'' the target is ''3m + 1'' and therefore longer.
	** For ''k = 3m + 1'' the source has ''LS = 4(3m + 1) + 3 = 12m + 7'', which is not short, so rule 5 never applies to these.		** For ''k = 3m + 1'' the source has ''LS = 4(3m + 1) + 3 = 12m + 7'', which is not short, so rule 5 never applies to these.
	** For ''k = 3m + 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 = 3m + 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		*** 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 ~~long~~ segment.		*** 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(6i - 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(6i - 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 ''9m + 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 ''27m + 19''


	----		----
	< previous part: [[OEIS/3x%2B1_Connectivity]]         ^ up: [[OEIS/3x%2B1_Problem]]		< previous part: [[OEIS/3x%2B1_Connectivity]]         ^ up: [[OEIS/3x%2B1_Problem]]

imported>Gfis: disroot shorts

2019-08-09T12:21:30Z

disroot shorts

← Older revision		Revision as of 12:21, 9 August 2019
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 12:09~~:03~~;-->		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>(4k + 3) \|\|3, 7, 11, 15\|\|3<sup>0</sup>k + 1 \|\|1, 2, 3, 4\|\|<		\|'''5'''\|\|2<sup>0</sup>(4k + 3) \|\|3, 7, 11, 15\|\|3<sup>0</sup>*k + 1 \|\|1, 2, 3, 4\|\|<
	\|-		\|-
	\|'''6'''\|\|2<sup>0</sup>(4k + 1) \|\|1, 5, 9, 13\|\|3<sup>1</sup>k + 1\|\|1, 4, 7, 10\|\|<		\|'''6'''\|\|2<sup>0</sup>(4k + 1) \|\|1, 5, 9, 13\|\|3<sup>1</sup>*k + 1\|\|1, 4, 7, 10\|\|<
	\|-		\|-
	\|'''9'''\|\|2<sup>1</sup>(4k + 1) \|\|2, 10, 18, 26\|\|3<sup>1</sup>k + 1\|\|1, 4, 7, 10\|\|<		\|'''9'''\|\|2<sup>1</sup>(4k + 1) \|\|2, 10, 18, 26\|\|3<sup>1</sup>*k + 1\|\|1, 4, 7, 10\|\|<
	\|-		\|-
	\|'''10'''\|\|2<sup>1</sup>(4k + 3) \|\|6, 14, 22, 30\|\|3<sup>2</sup>k + 7\|\|7, 16, 25, 34\|\|'''>'''		\|'''10'''\|\|2<sup>1</sup>(4k + 3) \|\|6, 14, 22, 30\|\|3<sup>2</sup>*k + 7\|\|7, 16, 25, 34\|\|'''>'''
	\|-		\|-
	\|'''13'''\|\|2<sup>2</sup>(4k + 3) \|\|12, 28, 44, 60\|\|3<sup>2</sup>k + 7\|\|7, 16, 25, 34\|\|<		\|'''13'''\|\|2<sup>2</sup>(4k + 3) \|\|12, 28, 44, 60\|\|3<sup>2</sup>*k + 7\|\|7, 16, 25, 34\|\|<
	\|-		\|-
	\|'''14'''\|\|2<sup>2</sup>(4k + 1) \|\|4, 20, 36, 52\|\|3<sup>3</sup>k + 7\|\|7, 34, 61, 88\|\|'''>'''		\|'''14'''\|\|2<sup>2</sup>(4k + 1) \|\|4, 20, 36, 52\|\|3<sup>3</sup>*k + 7\|\|7, 34, 61, 88\|\|'''>'''
	\|-		\|-
	\|'''17'''\|\|2<sup>3</sup>(4k + 1) \|\|8, 40, 72, 104\|\|3<sup>3</sup>k + 7\|\|7, 34, 61, 88\|\|<		\|'''17'''\|\|2<sup>3</sup>(4k + 1) \|\|8, 40, 72, 104\|\|3<sup>3</sup>*k + 7\|\|7, 34, 61, 88\|\|<
	\|-		\|-
	\|'''18'''\|\|2<sup>3</sup>(4k + 3) \|\|24, 56, 88, 120\|\|3<sup>4</sup>k + 61\|\|61, 142, 223, 304\|\|'''>'''		\|'''18'''\|\|2<sup>3</sup>(4k + 3) \|\|24, 56, 88, 120\|\|3<sup>4</sup>*k + 61\|\|61, 142, 223, 304\|\|'''>'''
	\|-		\|-
	\|'''21'''\|\|2<sup>4</sup>(4k + 3) \|\|48, 112, 176, 240\|\|3<sup>4</sup>k + 61\|\|61, 142, 223, 304\|\|'''>'''		\|'''21'''\|\|2<sup>4</sup>(4k + 3) \|\|48, 112, 176, 240\|\|3<sup>4</sup>*k + 61\|\|61, 142, 223, 304\|\|'''>'''
	\|-		\|-
	\|'''22'''\|\|2<sup>4</sup>(4k + 1) \|\|16, 80, 144, 208\|\|3<sup>5</sup>k + 61\|\|61, 304, 547, 790\|\|'''>'''		\|'''22'''\|\|2<sup>4</sup>(4k + 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 = 3m'' the target is ''3m + 1'' and therefore long.
			** For ''k = 3m + 1'' the source has ''LS = 4(3m + 1) + 3 = 12m + 7'', which is not short, so rule 5 never applies to these.
			** For ''k = 3m + 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]]

imported>Gfis at 10:11, 9 August 2019

2019-08-09T10:11:45Z

← Older revision		Revision as of 10:11, 9 August 2019
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 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''.

	~~T4 shows the nodes and formulas in uncompressed form, but the formulas for the compressed form can easily be derived by mapping ''7*i-2'' to ''i''.~~

	<!--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 10:20:02;-->		at 2019-08-09 12:09:03;-->
	{\| class="wikitable" style="text-align:left"		{\| class="wikitable" style="text-align:left"
	\|-		\|-
	!Rule /<br>column!!Source<br>segments~~\|\|Condition /<br>remaining~~!!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>(4k + 3) \|\|3, 7, 11, 15\|\|3<sup>0</sup>k + 1 \|\|1, 2, 3, 4\|\|<
	\|-		\|-
	\|'''5'''\|\|6(2<sup>0</sup>(4k + 3)) ~~- 2~~\|\|~~0 mod 8<br>2~~, 4, ~~6 mod 8\|\|16, 40, 64~~, 88\|\|6(3<sup>0</sup>k + 1 ~~) - 2~~\|\|4, 10~~, 16, 22~~\|\|<		\|'''6'''\|\|2<sup>0</sup>(4k + 1) \|\|1, 5, 9, 13\|\|3<sup>1</sup>k + 1\|\|1, 4, 7, 10\|\|<
	\|-		\|-
	\|'''6'''\|\|6(2<sup>0</sup>(4k + 1)~~) - 2~~\|\|~~4 mod 8<br>~~2~~, 6~~, 10, ~~14 mod 16\|\|4, 28~~, ~~52, 76~~\|\|6(3<sup>1</sup>k + 1~~) - 2~~\|\|4, 22, ~~40, 58~~\|\|<		\|'''9'''\|\|2<sup>1</sup>(4k + 1) \|\|2, 10, 18, 26\|\|3<sup>1</sup>k + 1\|\|1, 4, 7, 10\|\|<
	\|-		\|-
	\|'''9'''\|\|6(2<sup>1</sup>(4k + 1)~~) - 2~~\|\|~~10 mod 16<br>2,~~ 6, 14 ~~mod 16\|\|10~~, 58, ~~106, 154~~\|\|6(3<sup>1</sup>k + ~~1) - 2~~\|\|4, 22, 40, 58\|\|<		\|'''10'''\|\|2<sup>1</sup>(4k + 3) \|\|6, 14, 22, 30\|\|3<sup>2</sup>k + 7\|\|7, 16, 25, 34\|\|'''>'''
	\|-		\|-
	\|'''10'''\|\|6(2<sup>1</sup>(4k + 3)~~) - 2\|\|2 mod 16<br>6, 14, 22, 30 mod 32~~\|\|34, 82, ~~130~~, ~~178~~\|\|6(3<sup>2</sup>k + 7~~) - 2~~\|\|40, 94, ~~148~~, ~~202~~\|\|~~'''~~>~~'''~~		\|'''13'''\|\|2<sup>2</sup>(4k + 3) \|\|12, 28, 44, 60\|\|3<sup>2</sup>k + 7\|\|7, 16, 25, 34\|\|<
	\|-		\|-
	\|'''13'''\|\|6(2<sup>2</sup>(4k + 3)) ~~- 2\|\|6 mod 32<br>14, 22, 30 mod 32~~\|\|70, ~~166~~, ~~262~~, ~~358~~\|\|6(3<sup>2</sup>k + 7~~) - 2~~\|\|40, 94, ~~148~~, ~~202~~\|\|<		\|'''14'''\|\|2<sup>2</sup>(4k + 1) \|\|4, 20, 36, 52\|\|3<sup>3</sup>k + 7\|\|7, 34, 61, 88\|\|'''>'''
	\|-		\|-
	\|'''14'''\|\|6(2<sup>2</sup>(4k + 1)~~) - 2~~\|\|~~22 mod 32<br>14~~, ~~30, 46, 62 mod 64\|\|22, 118~~, ~~214~~, ~~310~~\|\|6(3<sup>3</sup>k + 7~~) - 2~~\|\|40, ~~202~~, ~~364~~, ~~526~~\|\|~~'''~~>~~'''~~		\|'''17'''\|\|2<sup>3</sup>(4k + 1) \|\|8, 40, 72, 104\|\|3<sup>3</sup>k + 7\|\|7, 34, 61, 88\|\|<
	\|-		\|-
	\|'''17'''\|\|6(2<sup>3</sup>(4k + 1)~~) - 2\|\|46 mod 64<br>14, 30, 62 mod 64~~\|\|46, ~~238~~, ~~430~~, ~~622~~\|\|6(3<sup>3</sup>k + ~~7) - 2~~\|\|40, ~~202~~, ~~364~~, ~~526~~\|\|<		\|'''18'''\|\|2<sup>3</sup>(4k + 3) \|\|24, 56, 88, 120\|\|3<sup>4</sup>k + 61\|\|61, 142, 223, 304\|\|'''>'''
	\|-		\|-
	\|'''18'''\|\|6(2<sup>3</sup>(4k + 3)~~) - 2\|\|14 mod 64<br>30, 62, 94, 126 mod 128~~\|\|~~142~~, ~~334~~, ~~526~~, ~~718~~\|\|6(3<sup>4</sup>k + 61~~) - 2~~\|\|~~364~~, ~~850~~, ~~1336~~, ~~1822~~\|\|'''>'''		\|'''21'''\|\|2<sup>4</sup>(4k + 3) \|\|48, 112, 176, 240\|\|3<sup>4</sup>k + 61\|\|61, 142, 223, 304\|\|'''>'''
	\|-		\|-
	\|'''21'''\|\|6(2<sup>4</sup>(4k + 3)) ~~- 2~~\|\|~~30 mod 128<br>62~~, 94, ~~126 mod 128\|\|286~~, ~~670, 1054, 1438~~\|\|6(3<sup>4</sup>k + 61~~) - 2~~\|\|~~364~~, ~~850~~, ~~1336~~, ~~1822~~\|\|'''>'''		\|'''22'''\|\|2<sup>4</sup>(4k + 1) \|\|16, 80, 144, 208\|\|3<sup>5</sup>k + 61\|\|61, 304, 547, 790\|\|'''>'''
	\|-		\|-
	~~\|'''22'''\|\|6(2<sup>4</sup>(4k + 1)) - 2\|\|94 mod 128<br>62, 126, 190, 254 mod 256\|\|94, 478, 862, 1246\|\|6(3<sup>5</sup>k + 61) - 2\|\|364, 1822, 3280, 4738\|\|'''>'''~~		\|...\|\|...\|\|...\|\|...\|\|...\|\|...
	\|-
	~~\|...\|~~\|... \|\|...\|\|... \|\|...\|\|... \|\|...
	\|-		\|-
	\|}		\|}
Line 39:		Line 36:
	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 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 ''c<sub>1</sub> = 4, c<sub>i1</sub>, c<sub>i2</sub>, c<sub>i3</sub>, ... '' where any ''c<sub>i</sub>'' can be attached to the previous one.		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 ''c<sub>1</sub> = 4, c<sub>i1</sub>, c<sub>i2</sub>, c<sub>i3</sub>, ... '' where any ''c<sub>i</sub>'' can be attached to the previous one.

	===Attachment of short segments===		===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'''.		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.
	----		----
	< previous part: [[OEIS/3x%2B1_Connectivity]]         ^ up: [[OEIS/3x%2B1_Problem]]		< previous part: [[OEIS/3x%2B1_Connectivity]]         ^ up: [[OEIS/3x%2B1_Problem]]

imported>Gfis: E and D

2019-08-09T09:06:27Z

E and D

New page

< previous part: [[OEIS/3x%2B1_Connectivity]]         ^ up: [[OEIS/3x%2B1_Problem]]
----
==Attachment rules==
The following table '''(T4)''' tells the computation rules for the target position, depending on the modularity condition of the 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''.

T4 shows the nodes and formulas in uncompressed form, but the formulas for the compressed form can easily be derived by mapping ''7*i-2'' to ''i''.


{| class="wikitable" style="text-align:left"
|-
!Rule / column!!Source segments||Condition / remaining!!First source segments!!Target segments!!First target segments!!Dir.
|-
|'''5'''||6(20(4k + 3)) - 2||0 mod 8 2, 4, 6 mod 8||16, 40, 64, 88||6(30k + 1 ) - 2||4, 10, 16, 22||<
|-
|'''6'''||6(20(4k + 1)) - 2||4 mod 8 2, 6, 10, 14 mod 16||4, 28, 52, 76||6(31k + 1) - 2||4, 22, 40, 58||<
|-
|'''9'''||6(21(4k + 1)) - 2||10 mod 16 2, 6, 14 mod 16||10, 58, 106, 154||6(31k + 1) - 2||4, 22, 40, 58||<
|-
|'''10'''||6(21(4k + 3)) - 2||2 mod 16 6, 14, 22, 30 mod 32||34, 82, 130, 178||6(32k + 7) - 2||40, 94, 148, 202||'''>'''
|-
|'''13'''||6(22(4k + 3)) - 2||6 mod 32 14, 22, 30 mod 32||70, 166, 262, 358||6(32k + 7) - 2||40, 94, 148, 202||<
|-
|'''14'''||6(22(4k + 1)) - 2||22 mod 32 14, 30, 46, 62 mod 64||22, 118, 214, 310||6(33k + 7) - 2||40, 202, 364, 526||'''>'''
|-
|'''17'''||6(23(4k + 1)) - 2||46 mod 64 14, 30, 62 mod 64||46, 238, 430, 622||6(33k + 7) - 2||40, 202, 364, 526||<
|-
|'''18'''||6(23(4k + 3)) - 2||14 mod 64 30, 62, 94, 126 mod 128||142, 334, 526, 718||6(34k + 61) - 2||364, 850, 1336, 1822||'''>'''
|-
|'''21'''||6(24(4k + 3)) - 2||30 mod 128 62, 94, 126 mod 128||286, 670, 1054, 1438||6(34k + 61) - 2||364, 850, 1336, 1822||'''>'''
|-
|'''22'''||6(24(4k + 1)) - 2||94 mod 128 62, 126, 190, 254 mod 256||94, 478, 862, 1246||6(35k + 61) - 2||364, 1822, 3280, 4738||'''>'''
|-
|...||... ||...||... ||...||... ||...
|-
|}
===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.
----
< previous part: [[OEIS/3x%2B1_Connectivity]]         ^ up: [[OEIS/3x%2B1_Problem]]