3 ms·
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:
by jules 16y ago
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.
- daeken 16y agoWow, 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.
- jules 16y agoLooking 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.
- cperciva 16y agon = 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.