View source for Syracuse problem

''<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s1103302.png" />-problem, Collatz problem, Hasse algorithm, Hasse–Collatz problem, Kakutani problem, Ulam problem''

This problem concerns the iteration of the Collatz mapping that sends a positive integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s1103303.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s1103304.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s1103305.png" /> even) or to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s1103306.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s1103307.png" /> odd). The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s1103309.png" />-conjecture (also called the Collatz conjecture) asserts that for any starting value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033010.png" /> there is some iterate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033011.png" />.

Some examples are:

a) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033012.png" />;

b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033013.png" />;

c) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033014.png" />.

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033015.png" /> is allowed to be a negative integer, the conjecture is not true, as is shown by the example <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033016.png" />. In other words: the Collatz conjecture with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033017.png" /> replaced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033018.png" /> does not hold.

This conjecture is generally attributed to L. Collatz, who studied similar problems in the 1930s. It has been numerically verified for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033019.png" /> [[#References|[a5]]]. The conjecture is unsolved (1996) and apparently extremely difficult despite its simple appearance. General references and surveys on the problem are [[#References|[a3]]], [[#References|[a4]]], [[#References|[a6]]].

There is no periodic orbit of the Collatz mapping of period less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033020.png" />, except the orbit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033021.png" />. The set of positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033022.png" /> that have some iterate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033023.png" /> less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033024.png" /> has density one. At least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033025.png" /> of all positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033026.png" /> less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033027.png" /> have some iterate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033028.png" />, [[#References|[a1]]].

J.H. Conway [[#References|[a2]]] showed that a certain generalization of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033029.png" />-problem is non-computable. He defined a particular mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033030.png" /> from the positive integers into the positive integers of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033031.png" />, in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033032.png" /> is periodic (modulo some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033033.png" />) for a fixed modulus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033034.png" />, which has the property that the set

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033035.png" /></td> </tr></table>

is recursively enumerable but not recursive.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D. Applegate,   J.C. Lagarias,   "Density bounds for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033036.png" /> problem II. Krasikov inequalities"  ''Math. Comp.'' , '''64'''  (1995)  pp. 427–438</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.H. Conway,   "Unpredictable Iterations" , ''Proc. 1972 Number Theory Conf. Univ. Colorado, Boulder''  (1972)  pp. 49–52</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.K. Guy,   "Unsolved problems in number theory" , Springer  (1994)  pp. Problem E16  (Edition: Second)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J.C. Lagarias,   "The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033037.png" /> problem and its generalizations"  ''Amer. Math. Monthly'' , '''92'''  (1985)  pp. 3–23</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  G. Leavens,   M. Vermeulen,   "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033038.png" /> search programs"  ''Computers &amp; Mathematics, with Applications'' , '''24''' :  11  (1992)  pp. 79–99</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  H.A. Müller,   "Das  "3n+1"  Problem"  ''Mitteil. Math. Ges. Hamburg'' , '''12'''  (1991)  pp. 231–251</TD></TR></table>