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