Saturday, November 21, 2009

Unsolved: Collatz conjecture

First proposed in 1937 by the German mathematician Lothar Collatz, the Collatz conjecture is also known as the 3n + 1 problem, Kakutani's problem, the Syracuse problem, Thwaites' conjecture, and Ulam's conjecture. The conjecture starts with the following simple procedure:
  1. Let n be any natural number (n > 0).
  2. If n is odd, triple it and add 1 (n = 3n + 1).
  3. If n is even divide it in half (n = n/2).
  4. Stop if n = 1, otherwise go back to step 2.
The Collatz conjecture asks:
Does the above process always terminate (end with n = 1) for any starting value of n?
For example, starting with a value of n = 42, we get the following sequence

{ 42, 21, 64, 32, 16, 8, 4, 2, 1 }

The sequences produced by the Collatz procedure are known as hailstone sequences.

The conjecture remains unanswered, although it has been proven that the process terminates for all values of n up to 5.764 × 1018. In 1972, John Conway proved that it is possible for problems of this type to be undecidable, so it is not known if a solution is even possible.


Troy said...

Is it possible to explain how this conjecture might be undecidable?

I'm somewhat familiar with undecidable propositions, but I the examples I remember are more like "Use truth machine T to prove that T will prove that statement X is true", where the statement involves a reference to the system being used to prove statements.

This conjecture doesn't seem like it fits into that pattern.

Bill the Lizard said...

What Conway did is definitely different than what you describe (which sounds very similar to Turing's proof that the Halting problem is undecidable).

Conway created a new problem that generalized Collatz, by introducing a family of functions, of which the Collatz function is a member. He then showed that there's no way to show that all of these Collatz-like functions terminate at 1.

There's a decent (but I can't bring myself to say simple) explanation of the Conway-Collatz problem starting on page 119 of Iteration[PFD] by Klaus Sutner.

ROHIT ROY said...

when the number is of positive integer,the number always terminate (end with n=1).
but in case of negative integer its differ.,