Encyclopedia > Collatz conjecture

  Article Content

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 × 1012, 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...


All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Museums in England

... Barton Museum of Village Life[?] Northampton Central Museum & Art Gallery[?] Norfolk Bressingham Steam Museum[?] East Anglia Railway ...

This page was created in 79 ms