Math/programming puzzle | Hacker News Reader

Math/programming puzzle

news.povray.org

44 pointsdaeken19 comments

The answer given in the mailing list is correct: ...1549598368.

The last 100 digits are: 7378277516597614839875462720152687058107692252615041788608016076116764404775402901225862901549498368

I think you're wrong (although I could just be being silly..).

As a mailing list comment points out, the effect of applying the for(c...) part to an n is:

    fc(n) = n * (2 ^ n) * (2 ^ (n * (2 ^ n))

So the first iteration of the d variable sets n = fc(n), then the second sets it to fc(fc(n)), which is the answer.

    fc(2) = 2 * (2 ^ 2) * (2 ^ (2 * (2 ^ 2)) = 2048

so we want to find

    fc(2048) mod (10 ^ 10).

Consider a simpler question, what are the last two digits, i.e.

    fc(2048) mod 100

We need one fact here to help, the periodicity of 2 ^ k mod 100 is 20, i.e.

    2 ^ (20q + r) = 2 ^ r mod 100

So:

    fc(2048) mod 100
    = 2048 * (2 ^ 2048) * (2 ^ (2048 * (2 ^ 2048)) = 
    =   48 * (2 ^    8) * (2 ^ (   8 * (2 ^    8)) [we can reduce all exponents mod 20, same in all below lines]
    =   48 * 256        * (2 ^ (   8 * 256 ) )
    =   48 *  56        * (2 ^ 2048)
    =   48 *  56        * (2^8)
    =   28 *  56        * 56
    =   150528
    = 28.

So I think that the last two digits should be 28. I don't know what the answer is for the last 10 digits though.

> As a mailing list comment points out, the effect of applying > the for(c...) part to an n is: > fc(n) = n * (2 ^ n) * (2 ^ (n * (2 ^ n))

This is not true. You need to apply the following formula n times, not 2 times (in this case n=2048).

    n <- n*2^n

What about the first 10 digits?

The answer is 1549498368.

Derivation comes next. DO NOT READ IF YOU WANT TO TRY IT FOR YOURSELF.

The program is

    n = 2
    n times:
      n times: 
         n times:
           n times:
             n++

    n = 2
    n times:
      n times: 
         n times:
           n = 2*n

    n = 2
    n times:
      n times: 
         n = n*2^n

    n = 2
    2 times:
      n times: 
         n = n*2^n

    n = 2
    2 times: 
      n = n*2^n
    n times: 
      n = n*2^n

    n = 2
    n = n*2^n
    n = n*2^n
    n times: 
      n = n*2^n

    n = 2048
    2048 times: 
      n = n*2^n

Now we use the fact that we only need the last 10 digits.

    n = 2048
    2048 times: 
      n = (n*2^n) % 10^10

    n = 2048
    2048 times: 
      n = (n*(2^n % 10^10)) % 10^10

    n = 2048
    2048 times: 
      n = (n*modexp(2,n,10^10)) % 10^10

Where modexp(k,n,a) computes k^n % a by repeated squaring and internally modding intermediate values:

    modexp(k,2*n,a) = modexp(k,n,a)**2 % a
    modexp(k,2*n+1,a) = k*modexp(k,2*n,a) % a

When we run this we get the answer 1549498368. This algorithm can also compute more digits efficiently by setting 10^10 higher. Computing 100 digits takes a couple of seconds in Ruby.

    n = 2048
    2048 times: 
      n = n*2^n
   Now we use the fact that we only need the last 10 digits.
    n = 2048
    2048 times: 
      n = (n*2^n) % 10^10

CHEAT! x^y mod N is not necessarily the same as x^(y mod N) mod N.

In this case it happens to be true, but you really should explain why.

Hmm, yes indeed. 2^(10^10) is not 1 mod 10^10, so I don't know. Please enlighten us!

The key is that 2^(10^10) is 1 mod 5^10, and 2^n is always 0 mod 2^10 (for the relevant values of n).

Wow, there are more bits in this, after the third iteration (that is, of n = 2048; 2048 times: n = n * 2 ^ n), than there are atoms in the universe. By about 537 orders of magnitude, no less. Don't think we're getting the full value any time soon.

Edit: I determined this by trying a logarithmic approach, while not really thinking about what that meant.

  n = 11 # 1 << 11 == 2048
  for i in range(2048):
  	print i, n
  	n += 2 ** n

At any point, 1 << n is equivalent to the same thing calculated via n = 2 * n. This works because n is always a power of 2, but it's really only gets you one step closer to the answer. With how many bits are involved here, I can't see how you could possibly calculate this in our universe.

Looking at the number of bits doesn't meaningfully change the size of numbers this big ;)

You couldn't store the number explicitly in this universe, but perhaps you could find a relatively cheap formula for the n-th digit of the number.

Hey all, puzzle poser from the Povray thread here. If you want a somewhat trickier version, try giving the last five digits of the case where you have 100 nested loops (instead of just four). It requires a very different, but oddly satisfying approach.

I have a feeling there is no closed-form equasion for a variable number of "levels" of such for loops. There should definitely be a recursive one, however. Would be interesting to define a new notation for such recursive forms.

I've always noted it as Sigma_loop, since it's basically the busy-beaver function for a programming language with no recursion and in which the bounds of every loop must stay fixed throughout the loop.

See http://en.wikipedia.org/wiki/Grahams_Number

The solution to this puzzle has a lot in common with http://projecteuler.net/index.php?section=problems&id=18....

If this were ancient times the Greeks would spend endless hours proving this whilst the Romans would just fire up VB VI and get an answer.

Dim a As Integer, b As Integer, c As Integer, d As Integer, n As Integer

n = II For b = n To I Step -I For c = n To I Step -I For d = n To I Step -I n = n + I Debug.Print n Next d Next c Next b

And the answer is MMXCVIII

This is probably not in the spirit of the pseudocode, but I expected that each loop would only execute twice, because the initializer part of each loop (a=n,b=n,c=n,d=n) would be evaluated only once at the start of each loop, so all variables would be set to 2.

It's executed once at the start of each loop, but 'n' changes each iteration. That makes it grow at an insane rate.

Oh, right. The initializers of the inner loops will get reevaluated. Thanks. :)

Reply on news.ycombinator.com