Smallest element of cycle of length $k$ in Collatz 3x+1 map?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
In studies of the Collatz conjecture, what research has asserted the existence of a $k$-length cycle and drawn conclusions about its smallest element $m$? In particular, about the behavior of $m$ as $k rightarrow infty$?
I know that this question tried, this question speculated, and that the existence of $k$-length cycles given $m$ has been studied a lot. For example
Lagarias (1985) used a result by Yoneda that $m > 2^40$ and a theorem by Crandall (quoted as Theorem I) to prove that there are no nontrivial cycles of period length less than $k = 275,000$.
I am interested in the other direction, of properties of $m$ given $k$.
EDIT: I am especially interested in lower bounds for $m$, and whether it has been shown that $m rightarrow infty$ as $k rightarrow infty$ (thanks to @rukhin for the answer concerning an upper bound on $m$).
Many thanks in advance.
reference-request recreational-mathematics collatz
add a comment |Â
up vote
1
down vote
favorite
In studies of the Collatz conjecture, what research has asserted the existence of a $k$-length cycle and drawn conclusions about its smallest element $m$? In particular, about the behavior of $m$ as $k rightarrow infty$?
I know that this question tried, this question speculated, and that the existence of $k$-length cycles given $m$ has been studied a lot. For example
Lagarias (1985) used a result by Yoneda that $m > 2^40$ and a theorem by Crandall (quoted as Theorem I) to prove that there are no nontrivial cycles of period length less than $k = 275,000$.
I am interested in the other direction, of properties of $m$ given $k$.
EDIT: I am especially interested in lower bounds for $m$, and whether it has been shown that $m rightarrow infty$ as $k rightarrow infty$ (thanks to @rukhin for the answer concerning an upper bound on $m$).
Many thanks in advance.
reference-request recreational-mathematics collatz
1
see my question math.stackexchange.com/q/2848446/1714 . I have discussed the same problem there, but for the generalized Collatz-problem $mx+1$ instead of $3x+1$ only. Just insert $3$ for $m$ and use the formulae there. Note, that for $m=5$ the formulae give immediately the known values for the first 3-step-cycle ($a_1 = 13$)
â Gottfried Helms
Aug 17 at 14:12
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
In studies of the Collatz conjecture, what research has asserted the existence of a $k$-length cycle and drawn conclusions about its smallest element $m$? In particular, about the behavior of $m$ as $k rightarrow infty$?
I know that this question tried, this question speculated, and that the existence of $k$-length cycles given $m$ has been studied a lot. For example
Lagarias (1985) used a result by Yoneda that $m > 2^40$ and a theorem by Crandall (quoted as Theorem I) to prove that there are no nontrivial cycles of period length less than $k = 275,000$.
I am interested in the other direction, of properties of $m$ given $k$.
EDIT: I am especially interested in lower bounds for $m$, and whether it has been shown that $m rightarrow infty$ as $k rightarrow infty$ (thanks to @rukhin for the answer concerning an upper bound on $m$).
Many thanks in advance.
reference-request recreational-mathematics collatz
In studies of the Collatz conjecture, what research has asserted the existence of a $k$-length cycle and drawn conclusions about its smallest element $m$? In particular, about the behavior of $m$ as $k rightarrow infty$?
I know that this question tried, this question speculated, and that the existence of $k$-length cycles given $m$ has been studied a lot. For example
Lagarias (1985) used a result by Yoneda that $m > 2^40$ and a theorem by Crandall (quoted as Theorem I) to prove that there are no nontrivial cycles of period length less than $k = 275,000$.
I am interested in the other direction, of properties of $m$ given $k$.
EDIT: I am especially interested in lower bounds for $m$, and whether it has been shown that $m rightarrow infty$ as $k rightarrow infty$ (thanks to @rukhin for the answer concerning an upper bound on $m$).
Many thanks in advance.
reference-request recreational-mathematics collatz
edited Aug 15 at 1:19
asked Aug 14 at 5:41
Patrick Hew
356111
356111
1
see my question math.stackexchange.com/q/2848446/1714 . I have discussed the same problem there, but for the generalized Collatz-problem $mx+1$ instead of $3x+1$ only. Just insert $3$ for $m$ and use the formulae there. Note, that for $m=5$ the formulae give immediately the known values for the first 3-step-cycle ($a_1 = 13$)
â Gottfried Helms
Aug 17 at 14:12
add a comment |Â
1
see my question math.stackexchange.com/q/2848446/1714 . I have discussed the same problem there, but for the generalized Collatz-problem $mx+1$ instead of $3x+1$ only. Just insert $3$ for $m$ and use the formulae there. Note, that for $m=5$ the formulae give immediately the known values for the first 3-step-cycle ($a_1 = 13$)
â Gottfried Helms
Aug 17 at 14:12
1
1
see my question math.stackexchange.com/q/2848446/1714 . I have discussed the same problem there, but for the generalized Collatz-problem $mx+1$ instead of $3x+1$ only. Just insert $3$ for $m$ and use the formulae there. Note, that for $m=5$ the formulae give immediately the known values for the first 3-step-cycle ($a_1 = 13$)
â Gottfried Helms
Aug 17 at 14:12
see my question math.stackexchange.com/q/2848446/1714 . I have discussed the same problem there, but for the generalized Collatz-problem $mx+1$ instead of $3x+1$ only. Just insert $3$ for $m$ and use the formulae there. Note, that for $m=5$ the formulae give immediately the known values for the first 3-step-cycle ($a_1 = 13$)
â Gottfried Helms
Aug 17 at 14:12
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
Here is a table, based on computation of my earlier answer (see there). I got the N for which the lower bounds $a_textmin_1cyc$ are relatively highest by the continued fractions of $lambda=log(3)/log(2)$.
$a_m$ is the very rough "mean" value of all $a_k$ by $1over 2^S/N-3$, such that it is a good upper bound for $a_min$.
A slightly better (=smaller) upper bound occurs, when the $a_1 cdots a_N$ are assumed to be packed as tight as possible (though all different), so roughly in steps of $3$, and still solving rhs = lhs. I called it $a_textmin_compact$. Because the exact computation is time (or memory)-consumptive I've shown this only for $N le 10000$
The improvement over $a_m$ however is only marginal, so this reduced display may not be critical.
A lower bound, as you have asked, occurs if we assume the $a_k$ being in a so-called "1-cycle" which means also that they have the widest distance of each other and are consecutive iterates $a_k+1=(3a_k+1)/2$.
The minimal $a_k$ of any type of cycle cannot be smaller than $a_textmin_1cyc$.
I was surprised myself when I saw such large values for the large N ,btw.
N lhs=2^S/3^N amin_1cyc amin_compact am
----------------------------------------------------------------------------------
1 (1+0.333333333333): 1.00000000000 <= a_1 <= 0 < 1
5 (1+0.0534979423868): 16.2307692308 <= a_1 <= 25 < 31.8135643475
41 (1+0.0115288518086): 86.7389013502 <= a_1 <= 1133 < 1192.08534275
306 (1+0.0010227617964): 977.744772545 <= a_1 <= 99323 < 99780.7914439
15601 (1+0.0000181947538): 54960.8972938 <= a_1 <= undef < 285817586.219
79335 (1+0.0000036647273): 272871.592753 <= a_1 <= undef < 7216102492.69
190537 (1+0.0000000645075): 15502072.2362 <= a_1 <= undef < 984572810981.
10781274 (1+0.0000000122069): 81920324.7724 <= a_1 <= undef < 2.9440182 E14
171928773 (1+0.0000000017892): 558903955.481 <= a_1 <= undef < 3.2030557 E16
397573379 (1+1.05843488 E-10): 9447912335.13 <= a_1 <= undef < 1.2520794 E18
6586818670 (1+1.01231253 E-11): 98783722251.5 <= a_1 <= undef < 2.1689015 E20
137528045312 (1+8.98654870 E-13): 1.1127742 E12 <= a_1 <= undef < 5.1012555 E22
5409303924479 (1+6.59287766 E-14): 1.5167883 E13 <= a_1 <= undef < 2.7349230 E25
11571718688839 (1+1.28966827 E-14): 7.7539319 E13 <= a_1 <= undef < 2.9908772 E26
431166034846567 (1+1.33377903 E-15): 7.4974937 E14 <= a_1 <= undef < 1.0775548 E29
add a comment |Â
up vote
1
down vote
Belaga gives an upper bound on the "perigee" of a cycle; the reference can be found here.
EDIT: For a lower bound on the perigee, see my response here. It follows from a Bohm-Sontacchi-style argument.
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Here is a table, based on computation of my earlier answer (see there). I got the N for which the lower bounds $a_textmin_1cyc$ are relatively highest by the continued fractions of $lambda=log(3)/log(2)$.
$a_m$ is the very rough "mean" value of all $a_k$ by $1over 2^S/N-3$, such that it is a good upper bound for $a_min$.
A slightly better (=smaller) upper bound occurs, when the $a_1 cdots a_N$ are assumed to be packed as tight as possible (though all different), so roughly in steps of $3$, and still solving rhs = lhs. I called it $a_textmin_compact$. Because the exact computation is time (or memory)-consumptive I've shown this only for $N le 10000$
The improvement over $a_m$ however is only marginal, so this reduced display may not be critical.
A lower bound, as you have asked, occurs if we assume the $a_k$ being in a so-called "1-cycle" which means also that they have the widest distance of each other and are consecutive iterates $a_k+1=(3a_k+1)/2$.
The minimal $a_k$ of any type of cycle cannot be smaller than $a_textmin_1cyc$.
I was surprised myself when I saw such large values for the large N ,btw.
N lhs=2^S/3^N amin_1cyc amin_compact am
----------------------------------------------------------------------------------
1 (1+0.333333333333): 1.00000000000 <= a_1 <= 0 < 1
5 (1+0.0534979423868): 16.2307692308 <= a_1 <= 25 < 31.8135643475
41 (1+0.0115288518086): 86.7389013502 <= a_1 <= 1133 < 1192.08534275
306 (1+0.0010227617964): 977.744772545 <= a_1 <= 99323 < 99780.7914439
15601 (1+0.0000181947538): 54960.8972938 <= a_1 <= undef < 285817586.219
79335 (1+0.0000036647273): 272871.592753 <= a_1 <= undef < 7216102492.69
190537 (1+0.0000000645075): 15502072.2362 <= a_1 <= undef < 984572810981.
10781274 (1+0.0000000122069): 81920324.7724 <= a_1 <= undef < 2.9440182 E14
171928773 (1+0.0000000017892): 558903955.481 <= a_1 <= undef < 3.2030557 E16
397573379 (1+1.05843488 E-10): 9447912335.13 <= a_1 <= undef < 1.2520794 E18
6586818670 (1+1.01231253 E-11): 98783722251.5 <= a_1 <= undef < 2.1689015 E20
137528045312 (1+8.98654870 E-13): 1.1127742 E12 <= a_1 <= undef < 5.1012555 E22
5409303924479 (1+6.59287766 E-14): 1.5167883 E13 <= a_1 <= undef < 2.7349230 E25
11571718688839 (1+1.28966827 E-14): 7.7539319 E13 <= a_1 <= undef < 2.9908772 E26
431166034846567 (1+1.33377903 E-15): 7.4974937 E14 <= a_1 <= undef < 1.0775548 E29
add a comment |Â
up vote
1
down vote
accepted
Here is a table, based on computation of my earlier answer (see there). I got the N for which the lower bounds $a_textmin_1cyc$ are relatively highest by the continued fractions of $lambda=log(3)/log(2)$.
$a_m$ is the very rough "mean" value of all $a_k$ by $1over 2^S/N-3$, such that it is a good upper bound for $a_min$.
A slightly better (=smaller) upper bound occurs, when the $a_1 cdots a_N$ are assumed to be packed as tight as possible (though all different), so roughly in steps of $3$, and still solving rhs = lhs. I called it $a_textmin_compact$. Because the exact computation is time (or memory)-consumptive I've shown this only for $N le 10000$
The improvement over $a_m$ however is only marginal, so this reduced display may not be critical.
A lower bound, as you have asked, occurs if we assume the $a_k$ being in a so-called "1-cycle" which means also that they have the widest distance of each other and are consecutive iterates $a_k+1=(3a_k+1)/2$.
The minimal $a_k$ of any type of cycle cannot be smaller than $a_textmin_1cyc$.
I was surprised myself when I saw such large values for the large N ,btw.
N lhs=2^S/3^N amin_1cyc amin_compact am
----------------------------------------------------------------------------------
1 (1+0.333333333333): 1.00000000000 <= a_1 <= 0 < 1
5 (1+0.0534979423868): 16.2307692308 <= a_1 <= 25 < 31.8135643475
41 (1+0.0115288518086): 86.7389013502 <= a_1 <= 1133 < 1192.08534275
306 (1+0.0010227617964): 977.744772545 <= a_1 <= 99323 < 99780.7914439
15601 (1+0.0000181947538): 54960.8972938 <= a_1 <= undef < 285817586.219
79335 (1+0.0000036647273): 272871.592753 <= a_1 <= undef < 7216102492.69
190537 (1+0.0000000645075): 15502072.2362 <= a_1 <= undef < 984572810981.
10781274 (1+0.0000000122069): 81920324.7724 <= a_1 <= undef < 2.9440182 E14
171928773 (1+0.0000000017892): 558903955.481 <= a_1 <= undef < 3.2030557 E16
397573379 (1+1.05843488 E-10): 9447912335.13 <= a_1 <= undef < 1.2520794 E18
6586818670 (1+1.01231253 E-11): 98783722251.5 <= a_1 <= undef < 2.1689015 E20
137528045312 (1+8.98654870 E-13): 1.1127742 E12 <= a_1 <= undef < 5.1012555 E22
5409303924479 (1+6.59287766 E-14): 1.5167883 E13 <= a_1 <= undef < 2.7349230 E25
11571718688839 (1+1.28966827 E-14): 7.7539319 E13 <= a_1 <= undef < 2.9908772 E26
431166034846567 (1+1.33377903 E-15): 7.4974937 E14 <= a_1 <= undef < 1.0775548 E29
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Here is a table, based on computation of my earlier answer (see there). I got the N for which the lower bounds $a_textmin_1cyc$ are relatively highest by the continued fractions of $lambda=log(3)/log(2)$.
$a_m$ is the very rough "mean" value of all $a_k$ by $1over 2^S/N-3$, such that it is a good upper bound for $a_min$.
A slightly better (=smaller) upper bound occurs, when the $a_1 cdots a_N$ are assumed to be packed as tight as possible (though all different), so roughly in steps of $3$, and still solving rhs = lhs. I called it $a_textmin_compact$. Because the exact computation is time (or memory)-consumptive I've shown this only for $N le 10000$
The improvement over $a_m$ however is only marginal, so this reduced display may not be critical.
A lower bound, as you have asked, occurs if we assume the $a_k$ being in a so-called "1-cycle" which means also that they have the widest distance of each other and are consecutive iterates $a_k+1=(3a_k+1)/2$.
The minimal $a_k$ of any type of cycle cannot be smaller than $a_textmin_1cyc$.
I was surprised myself when I saw such large values for the large N ,btw.
N lhs=2^S/3^N amin_1cyc amin_compact am
----------------------------------------------------------------------------------
1 (1+0.333333333333): 1.00000000000 <= a_1 <= 0 < 1
5 (1+0.0534979423868): 16.2307692308 <= a_1 <= 25 < 31.8135643475
41 (1+0.0115288518086): 86.7389013502 <= a_1 <= 1133 < 1192.08534275
306 (1+0.0010227617964): 977.744772545 <= a_1 <= 99323 < 99780.7914439
15601 (1+0.0000181947538): 54960.8972938 <= a_1 <= undef < 285817586.219
79335 (1+0.0000036647273): 272871.592753 <= a_1 <= undef < 7216102492.69
190537 (1+0.0000000645075): 15502072.2362 <= a_1 <= undef < 984572810981.
10781274 (1+0.0000000122069): 81920324.7724 <= a_1 <= undef < 2.9440182 E14
171928773 (1+0.0000000017892): 558903955.481 <= a_1 <= undef < 3.2030557 E16
397573379 (1+1.05843488 E-10): 9447912335.13 <= a_1 <= undef < 1.2520794 E18
6586818670 (1+1.01231253 E-11): 98783722251.5 <= a_1 <= undef < 2.1689015 E20
137528045312 (1+8.98654870 E-13): 1.1127742 E12 <= a_1 <= undef < 5.1012555 E22
5409303924479 (1+6.59287766 E-14): 1.5167883 E13 <= a_1 <= undef < 2.7349230 E25
11571718688839 (1+1.28966827 E-14): 7.7539319 E13 <= a_1 <= undef < 2.9908772 E26
431166034846567 (1+1.33377903 E-15): 7.4974937 E14 <= a_1 <= undef < 1.0775548 E29
Here is a table, based on computation of my earlier answer (see there). I got the N for which the lower bounds $a_textmin_1cyc$ are relatively highest by the continued fractions of $lambda=log(3)/log(2)$.
$a_m$ is the very rough "mean" value of all $a_k$ by $1over 2^S/N-3$, such that it is a good upper bound for $a_min$.
A slightly better (=smaller) upper bound occurs, when the $a_1 cdots a_N$ are assumed to be packed as tight as possible (though all different), so roughly in steps of $3$, and still solving rhs = lhs. I called it $a_textmin_compact$. Because the exact computation is time (or memory)-consumptive I've shown this only for $N le 10000$
The improvement over $a_m$ however is only marginal, so this reduced display may not be critical.
A lower bound, as you have asked, occurs if we assume the $a_k$ being in a so-called "1-cycle" which means also that they have the widest distance of each other and are consecutive iterates $a_k+1=(3a_k+1)/2$.
The minimal $a_k$ of any type of cycle cannot be smaller than $a_textmin_1cyc$.
I was surprised myself when I saw such large values for the large N ,btw.
N lhs=2^S/3^N amin_1cyc amin_compact am
----------------------------------------------------------------------------------
1 (1+0.333333333333): 1.00000000000 <= a_1 <= 0 < 1
5 (1+0.0534979423868): 16.2307692308 <= a_1 <= 25 < 31.8135643475
41 (1+0.0115288518086): 86.7389013502 <= a_1 <= 1133 < 1192.08534275
306 (1+0.0010227617964): 977.744772545 <= a_1 <= 99323 < 99780.7914439
15601 (1+0.0000181947538): 54960.8972938 <= a_1 <= undef < 285817586.219
79335 (1+0.0000036647273): 272871.592753 <= a_1 <= undef < 7216102492.69
190537 (1+0.0000000645075): 15502072.2362 <= a_1 <= undef < 984572810981.
10781274 (1+0.0000000122069): 81920324.7724 <= a_1 <= undef < 2.9440182 E14
171928773 (1+0.0000000017892): 558903955.481 <= a_1 <= undef < 3.2030557 E16
397573379 (1+1.05843488 E-10): 9447912335.13 <= a_1 <= undef < 1.2520794 E18
6586818670 (1+1.01231253 E-11): 98783722251.5 <= a_1 <= undef < 2.1689015 E20
137528045312 (1+8.98654870 E-13): 1.1127742 E12 <= a_1 <= undef < 5.1012555 E22
5409303924479 (1+6.59287766 E-14): 1.5167883 E13 <= a_1 <= undef < 2.7349230 E25
11571718688839 (1+1.28966827 E-14): 7.7539319 E13 <= a_1 <= undef < 2.9908772 E26
431166034846567 (1+1.33377903 E-15): 7.4974937 E14 <= a_1 <= undef < 1.0775548 E29
answered Aug 18 at 8:22
Gottfried Helms
22.7k24195
22.7k24195
add a comment |Â
add a comment |Â
up vote
1
down vote
Belaga gives an upper bound on the "perigee" of a cycle; the reference can be found here.
EDIT: For a lower bound on the perigee, see my response here. It follows from a Bohm-Sontacchi-style argument.
add a comment |Â
up vote
1
down vote
Belaga gives an upper bound on the "perigee" of a cycle; the reference can be found here.
EDIT: For a lower bound on the perigee, see my response here. It follows from a Bohm-Sontacchi-style argument.
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Belaga gives an upper bound on the "perigee" of a cycle; the reference can be found here.
EDIT: For a lower bound on the perigee, see my response here. It follows from a Bohm-Sontacchi-style argument.
Belaga gives an upper bound on the "perigee" of a cycle; the reference can be found here.
EDIT: For a lower bound on the perigee, see my response here. It follows from a Bohm-Sontacchi-style argument.
edited Aug 17 at 21:29
answered Aug 14 at 18:00
rukhin
717
717
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2882105%2fsmallest-element-of-cycle-of-length-k-in-collatz-3x1-map%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
see my question math.stackexchange.com/q/2848446/1714 . I have discussed the same problem there, but for the generalized Collatz-problem $mx+1$ instead of $3x+1$ only. Just insert $3$ for $m$ and use the formulae there. Note, that for $m=5$ the formulae give immediately the known values for the first 3-step-cycle ($a_1 = 13$)
â Gottfried Helms
Aug 17 at 14:12