Invisible wrote:
> So what's the answer? I make it
> 
> .....1,549,498,368

I believe that answer is correct, although I'm not sure your reasoning 
behind the algorithm was watertight.  In particular, since you're 
applying modular exponentiation in each iteration, you're implicitly 
assuming that a^b mod m == a^(b mod m) in the next iteration. 
Fortunately this ends up bring very close to true in this case, so 
everything still works out, but to be totally safe you should really 
compute everything mod lcm(10^10,phi(10^10)) = 10^11.  Unless I was 
overly conservative in my analysis somewhere.

Now for a tricker question, say I add another loop:

n = 2
for(a = n; a > 0; a--)
   for(b = n; b > 0; b--)
     for(c = n; c > 0; c--)
       for(d = n; d > 0; d--)
         for(e = n; e > 0; e--)
           n++
print n

What are the last five digits printed?

Note that I haven't actually worked through this yet to be sure that my 
idea or solving it will actually work, so be forewarned that I'm not 
positive it's possible.

Post a reply to this message