[HNatWORK]

So this post inspired me because I've been doing a lot of the Project Euler (http://projecteuler.net/) problems and this seemed in a similar vein.

I let it run a few hours in Python on a fastish laptop (although I could only use one core) and only got to ~23%. I became interested in the number of minutes it took to advance each step, and found an interesting pattern:

To go from 7% to 8% takes 2.719 times as long as 6% to 7%, and 8% to 9% takes 2.719 times as long as that. The period eventually settles at e (2.7182818...). Using this, it should be easy to calculate the total number of minutes as such: I found it took 100210581 minutes to get to 19%, so: 100% = 100210581 * e^(100-19) = 1.509e+43

I checked my math by using another number (36865412 is ~18%) so while I don't understand the underlying mathematics, I'm at least confident that this is correct. It also contradicts my intuition which says that as the ant gets closer to the end, the rubber band stretching goes on mostly behind him and he should be able to make % increases in fewer minutes.

Anyway, here is my python script which never gets past 23% (I'm on minute 14803200000, or year 28,164): https://gist.github.com/1871474

[lotharbot]

In essence, what's being computed is the sum of 1 + 1/2 + 1/3 + 1/4 + ... (which we call the harmonic series), and you're trying to figure out how fast it reaches a given number. You've experimentally verified that it takes exponential time, which is another way of saying that the sum grows like a logarithm.

To verify this mathematically, use the "integral test" [0] twice. The linked proof shows that the sum of k terms is larger than ln(k+1). It turns out that, by drawing the rectangles under instead of above the curve, you can also show that the sum of k terms is less than 1+ln(k+1). Thus, the long-term behavior of the sum is essentially the same as the long-term behavior of a (base e) logarithm.

[0] http://en.wikipedia.org/wiki/Harmonic_series_%28mathematics%...