4 ms·

One of my favorite C.S. professors, in a first-year grad class, gave out 3 of these problems as homework, including the first one, without indicating whether it

by mturmon 11y ago

One of my favorite C.S. professors, in a first-year grad class, gave out 3 of these problems as homework, including the first one, without indicating whether it was easy or hard. The problem was posed as a while loop, and the question was, does the loop terminate for arbitrary n>0, so it seemed very tractable: given: n > 0. while n != 1: if n is odd: n = 3n + 1 else: n = n/2 It was a tease. I tried a couple of different ways to prove it, but of course nothing worked. Then I tried to find a counter-example. The numbers get pretty big, in some cases, because applying n = 3n + 1 several times in a row will blow "n" up, despite the intervening n = n/2. This was before arbitrary-precision arithmetic was a thing, so the only tool I knew that could do this was the Unix "dc". I think I was able to get up to n=10K or 50K on our campus VAX. That was about 30 years ago. I still remember it fondly.

0xffff2 11y ago
This is a pretty good example of how far computing hardware has come. I was able to eliminated 2 to 50k in 81ms in completely unoptimized C# just now. Makes me wonder who has taken this approach the farthest these days.
- ggchappell 11y ago
  > ... who has taken this approach the farthest these days. Tomás Oliveira e Silva of the Universidade de Aveiro, in Portugal, apparently. According to a page on his personal website [http://sweet.ua.pt/tos/3x+1.html http://sweet.ua.pt/tos/3x+1.html] he has verified it up to 5 x 2^60.
- mturmon 11y ago
  My prof was also more impressed by my implementing it than by my attempted proofs. (Not the first time this has happened!) I just implemented it too. I notice that by 100K, you get an intermediate result of size just less than 2^31, but at 1M, you get an intermediate result of size about 2^36. Maybe I went up above 100K. For more: http://en.wikipedia.org/wiki/Collatz_conjecture#Experimental_evidence http://en.wikipedia.org/wiki/Collatz_conjecture#Experimental..., which includes some very nice plots, and a fractal construction when iterating an extension of the map to the complex plane. Whew! (On the other hand, https://xkcd.com/710/ https://xkcd.com/710/)
yeldarb 11y ago
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.

by mturmon 11y ago

0xffff2 11y ago

This is a pretty good example of how far computing hardware has come. I was able to eliminated 2 to 50k in 81ms in completely unoptimized C# just now. Makes me wonder who has taken this approach the farthest these days.

ggchappell 11y ago
> ... who has taken this approach the farthest these days. Tomás Oliveira e Silva of the Universidade de Aveiro, in Portugal, apparently. According to a page on his personal website [http://sweet.ua.pt/tos/3x+1.html http://sweet.ua.pt/tos/3x+1.html] he has verified it up to 5 x 2^60.
mturmon 11y ago
My prof was also more impressed by my implementing it than by my attempted proofs. (Not the first time this has happened!) I just implemented it too. I notice that by 100K, you get an intermediate result of size just less than 2^31, but at 1M, you get an intermediate result of size about 2^36. Maybe I went up above 100K. For more: http://en.wikipedia.org/wiki/Collatz_conjecture#Experimental_evidence http://en.wikipedia.org/wiki/Collatz_conjecture#Experimental..., which includes some very nice plots, and a fractal construction when iterating an extension of the map to the complex plane. Whew! (On the other hand, https://xkcd.com/710/ https://xkcd.com/710/)

yeldarb 11y ago

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.