(classic problem)
Definition: Consider the function: if N is odd, 3 × N + 1; else N/2. Does beginning with any positive integer and repeatedly applying the function always yields 1?
Note: First posed by the German mathematician Lothar Collatz in 1937. Began appearing in print in the 1950's.
The sequence of integers generated are called "hailstones", since they may rise and fall but (presumably) always fall to the ground (the integer 1). Also called the Syracuse problem and many other names.
Author: PEB
MathWorld's Collatz problem entry.
Jeff Lagarias, The 3x+1 Problem and its Generalizations, American Mathematical Monthly, 92:3-23, 1985.
This paper gives the history of the problem, including various names, many references, and a survey of what is (was) known. The web version also has links to related sites.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 14 August 2008.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "Collatz problem", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/CollatzProblem.html