Take a positive integer: if it's even halve it, otherwise multiply by 3 and add 1, then halve. Iterate this.

Eventually, you will get to 1 - the number of iterations this requires is the Collatz Number of n0, α(n0).

The Collatz Conjecture is that we always reach 1, whatever the value of n0. Lothar Collatz set it in 1937 and it has defied proof ever since, despite attention by very strong mathematicians. The celebrated Paul Erdös described attempts to prove the Conjecture as Hopeless, absolutely hopeless.

If n= 2k then α(n)=k (try it!), and otherwise it's easy to see that α(n)>log2(n). A statistical argument [Crandall] suggests that on average, α(n)=5.28log2(n).

Plotting α(n) is interesting as it is essentially random, even if you think you can detect patterns. It does grow (unevenly) with n, but a plot of α(n)/log(n) does not (on average!). The randomness has reminded people of hailstones bouncing off a hard flat surface, and it is sometimes called the Hailstone function.

John Conway (famous for his Game of Life) suggests that it may not actually be possible to prove or disprove the conjecture; that it is undecidable. If this is in fact the case, then the Collatz Conjecture is the simplest known undecidable problem.

[brief!] Bibliography

Hammett gives a very gentle and understandable overview;
Lagarias provides an accessible but deeper introduction (and has worked and published extensively on the problem);
Littman's lecture on Computability [decidability] is very accessible and uses Collatz as an example;
van Bedegem provides an interesting philosophical study of the problem.

  1. Conway, J: Unpredictable iterations, Proc. 1972 Number theory Conference, Boulder Colorado, 49-52, 1972.
  2. Crandall, R: On the 3x+1 problem, Mathematics of Computation, 64, 1281-1292, 1978.
  3. Hammett, M: The Collatz Conjecture - A brief overview, online, 2011.
  4. Lagarias, J: The 3x+1 problem and its generalizations, American Mathematical Monthly, 92, 3-23, 1985.
  5. Littman, M: Computability, online, 2006.
  6. van Bendegem, J: The Collatz Conjecture, Logic and Logical Philosophy, 14, 7-23, 2005.