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

scott wrote:
>> So the answer we seek is (approximately) 2↑↑↑2.
> 
> Isn't that 4?

No, since 2^^^2 = 2^^2^^2 = 2^^(2^2^2) = 2^^16 = 
2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2.

However, in this case you can very easily give a somewhat tighter lower 
bound of 2^^2048, that is 2^2^2^2^ ... 2048 times ... ^2^2^2

Post a reply to this message

Kevin Wampler wrote:
> 
> 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?
> 

Ok, I haven't been able to post today since I've been on airplanes on or 
airports without wireless the whole time, but I implemented the solution 
and it seems to work, so this problem is totally solvable, and only 
takes a fraction of a second on my computer.

It turns out that the solution is actually quite simple too!  Possibly 
even more so than that to the last puzzle -- although certainly not as 
mathematically concise.

Actually pretty fun, so feel free to give it a shot knowing that it does 
indeed have a relatively simple solution!

Post a reply to this message

Invisible wrote:
> 
>  (Assuming you meant the last 10 *decimal* digits...)
> 

Man, meaning the last ten binary digits would have made this the lamest 
trick question ever (so yeah, you're correct in solving for decimal 
obviously).

Post a reply to this message

scott wrote:
>> .....1,549,498,368
> 
> I recognise those last 6 digits!  I think I got them from my program, 
> but then my method was too slow to do any more digits in reasonable time.
> 

It's interesting that you had an algorithm that could compute six digits 
but not ten.  You might try running it on the second version of the 
puzzle that I gave, since I only ask for the last five digits in that 
case.  Maybe it'll work!

Post a reply to this message

>>> So the answer we seek is (approximately) 2↑↑↑2.
>>
>> Isn't that 4?
>
> No, since 2^^^2 = 2^^2^^2

I understood from wikipedia that 2^^^3 = 2^^2^^2 and 2^^^2 = 2^^2.  Is that 
wrong?

Post a reply to this message

>>> .....1,549,498,368
>>
>> I recognise those last 6 digits!  I think I got them from my program, but 
>> then my method was too slow to do any more digits in reasonable time.
>>
>
> It's interesting that you had an algorithm that could compute six digits 
> but not ten.

Well I simplified as far as Invisible did, and then didn't go through the 
modular math to simplifiy it, just applied the mod operator at various 
points in the code.  Using mod 1e5 took a fraction of a second, mod 1e6 took 
about 10 seconds, and mod 1e7 never finished!

> You might try running it on the second version of the puzzle that I gave, 
> since I only ask for the last five digits in that case.  Maybe it'll work!

Hmmm.

Post a reply to this message

Kevin Wampler wrote:

> Ok, I haven't been able to post today since I've been on airplanes on or 
> airports without wireless the whole time, but I implemented the solution 
> and it seems to work, so this problem is totally solvable, and only 
> takes a fraction of a second on my computer.
> 
> It turns out that the solution is actually quite simple too!  Possibly 
> even more so than that to the last puzzle -- although certainly not as 
> mathematically concise.
> 
> Actually pretty fun, so feel free to give it a shot knowing that it does 
> indeed have a relatively simple solution!

I have a truly marvelous proof of this, which this forum is too small to 
contain...

Post a reply to this message

On 02/07/2010 8:56 AM, Invisible wrote:
> Kevin Wampler wrote:
>
>> Ok, I haven't been able to post today since I've been on airplanes on
>> or airports without wireless the whole time, but I implemented the
>> solution and it seems to work, so this problem is totally solvable,
>> and only takes a fraction of a second on my computer.
>>
>> It turns out that the solution is actually quite simple too! Possibly
>> even more so than that to the last puzzle -- although certainly not as
>> mathematically concise.
>>
>> Actually pretty fun, so feel free to give it a shot knowing that it
>> does indeed have a relatively simple solution!
>
> I have a truly marvelous proof of this, which this forum is too small to
> contain...

LOL ;-)

-- 

Best Regards,
	Stephen

Post a reply to this message

>> I have a truly marvelous proof of this, which this forum is too small to
>> contain...
> 
> LOL ;-)

You may laugh, but for 300 years mathematicians have been unable to 
rediscover this "marvellous proof" - so excuse me if mathematicians are 
a teeny bit skeptical about sweeping claims. ;-)

Post a reply to this message