OEIS/3x+1 Connectivity - Revision history

imported>Gfis at 07:39, 10 September 2019

2019-09-10T07:39:53Z

← Older revision		Revision as of 07:39, 10 September 2019
Line 142:		Line 142:

	Again, the residue conditions become more and more specific with increasing rule number, so it is plausible that it is difficult to build longer chains of such segments.		Again, the residue conditions become more and more specific with increasing rule number, so it is plausible that it is difficult to build longer chains of such segments.
	: For example, if we look at rule 10, we can combine this type of segment only for multiples of 72 (*6 - 2)~~. Longer chains cannot be built~~.		: For example, if we look at rule 10, we can combine this type of segment only for multiples of 72 (*6 - 2).

	The additive constants in T5 follow simple linear recurrences, namely [[https://oeis.org/A309791 A309791] for the left side and [[https://oeis.org/A309792 A309792] for the tail.		The additive constants in T5 follow simple linear recurrences, namely [https://oeis.org/A309791 A309791] for the left side and [https://oeis.org/A309792 A309792] for the tail.

	<!--		<!--

imported>Gfis: A309791/2

2019-09-10T07:37:31Z

A309791/2

← Older revision		Revision as of 07:37, 10 September 2019
Line 140:		Line 140:
	\|-		\|-
	\|}		\|}

	Again, the residue conditions become more and more specific with increasing rule number, so it is plausible that it is difficult to build longer chains of such segments.		Again, the residue conditions become more and more specific with increasing rule number, so it is plausible that it is difficult to build longer chains of such segments.
	: For example, if we look at rule 10, we can combine this type of segment only for multiples of 72 (*6 - 2). Longer chains cannot be built.		: For example, if we look at rule 10, we can combine this type of segment only for multiples of 72 (*6 - 2). Longer chains cannot be built.
	The additive constants in T5 ~~are explainable as follows~~:
	* ''m''		The additive constants in T5 follow simple linear recurrences, namely [[https://oeis.org/A309791 A309791] for the left side and [[https://oeis.org/A309792 A309792] for the tail.
	* ''n''
	<!--		<!--
	We now have to explain the chains of expanding segments, and prove their finite length.		We now have to explain the chains of expanding segments, and prove their finite length.

imported>Gfis: new T5

2019-08-17T06:01:01Z

new T5

Show changes

imported>Gfis: T5

2019-08-16T09:55:44Z

@@ Line 99: / Line 99: @@
 * Step 3: For each remaining subtree ''s > 1'' assembled so far in ''E'' attach ''s'' to its target and then remove it from ''E''. This target of the left side is unique and always exists in some subtree assembled so far in ''E''. A loop cannot be created because any node > 1 is reached by exactly one other node.
 * Step 4: The tree above segment 1 is the only one which remains in ''E''.
-===Chains of expanding segments===
+===Chains of segments===
 We now have to explain the chains of expanding segments, and prove their finite length.
-First we observe that the target node is always at the end of the right part of the target segment (the last or the last but one node).
+-->
 ----
 &lt; next part: [[OEIS/3x%2B1_Segments]] &nbsp; &nbsp; ^ up: [[OEIS/3x%2B1_Problem]] &nbsp; &nbsp; &gt; next part: [[OEIS/3x%2B1_Levels]]

imported>Gfis: few more

2019-08-14T21:19:36Z

few more

← Older revision		Revision as of 21:19, 14 August 2019
Line 85:		Line 85:
	* '''shrinking''', that is the left side is to be attached to a segment with a lower index (or same index for the root segment 1),		* '''shrinking''', that is the left side is to be attached to a segment with a lower index (or same index for the root segment 1),
	* '''expanding''' otherwise, that is when the left side is to be attached to a segment with higher index.		* '''expanding''' otherwise, that is when the left side is to be attached to a segment with higher index.
	Expanding segments result from rules 10, 14, 18, 21 and all following (with a ">" symbol in the last column of the table above). ~~That~~ are ~~the~~ ''long'' segments with more than 3 nodes in the right part.		Expanding segments result from rules 10, 14, 18, 21 and all following (with a ">" symbol in the last column of the table above). They are all '''long''' segments with more than 3 nodes in the right part.

	===Attachment process===		===Attachment process===
	At the beginning we have the infinite set of small subtrees represented by the segments. We want to combine all segments such that they finally form a single tree with root 1 (in the compressed case).		At the beginning we have the infinite set of small subtrees represented by the segments. We want to combine all segments such that they finally form a single tree with root 1 (in the compressed case).
	We define:		We define the '''enrooted set E''' to enumerate all segments for which it is still unknown how they should be attached to other segments.
	* The '''enrooted set E''' ~~enumerates~~ all segments for which it is still unknown how they should be attached to other segments~~. Set ''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. Set ''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. Set ''D'' is empty in the beginning.
	-->		-->
	Expanding segments may sometimes be attached to each other. As we will see below, the attachment target ~~lays~~ always at the end of the segment (it is the last or the last but one node in the right part). Furthermore, we claim that chains of expanding segments always have a finite length, and that we can build those chains.		Expanding (long) segments may sometimes be attached to each other. As we will see below, the attachment target is always at the end of the segment (it is the last or the last but one node in the right part). Furthermore, we claim that chains of expanding segments always have a finite length, and that we can build those chains.
	* Step 1: Build all chains of expanding segments ~~(infinitely many, but all of~~ finite length) .		* Step 0: Set ''E'' contains all segments from the segment directory in the beginning.
	* Step 2: ~~Attach~~ the first left side ~~of any such chain~~ to its target (which is shrinking), and remove all ~~segments of all chains~~ (~~that are all~~ expanding segments~~) from ''E''~~. In the end ''E'' contains shrinking subtrees only.		* Step 1: Build all chains of expanding segments by a process which is described below. The chains must have finite length.
	* Step 3: ~~We can now - in any order - pick a~~ remaining subtree ''s > 1'' assembled so far in ''E''~~, and~~ attach it to its target and then remove it from ''E''. This target of the left side is unique and always exists in some subtree assembled so far in ''E''. A loop cannot be created because any node > 1 is reached by exactly one other node.		* Step 2: For each such chain, attach the first left side to its target (which is shrinking), and remove all (expanding) segments of the chain. In the end ''E'' contains shrinking subtrees only.
			* Step 3: For each remaining subtree ''s > 1'' assembled so far in ''E'' attach ''s'' to its target and then remove it from ''E''. This target of the left side is unique and always exists in some subtree assembled so far in ''E''. A loop cannot be created because any node > 1 is reached by exactly one other node.
	* Step 4: The tree above segment 1 is the only one which remains in ''E''.		* Step 4: The tree above segment 1 is the only one which remains in ''E''.
	===Chains of expanding segments===		===Chains of expanding segments===
			We now have to explain the chains of expanding segments, and prove their finite length.
			First we observe that the target node is always at the end of the right part of the target segment (the last or the last but one node).
	----		----
	< next part: [[OEIS/3x%2B1_Segments]]     ^ up: [[OEIS/3x%2B1_Problem]]     > next part: [[OEIS/3x%2B1_Levels]]		< next part: [[OEIS/3x%2B1_Segments]]     ^ up: [[OEIS/3x%2B1_Problem]]     > next part: [[OEIS/3x%2B1_Levels]]

imported>Gfis: long chains

2019-08-14T21:06:09Z

long chains

← Older revision		Revision as of 21:06, 14 August 2019
Line 82:		Line 82:
	\|}		\|}

	The last column shows whether the rule is		The last column shows whether the rule (or the left side, segment, subtree) is
	* '''~~decreasing~~''', that is the left side is to be attached to a segment with a lower index (~~except~~ for the ~~first~~ segment),		* '''shrinking''', that is the left side is to be attached to a segment with a lower index (or same index for the root segment 1),
	* '''~~increasing~~''' when the ~~target of a~~ left side is a higher ~~segment~~.		* '''expanding''' otherwise, that is when the left side is to be attached to a segment with higher index.
			Expanding segments result from rules 10, 14, 18, 21 and all following (with a ">" symbol in the last column of the table above). That are the ''long'' segments with more than 3 nodes in the right part.

	===Attachment process===		===Attachment process===
	We want to combine all segments such that they form a single tree with root 1 (in the compressed case). We define ~~two sets~~:		At the beginning we have the infinite set of small subtrees represented by the segments. We want to combine all segments such that they finally form a single tree with root 1 (in the compressed case).
	* 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.		We define:
	* The '''attached set A''' enumerates all segments which have a known attachment rule, target segment and column where they can be attached. A is empty in the beginning.		* The '''enrooted set E''' enumerates all segments for which it is still unknown how they should be attached to other segments. Set ''E'' contains all segments from the segment directory in the beginning.
	~~We now proceed by describing a process which moves source segments from some subset of E to A. In each step, we~~
	* consider the source segments which are still in E,
	* and which have some property,
	* and delete those in E and add them to A.
	~~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 A.~~

	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 '''contracted''', 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 can move all segments except the ''s<sub>i1</sub>'' from E to A. Such contractions are defined only for decreasing rules.

	~~When we use the verb ''attach'', we do not repeat the more complicated process described above.~~

	<!--		<!--
	~~===Following a Collatz trajectory===~~		* The '''disrooted set D''' enumerates all segments which have a known attachment rule, target segment and column where they can be attached. Set ''D'' is empty in the beginning.
	~~Since we are sure that~~ all ~~numbers occur once in the right part of our segment directory, we can pick any of them and start~~ a ~~Collatz trajectory, hopefully proceeding down to the root (4). In parallel~~, ~~we try to trace the trajectory in the~~ segment ~~directory~~.
	~~==Covering the Collatz graph by the right part==~~
	~~The fact that all numbers occur at exactly one place in the segment directory~~ is ~~a good indication~~
	* that the whole Collatz graph can be covered by the right part of the segment directory,
	* that there are no cycles in the ~~graph, and~~
	* that it really has the form of a tree.
	-->		-->
			Expanding segments may sometimes be attached to each other. As we will see below, the attachment target lays always at the end of the segment (it is the last or the last but one node in the right part). Furthermore, we claim that chains of expanding segments always have a finite length, and that we can build those chains.
			* Step 1: Build all chains of expanding segments (infinitely many, but all of finite length) .
			* Step 2: Attach the first left side of any such chain to its target (which is shrinking), and remove all segments of all chains (that are all expanding segments) from ''E''. In the end ''E'' contains shrinking subtrees only.
			* Step 3: We can now - in any order - pick a remaining subtree ''s > 1'' assembled so far in ''E'', and attach it to its target and then remove it from ''E''. This target of the left side is unique and always exists in some subtree assembled so far in ''E''. A loop cannot be created because any node > 1 is reached by exactly one other node.
			* Step 4: The tree above segment 1 is the only one which remains in ''E''.
			===Chains of expanding segments===
	----		----
	< next part: [[OEIS/3x%2B1_Segments]]     ^ up: [[OEIS/3x%2B1_Problem]]     > next part: [[OEIS/3x%2B1_Levels]]		< next part: [[OEIS/3x%2B1_Segments]]     ^ up: [[OEIS/3x%2B1_Problem]]     > next part: [[OEIS/3x%2B1_Levels]]

