- Let n be any natural number (n > 0).
- If n is odd, triple it and add 1 (n = 3n + 1).
- If n is even divide it in half (n = n/2).
- Stop if n = 1, otherwise go back to step 2.
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.
3 comments:
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.
Troy,
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.
when the number is of positive integer,the number always terminate (end with n=1).
but in case of negative integer its differ.,
Post a Comment