3 ms·

Now I'm curious, is it guaranteed to terminate? Is there a name for this problem? It needs to land on a power of 2 at some point.

• _asummers 11y ago
  It's the Collatz Conjecture. [0] [0] https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture
• ggchappell 11y ago
  > Now I'm curious, is it guaranteed to terminate? No one knows. > Is there a name for this problem? The statement that it always terminates is the Collatz Conjecture. It's the first problem in the posted article.
  • emiliobumachar 11y ago
    Just to clarify why, if the result is ever one (the loop's exit condition), then it would be about to get stuck repeating 1,4,2 forever if it didn't exit. If you can prove the loop does not exit (i.e., never reaches one) for some n, then you just proved that, for that n, it would never reach the 1,4,2 repetition pattern even without the stop condition. It's a clever way to re-state the problem to look more computer-science-y.
• vlasev 11y ago
  As some of the people have already said, this is the Collatz conjecture aka 3n+1 problem aka half-or-triple-plus-one (HOTPO)problem. The fact that we don't know if the algorithm will certainly land on a power of two shows that it's quite a difficult problem. The famous mathematician Erdos said that math is not yet ready for such problems. There are heuristic to show that the algorithm should terminate but there are numbers for which it takes an arbitrarily long time for convergence. Furthermore, there are similar problems that have divergence or loops. What makes matters worse is that it's been proven that such problems are undecidable in general.