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 *n*_{0},
*α(n*_{0}).

The Collatz Conjecture is that we always reach 1, whatever the value
of *n*_{0}. 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= 2*^{k} then
*α(n)=k*
(try it!),
and otherwise it's easy to see that
*α(n)>log*_{2}(n).
A statistical argument [Crandall] suggests that *on average*,
*α(n)=5.28log*_{2}(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.

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