Collatz conjecture

The Collatz conjecture, also known as the 3n+1 conjecture, the Ulam conjecture or the Hailstone sequence, was first stated around 1950 and concerns the following process:

1. Pick any positive integer n.
2. If n is even, divide it by two; if it is odd, multiply it by three and add one.
3. If n = 1, stop; else go back to step 2.

For instance, starting with n = 6, we get the sequence 6, 3, 10, 5, 16, 8, 4, 2, 1.

The Collatz conjecture says that this process always stops, no matter what the start value.

The conjecture has been checked by computer for all start values up to 1.2 × 10¹², but a proof of the conjecture has not been found. Paul Erdős said about the Collatz conjecture: "Mathematics is not yet ready for such problems." He offered $500 for its solution.

There are some heuristic, statistical arguments supporting the conjecture: if one considers only the odd numbers in the sequence generated by the Collatz process, then one can argue that on average the next odd number should be about 3/4 of the previous one, which suggests that they eventually hit the bottom.

Sometimes the problem is stated differently. The termination condition ("If n = 1, stop") is removed from the procedure, so the sequence doesn't end. If you state the problem this way, the conjecture becomes the statement that the sequence always ends up in the repeating loop 1, 4, 2, 1, 4, 2...

References

• Jeff Lagarias: The 3x+1 problem and its generalizations, American Mathematical Monthly Volume 92, 1985, pp. 3 - 23. Online at http://www.cecm.sfu.ca/organics/papers/lagarias/
• An ongoing distributed computing project verifies the Collatz conjecture for larger and larger values. Online at http://personal.computrain.nl/eric/wondrous/index.html