imported>Gfis: Rules 25, 26

2019-08-14T15:46:20Z

Rules 25, 26

← Older revision		Revision as of 15:46, 14 August 2019
Line 72:		Line 72:
	\|'''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\|\|'''>'''
			\|-
			\|'''25'''\|\|2<sup>5</sup>(4k + 1) \|\| ... \|\|3<sup>5</sup>*k + 61\|\| ... \|\|'''>'''
			\|-
			\|'''26'''\|\|2<sup>5</sup>(4k + 3) \|\| ... \|\|3<sup>6</sup>*k + 547\|\| ... \|\|'''>'''
	\|-		\|-
	\|...\|\|...\|\|...\|\|...\|\|...\|\|'''>'''		\|...\|\|...\|\|...\|\|...\|\|...\|\|'''>'''

imported>Gfis at 15:42, 12 August 2019

2019-08-12T15:42:56Z

← Older revision		Revision as of 15:42, 12 August 2019
Line 46:		Line 46:
	Our goal is to combine the small subtrees represented by the (compressed) segments into bigger trees and finally into one tree which maps to the whole Collatz graph.		Our goal is to combine the small subtrees represented by the (compressed) segments into bigger trees and finally into one tree which maps to the whole Collatz graph.


	~~==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 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.		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 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
Line 76:		Line 74:
	\|'''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\|\|'''>'''
	\|-		\|-
	\|...\|\|...\|\|...\|\|...\|\|...\|\|~~...~~		\|...\|\|...\|\|...\|\|...\|\|...\|\|'''>'''
	\|-		\|-
	\|}		\|}

