Namespaces
Variants
Actions

Difference between revisions of "Syracuse problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
''<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''
+
<!--
 +
s1103302.png
 +
$#A+1 = 33 n = 3
 +
$#C+1 = 33 : ~/encyclopedia/old_files/data/S110/S.1100330 Syracuse problem,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
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" />.
+
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
'' $  ( 3x + 1 ) $-
 +
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 $  a _ {n} $
 +
to $  a _ {n + 1 }  = { {a _ {n} } / 2 } $(
 +
$  a _ {n} $
 +
even) or to $  3a _ {n + 1 }  + 1 $(
 +
$  a _ {n} $
 +
odd). The $  ( 3x + 1 ) $-
 +
conjecture (also called the Collatz conjecture) asserts that for any starting value $  a _ {0} \geq  2 $
 +
there is some iterate $  a _ {n} = 1 $.
  
 
Some examples are:
 
Some examples are:
  
a) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033012.png" />;
+
a) $  1 \rightarrow 4 \rightarrow 2 \rightarrow 1 $;
  
b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033013.png" />;
+
b) $  5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 $;
  
c) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110330/s11033014.png" />.
+
c) $  7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 $.
  
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.
+
If $  a _ {0} $
 +
is allowed to be a negative integer, the conjecture is not true, as is shown by the example $  - 5 \rightarrow - 14 \rightarrow - 7 \rightarrow - 20 \rightarrow - 10 \rightarrow - 5 $.  
 +
In other words: the Collatz conjecture with $  3 a _ {n} + 1 $
 +
replaced by $  3 a _ {n} - 1 $
 +
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]]].
+
This conjecture is generally attributed to L. Collatz, who studied similar problems in the 1930s. It has been numerically verified for all $  a _ {0} < 6 \times 10 ^ {13 } $[[#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]]].
+
There is no periodic orbit of the Collatz mapping of period less than $  17087915 $,  
 +
except the orbit $  \{ 1,4,2 \} $.  
 +
The set of positive integers $  a _ {0} $
 +
that have some iterate $  a _ {n} $
 +
less than $  a _ {0} $
 +
has density one. At least $  x ^ {8/10 } $
 +
of all positive integers $  a _ {0} $
 +
less than $  x $
 +
have some iterate $  a _ {n} = 1 $,  
 +
[[#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
+
J.H. Conway [[#References|[a2]]] showed that a certain generalization of the $  ( 3x + 1 ) $-
 +
problem is non-computable. He defined a particular mapping $  f $
 +
from the positive integers into the positive integers of the form $  f ( n ) = b _ {n} n $,  
 +
in which $  \{ b _ {n} \} $
 +
is periodic (modulo some $  N _ {0} $)  
 +
for a fixed modulus $  N _ {0} $,  
 +
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>
+
$$
 +
\left \{ m : {\textrm{ some  iterate  }  f ^ {( k ) } ( m ) = 2  ^ {j} , \textrm{ some  }  j \geq  0 } \right \}
 +
$$
  
 
is recursively enumerable but not recursive.
 
is recursively enumerable but not recursive.

Latest revision as of 08:24, 6 June 2020


$ ( 3x + 1 ) $- 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 $ a _ {n} $ to $ a _ {n + 1 } = { {a _ {n} } / 2 } $( $ a _ {n} $ even) or to $ 3a _ {n + 1 } + 1 $( $ a _ {n} $ odd). The $ ( 3x + 1 ) $- conjecture (also called the Collatz conjecture) asserts that for any starting value $ a _ {0} \geq 2 $ there is some iterate $ a _ {n} = 1 $.

Some examples are:

a) $ 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 $;

b) $ 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 $;

c) $ 7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 $.

If $ a _ {0} $ is allowed to be a negative integer, the conjecture is not true, as is shown by the example $ - 5 \rightarrow - 14 \rightarrow - 7 \rightarrow - 20 \rightarrow - 10 \rightarrow - 5 $. In other words: the Collatz conjecture with $ 3 a _ {n} + 1 $ replaced by $ 3 a _ {n} - 1 $ 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 $ a _ {0} < 6 \times 10 ^ {13 } $[a5]. The conjecture is unsolved (1996) and apparently extremely difficult despite its simple appearance. General references and surveys on the problem are [a3], [a4], [a6].

There is no periodic orbit of the Collatz mapping of period less than $ 17087915 $, except the orbit $ \{ 1,4,2 \} $. The set of positive integers $ a _ {0} $ that have some iterate $ a _ {n} $ less than $ a _ {0} $ has density one. At least $ x ^ {8/10 } $ of all positive integers $ a _ {0} $ less than $ x $ have some iterate $ a _ {n} = 1 $, [a1].

J.H. Conway [a2] showed that a certain generalization of the $ ( 3x + 1 ) $- problem is non-computable. He defined a particular mapping $ f $ from the positive integers into the positive integers of the form $ f ( n ) = b _ {n} n $, in which $ \{ b _ {n} \} $ is periodic (modulo some $ N _ {0} $) for a fixed modulus $ N _ {0} $, which has the property that the set

$$ \left \{ m : {\textrm{ some iterate } f ^ {( k ) } ( m ) = 2 ^ {j} , \textrm{ some } j \geq 0 } \right \} $$

is recursively enumerable but not recursive.

References

[a1] D. Applegate, J.C. Lagarias, "Density bounds for the problem II. Krasikov inequalities" Math. Comp. , 64 (1995) pp. 427–438
[a2] J.H. Conway, "Unpredictable Iterations" , Proc. 1972 Number Theory Conf. Univ. Colorado, Boulder (1972) pp. 49–52
[a3] R.K. Guy, "Unsolved problems in number theory" , Springer (1994) pp. Problem E16 (Edition: Second)
[a4] J.C. Lagarias, "The problem and its generalizations" Amer. Math. Monthly , 92 (1985) pp. 3–23
[a5] G. Leavens, M. Vermeulen, " search programs" Computers & Mathematics, with Applications , 24 : 11 (1992) pp. 79–99
[a6] H.A. Müller, "Das "3n+1" Problem" Mitteil. Math. Ges. Hamburg , 12 (1991) pp. 231–251
How to Cite This Entry:
Syracuse problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Syracuse_problem&oldid=11881
This article was adapted from an original article by J.C. Lagarias (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article