A while ago, i read a story about a billboard that Google put up as a way to recruit talent. The story seemed to resurface again this week. The sign reads: "{the 10-digit prime number found in consecutive digits of e}.com ." While the answer has been posted around the web, NewGuy and I wanted to find it on our own. The web makes it easy to find first five million digits of e so you know where to start. We quickly threw together an algorithm at the end of the work day. We let it run over night and same back the next day to find that it found the correct answer, but it took 13 hours. We took another look at the algorithm, found a few places for improvements and got the time down to 6 hours. We took one last stab at rewriting the code, this time eliminating some unnecessary assumptions, and managed to get the the code to run in under one minute.
It's almost embarrassing that our first go took such a horribly inefficient route. It's easy to overthink some problems and sometimes you just need to take a step back and start over.
I still wasn't completely satisfied with our final algorithm. It got me interested in finding an even more efficient routine. This lead me to Fermat's little theorem. In order to understand how the theorem worked, i had to improve my understanding of the intricacies of the mod operator. The last trick is to figure out how to raise 17 to a power in the billionths without causing a data-type overflow. Most of the sample code i've seen makes use of bit manipulation to pull it off and that's way beyond my comprehension at this point. Computer science gets really ugly at a very low level and i'm not sure if i'm excited or frightened by it.
Posted by Matthew at September 20, 2004 09:14 PM