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.
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.
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.
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.
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.
21 comments
[ 3.1 ms ] story [ 60.8 ms ] threadThe last 100 digits are: 7378277516597614839875462720152687058107692252615041788608016076116764404775402901225862901549498368
As a mailing list comment points out, the effect of applying the for(c...) part to an n is:
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. so we want to find Consider a simpler question, what are the last two digits, i.e. We need one fact here to help, the periodicity of 2 ^ k mod 100 is 20, i.e. So: 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.This is not true. You need to apply the following formula n times, not 2 times (in this case n=2048).
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
Derivation comes next. DO NOT READ IF YOU WANT TO TRY IT FOR YOURSELF.
The program is
=> => => => => => Now we use the fact that we only need the last 10 digits. => => Where modexp(k,n,a) computes k^n % a by repeated squaring and internally modding intermediate values: 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.Edit: I determined this by trying a logarithmic approach, while not really thinking about what that meant.
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.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.
In this case it happens to be true, but you really should explain why.