A006877 - In the `3x+1' problem, these values for the starting value set new records for number of steps to reach 1
A006877 - In the `3x+1' problem, these values for the starting value set new records for number of steps to reach 1
1, 2, 3, 6, 7, 9, 18, 25, ...
In 1937, Lothar Collatz described an operation on positive integers. If the integer is even, divide it by 2. If it is odd, triple it and add one. And then he posed a problem, which has since been called the Collatz conjecture (and a dozen other less common names) -- if you apply this operation repeatedly, will it always eventually reach 1, no matter what number you start with?
The most promising avenues of proof are by disproving the alternatives. If the Collatz conjecture were false, that would mean that one of the following alternatives were true:
For some odd n, there is an infinitely divergent series, i.e. 3n+1 is odd, and 3(3n+1)+1 is odd, and so forth forever, it never equals 2k for any k, or
There exists a cycle which does not include 1
Tim Conway and Jeffrey Lagarias each examined the latter alternative through the 70s and 80s, Lagarias proving that there are no cycles of length < 275,000. More recently, several researchers (most recently Oliveira e Silva) have searched for some n that does not have a finite path to 1. So far, no counter-examples are known through at least 5 Ă 1018.
Unfortunately, the Collatz Conjecture may never be proved. Paul ErdĹs himself once said "mathematics is not yet ready for such problems" in reference to this problem. He may have been right -- In 1972, Conway proved that general Collatz-type problems can be formally undecidable.