XKCD - http://xkcd.com/710/
http://en.wikipedia.org/wiki/Collatz_conjecture#Syracuse_function
I remember learning about this as an undergrad at Syracuse University in the 70's and didn't think much of it. It was just "one of those things" that I heard about, and perhaps wrote a homework assignment in APL or Algol-W.
http://projecteuler.net/index.php?section=problems&id=14
The good old days. When a program to examine the conjecture was hours of heavy thinking followed by carefully monitored run-times on an IBM 370. Computer time was money back in the day. Every minute counted. And you could spend your precious budget checking the Syracuse function or going out with friends.
My solution to the Project Euler problem is 18 lines of Python.
With a few memoization tricks, it runs in something like 3 seconds on my little MacBook. Back in the day, I don't think it even compiled that quickly.
My solution is about twice as many lines of Java, ...
Bill the Lizard<noreply@blogger.com>
2010-03-05 13:15:29.678000-05:00
My solution is about twice as many lines of Java, but I didn't use any memoization tricks so it would get a bit longer. Even without caching any values it only took about 9 seconds (on a fairly new desktop machine). It would certainly speed things up if I stored the lengths of the sequences, at least for each starting value. It would probably complicate the code beyond all recognition if I tried to cache all of the intermediate values as well.