imported>Gfis: Attachment process

2019-08-12T15:40:07Z

Attachment process

@@ Line 1: / Line 1: @@
-&lt; next part: [[OEIS/3x%2B1_Segments]] &nbsp; &nbsp; &nbsp; &nbsp; &gt; next part: [[OEIS/3x%2B1_Proof]]
+&lt; next part: [[OEIS/3x%2B1_Segments]] &nbsp; &nbsp; ^ up: [[OEIS/3x%2B1_Problem]] &nbsp; &nbsp; &gt; next part: [[OEIS/3x%2B1_Levels]]
 ----
 ==Connectivity of the graph==
@@ Line 45: / Line 45: @@
 ===Attachment rules===
 Our goal is to combine the small subtrees represented by the (compressed) segments into bigger trees and finally into one tree which maps to the whole Collatz graph.
 <!--
@@ Line 56: / Line 107: @@
 -->
 ----
-&lt; next part: [[OEIS/3x%2B1_Segments]] &nbsp; &nbsp; &nbsp; &nbsp; &gt; next part: [[OEIS/3x%2B1_Proof]]
+&lt; next part: [[OEIS/3x%2B1_Segments]] &nbsp; &nbsp; ^ up: [[OEIS/3x%2B1_Problem]] &nbsp; &nbsp; &gt; next part: [[OEIS/3x%2B1_Levels]]

