Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

Collatz problem





A problem first posed by the German mathematician Lothar Collatz (1910–1990) in 1937, that is also known variously as the 3n + 1 problem, Kakutani's problem, the Syracuse problem, Thwaites' conjecture, and Ulam's conjecture. It runs as follows. Let n be any integer. (1) If n is odd, put n equal to 3n + 1; otherwise, put n equal to n/2. (2) If n = 1, stop; otherwise go back to step 1. Does this process always terminate (i.e. end in 1) for any value of n? To date, this question remains unanswered, though the process has been found to stop for all n up to 5.6 × 1013. British mathematician Bryan Thwaites (1996) has offered a 1,000 reward for a resolution of the problem. However, John Conway has shown that Collatz-type problems can be formally undecidable, so it not known if a solution is even possible. The sequences of numbers produced by the Collatz problem are sometimes known as hailstone sequences.


Reference

  1. Guy, Richard K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, 1994.

Related category

   • NUMBER THEORY