## The 3x + 1 Problem and its Generalizations

**Abstract**

JEFFREY C. LAGARIAS AT & T Bell Laboratories, Murray Hill, NJ 07974 1. Introduction. The 3x + 1 problem, also known as the Collatz problem, the Syracuse prob lem, 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 (see Guy [36], Problem B6) 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 log 3 and the distribution (mod 1) of the sequence { (3 /2l: k = 1, 2, ... } , with questions of ergodic theory on the