Collatz conjecture - Definition and Overview

The Collatz conjecture, also known as the 3n + 1 conjecture, the Ulam conjecture or the Hailstone sequence or Hailstone numbers, was first stated in 1937 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.

Or, algebraically,

<math>f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \pmod{2} \\ 3n+1 & \mbox{if } n\equiv 1 \pmod{2} \end{cases}<math>

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

The sequence of Collatz conjecture can be easily computated by:

   function collatz(n)
       print n;
       if n = 1 
           return 1;
       else if n mod 2 = 0
           return collatz(n ÷ 2);
       else
           return collatz(3 × n + 1);

One can easly see that every time that n is odd, in the next call, will be even, because when n is replaced by 2m + 1 then 3n + 1 is replaced by

<math> 3(2m+1) + 1\, <math>

<math> = 6m + 3 + 1\,<math>

<math> = 6m + 4\,<math>

<math> = 2z\, <math> where <math> z = 3m + 2.<math>

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 3 × 2⁵³ (about 2.702 × 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...

There is another approach to prove the following conjecture, which considers the bottom-up method of growing Collatz graph. Collatz graph is defined by an inverse function,

<math> f(n) = \begin{cases} \{2n \} & \mbox{if } n\equiv 0 \pmod{3} \\ \{2n, (2n-1)/3\} & \mbox{if } n\equiv \pm 1 \pmod{3} \end{cases}<math>

Thus looking from this perspective, we have the problem redefined in the following way. The Collatz conjecture states,

• The inverse function forms a tree except for the 1-2 loop.
• All integers are present in the tree.

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
• Collatz Problem: Wolfram's MathWorld gives a good insight for introduction of this problem and its generalization. Online at http://mathworld.wolfram.com/CollatzProblem.html