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.

Heh. Could be just fluke.

I'm still not 100% certain that my program works. For example, the 
exponent is reduced as per the modulus too, which could affect the 
answer. As a quick check, I tried rerunning with 20 digits:

.......1,225,862,901,549,498,368

So the digits don't change by making the calculation wider. Which 
presumably means it's wide enough not to screw up the answer. (Or it's a 
very big fluke. You never know - mathematics is like that!)

Post a reply to this message

> I'm still not 100% certain that my program works. For example, the 
> exponent is reduced as per the modulus too, which could affect the 
> answer. As a quick check, I tried rerunning with 20 digits:
> 
> .......1,225,862,901,549,498,368

Next task, give us some indication of how big n is :-)

Post a reply to this message

scott wrote:

> Next task, give us some indication of how big n is :-)

I can see I won't get much work done today...



OK, well we have

   d = λ n → n 2
   c = λ n → n 2^n
   b = λ n → c@n n
   a = λ n → b@n n

where "b@n" means "b applied n times".

If n = 100, then 2^n ≈ 10^30, while is a mere 10^2 times larger. As n 
becomes larger, the difference becomes more and more insignificant. So, 
we can approximate with

   c = λ n → 2^n

On that bases, the final result is guaranteed to be an exact power of 2. 
We just need to figure out which one.

Using Knuth's "up-arrow notation", we have

   c = λ n → 2↑n
   b = λ n → 2↑↑n
   a = λ n → 2↑↑↑n

So the answer we seek is (approximately) 2↑↑↑2. In other words, the 
pentation of 2 with 2. Unfortunately, I don't know of any efficient way 
to compute the size of this ludicrously massive quantity.

Post a reply to this message

> So the answer we seek is (approximately) 2↑↑↑2.

Isn't that 4?

Post a reply to this message

Invisible wrote:
> 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.
> 
> Heh. Could be just fluke.

Nah. That would be a one in a million chance.

Wait, no, one in a million chances work out all the time!

-- 
Darren New, San Diego CA, USA (PST)
    C# - a language whose greatest drawback
    is that its best implementation comes
    from a company that doesn't hate Microsoft.

Post a reply to this message

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