# Syracuse problem

$( 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=48940
This article was adapted from an original article by J.C. Lagarias (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article