The 3x+1 problem and its generalizations***

Mathactivated text
Other available formats
Related links
Author biography

Abstract: (taken from the Introduction)

The 3x+1 problem, also known as the Collatz problem, the Syracuse problem, Kakutani's problem, Hasse's algorithm, and Ulam's problem, concerns the behavior of the iterates of the function which takes odd integers n to 3n+1 and even integers n to n/2. The 3x+1 Conjecture asserts that, starting from any positive integer n, repeated iteration of this function eventually produces the value 1.

The 3x+1 Conjecture is simple to state and apparently intractably hard to solve. It shares these properties with other iteration problems, for example that of aliquot sequences and with celebrated Diophantine equations such as Fermat's last theorem. Paul Erdos commented concerning the intractability of the 3x+1 problem: "Mathematics is not yet ready for such problems." Despite this doleful pronouncement, study of the 3x+1 problem has not been without reward. It has interesting connections with the Diophantine approximation of the binary logarithm of 3 and the distribution mod 1 of the sequence {(3/2)^k : k = 1, 2, ...}, with questions of ergodic theory on the 2-adic integers, and with computability theory - a generalization of the 3x+1 problem has been shown to be a computationally unsolvable problem. In this paper I describe the history of the 3x+1 problem and survey all the literature I am aware of about this problem and its generalizations.