Smallest element of cycle of length $k$ in Collatz 3x+1 map?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite
1












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.







share|cite|improve this question


















  • 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















up vote
1
down vote

favorite
1












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.







share|cite|improve this question


















  • 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













up vote
1
down vote

favorite
1









up vote
1
down vote

favorite
1






1





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.







share|cite|improve this question














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.









share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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













  • 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











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





share|cite|improve this answer



























    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.






    share|cite|improve this answer






















      Your Answer




      StackExchange.ifUsing("editor", function ()
      return StackExchange.using("mathjaxEditing", function ()
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      );
      );
      , "mathjax-editing");

      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "69"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      convertImagesToLinks: true,
      noModals: false,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );








       

      draft saved


      draft discarded


















      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






























      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





      share|cite|improve this answer
























        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





        share|cite|improve this answer






















          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





          share|cite|improve this answer












          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






          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Aug 18 at 8:22









          Gottfried Helms

          22.7k24195




          22.7k24195




















              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.






              share|cite|improve this answer


























                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.






                share|cite|improve this answer
























                  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.






                  share|cite|improve this answer














                  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.







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Aug 17 at 21:29

























                  answered Aug 14 at 18:00









                  rukhin

                  717




                  717






















                       

                      draft saved


                      draft discarded


























                       


                      draft saved


                      draft discarded














                      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













































































                      這個網誌中的熱門文章

                      How to combine Bézier curves to a surface?

                      Mutual Information Always Non-negative

                      Why am i infinitely getting the same tweet with the Twitter Search API?