imported>Gfis at 21:03, 7 August 2019

2019-08-07T21:03:26Z

← Older revision		Revision as of 21:03, 7 August 2019
Line 22:		Line 22:
	The following table ('''T2''') shows how the formulas from T1 can be rearranged to yield the simple sequence of "/3" and "*2" operations which is used to compute A322469:		The following table ('''T2''') shows how the formulas from T1 can be rearranged to yield the simple sequence of "/3" and "*2" operations which is used to compute A322469:
	{\| class="wikitable" style="text-align:left"		{\| class="wikitable" style="text-align:left"
	!Column j!! Operation on 6*i-2 !! Formula from T1 !! = !! = !! Operation in A322469		!Column j!! Operation on 6*i-2 !!Formula from T1 !! = !! = !!Operation in A322469
	\|-		\|-
	\|5 \|\|µµ \|\| 24(i - 1)/1 + 16 \|\| 6(4(i - 1)/1 + 3) - 2 \|\| 6(4i - 1) - 2 \|\| 4i-1		\|5 \|\|µµ \|\|24(i - 1)/1 + 16 \|\| 6(4(i - 1)/1 + 3) - 2\|\| 6(4i - 1) - 2\|\|4i - 1
	\|-		\|-
	\|6 \|\|δµµ \|\| 24(i - 1)/3 + 4 \|\| 6(4(i - 1)/3 + 1) - 2 \|\| 6(4*i/3 - 1/3) - 2 \|\| /3		\|6 \|\|δµµ \|\|24(i - 1)/3 + 4 \|\| 6(4(i - 1)/3 + 1) - 2\|\| 6(4*i/3 - 1/3) - 2\|\|/3
	\|-		\|-
	\|9 \|\|µµσ \|\| 48(i - 1)/3 + 10 \|\| 6(8(i - 1)/3 + 2) - 2 \|\| 6(8i/3 - 2/3) - 2 \|\| 2		\|9 \|\|µµσ \|\|48(i - 1)/3 + 10 \|\| 6(8(i - 1)/3 + 2) - 2\|\| 6(8i/3 - 2/3) - 2\|\|2
	\|-		\|-
	\|10 \|\|δµµσ \|\| 48(i - 7)/9 + 34 \|\| 6(8(i - 7)/9 + 6) - 2 \|\| 6(8*i/9 - 2/9) - 2 \|\| /3		\|10\|\|δµµσ \|\|48(i - 7)/9 + 34 \|\| 6(8(i - 7)/9 + 6) - 2\|\| 6(8*i/9 - 2/9) - 2\|\|/3
	\|-		\|-
	\|13 \|\|µµσ<sup>2</sup> \|\| 96(i - 7)/9 + 70 \|\| 6(16(i - 7)/9 + 12) - 2 \|\| 6(16i/9 - 4/9) - 2 \|\| 2		\|13\|\|µµσ<sup>2</sup> \|\|96(i - 7)/9 + 70 \|\| 6(16(i - 7)/9 + 12) - 2\|\| 6(16i/9 - 4/9) - 2\|\|2
	\|-		\|-
	\|14 \|\|δµµσ<sup>2</sup>\|\| 96(i - 7)/27 + 22 >\|\| 6(16(i - 7)/27 + 4) - 2 \|\| 6(16*i/27 - 4/27) - 2 \|\| /3		\|14\|\|δµµσ<sup>2</sup>\|\|96(i - 7)/27 + 22 \|\| 6(16(i - 7)/27 + 4) - 2\|\| 6(16*i/27 - 4/27) - 2\|\|/3
	\|-		\|-
	\|17 \|\|µµσ<sup>3</sup> \|\| 192(i - 7)/27 + 46 \|\| 6(32(i - 7)/27 + 8) - 2 \|\| 6(32i/27 - 8/27) - 2 \|\| 2		\|17\|\|µµσ<sup>3</sup> \|\|192(i - 7)/27 + 46\|\| 6(32(i - 7)/27 + 8) - 2\|\| 6(32i/27 - 8/27) - 2\|\|2
	\|-		\|-
	\|... \|\|... \|\| ... \|\| ... \|\| ... \|\| ...		\|..\|\|... \|\|... \|\| ... \|\| ... \|\|...
	\|-		\|-
	\|}		\|}
	A322469 also contains a proof that the sequence (the right part of that table) is a permutation of the numbers > 0.		A322469 also contains a proof that the sequence (the right part of that table) is a permutation of the numbers > 0.

			===Attachment rules===
			Our goal is to combine the small subtrees represented by the (compressed) segments into bigger trees and finally into one tree which maps to the whole Collatz graph.

			<!--
	===Following a Collatz trajectory===		===Following a Collatz trajectory===
	Since we are sure that all numbers occur once in the right part of our segment directory, we can pick any of them and start a Collatz trajectory, hopefully proceeding down to the root (4). In parallel, we try to trace the trajectory in the segment directory.		Since we are sure that all numbers occur once in the right part of our segment directory, we can pick any of them and start a Collatz trajectory, hopefully proceeding down to the root (4). In parallel, we try to trace the trajectory in the segment directory.
Line 50:		Line 54:
	* that there are no cycles in the graph, and		* that there are no cycles in the graph, and
	* that it really has the form of a tree.		* that it really has the form of a tree.
			-->
	~~Any number ''n'', be it a start value or a~~
	----		----
	< next part: [[OEIS/3x%2B1_Segments]]         > next part: [[OEIS/3x%2B1_Proof]]		< next part: [[OEIS/3x%2B1_Segments]]         > next part: [[OEIS/3x%2B1_Proof]]