I was going through some old stuff on my hard drive, and I came across a 
small code snippet which led to a cute little problem:

I have a number which is defined with the following bit of pseudocode, 
with all variables representing ideal mathematical integers:

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

What are the last 10 digits of the result printed by this program?

Post a reply to this message

I just spotted a typo:  The code should obviously read:

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--)
         n++;
print n

Since the version I gave didn't terminate!


Kevin Wampler wrote:
> I was going through some old stuff on my hard drive, and I came across a 
> small code snippet which led to a cute little problem:
> 
> I have a number which is defined with the following bit of pseudocode, 
> with all variables representing ideal mathematical integers:
> 
> n = 2
> for(a = n; a > 0; a--)
>   for(b = n; b > 0; b--)
>     for(c = n; c > 0; c--)
>       for(d = n; n > 0; d--)
>         n++;
> print n
> 
> What are the last 10 digits of the result printed by this program?

Post a reply to this message

Kevin Wampler wrote:

> 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--)
>         n++;
> print n

Damned mutable state! >_<

OK, well

   for(d=n; d>0; d--) n++;

is equivilent to

   n = 2*n;

so we have

   for(c=n;c>0;c--) n = 2*n;

which is

   n = n * 2^n;

so now we have

   for(b=n;b>0;b--) n = n * 2^n;

Now there's trouble. You see, initially we have

   n[0] = n

On the next iteration we have

   n[1] = n[0] 2^n[0] = n 2^n

But then we have

   n[2] = n[1] 2^n[1] = (n 2^n) 2^(n 2^n)

You can simplify this to

   n[2] = n 2^(n + n 2^n)

but that's still quite complex. More to the point, on the next iteration 
it'll get even more complex, and I don't see a closed-form solution to this.

More to the point, by the time a=1, n=2048. That means that the b-loop 
runs 2048 times. And when you consider that 2048 * 2^2048 is

6618522843404494295186406745839606161498952226757731129780294743557
0493724401440549267868490798926773634494383968047143923956857140205
4064027405360874460838310520368482324399959044049927980075147183260
4341057037983087046378008526061944441720519919712375121070497035272
7833755425876102776028267313405809429548880554782040765277562828362
8842383254654485203483075749433459903099416426669267233797295981858
3473505473250041540988386836142315991377081221877271190177224955315
3402287759789517121744336755350465901655205184917370974202405586941
2110653955407655676631932971733672542303136122441829419995004023881
95450053080383488

(i.e., 6.618 * 10^619), you realise that the very next iteration is 
going to produce some absurdly *huge* number. This explains why the 
program I wrote eats several GB of RAM without ever coming up with an 
answer.

The difficulty, then, is coming up with an algorithm to compute the 
least-significant digits of λ n → n 2^n without computing the entire 
number. I'll have to go check my number theory; I don't recall the exact 
details of the algorithm.

Post a reply to this message

Invisible wrote:

> The difficulty, then, is coming up with an algorithm to compute the 
> least-significant digits of λ n → n 2^n without computing the entire 
> number. I'll have to go check my number theory; I don't recall the exact 
> details of the algorithm.

You're asking for the last 10 digits of the answer. In other words, the 
answer modulo 10^10. (Assuming you meant the last 10 *decimal* digits...)

In modular arithmetic,

   (X mod M) * (Y mod M) = (X * Y) mod M

In other words, we can reduce our running total to the least positive 
reside class mod 10^10 and still get the same answer. Handling 
billion-digit numbers is quite expensive, but piffling 10-digit numbers 
are no match for the GMP.

Unfortimately,

   (X mod M)^(Y mod M) ≠ (X^Y) mod M

But fortunately,

   (X mod M)^Y = (X^Y) mod M

due to the first theorum. Better still,

   A+B = Y ⇒ (X mod M)^A * (X mod M)^B = (X^Y) mod M

by the usual first law of logarithms. This gives us the binary 
exponentiation algorithm:

   x = 1;
   b = base;
   e = exponent;
   while (e>0)
     if odd(e) then x = x*b mod m;
     e = shift_right(e);
     b = b*b mod m;

At any time, you need to deal with numbers containing at most 20 digits.

So what's the answer? I make it

.....1,549,498,368

It took about 0.2 seconds to compute. I have very little confidence that 
this is correct though.

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.

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.

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