4 ms·
Math/programming puzzle
- techiferous 16y agoThis 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.
- daeken 16y agoIt's executed once at the start of each loop, but 'n' changes each iteration. That makes it grow at an insane rate.
- techiferous 16y agoOh, right. The initializers of the inner loops will get reevaluated. Thanks. :)
- andreyf 16y agoI 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.
- fhars 16y agoSee http://en.wikipedia.org/wiki/Grahams_Number http://en.wikipedia.org/wiki/Grahams_Number
- sublimeloge 16y agoI'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.
- cperciva 16y agoThe answer given in the mailing list is correct: ...1549598368. The last 100 digits are: 7378277516597614839875462720152687058107692252615041788608016076116764404775402901225862901549498368
- andrew1 16y agoI 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.
- jules 16y ago> 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
- jules 16y agoWhat about the first 10 digits?
- didtrade 16y ago<a href="http://www.didtrade.com/ http://www.didtrade.com/ target="_blank"> www.didtrade.com </a> Online sell fashion goods,Accept PayPal.cheap replica fashion goods for sale from china free shipping <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Handbags&SmallClassName=wholesale coach" target="_blank">Coach Handbag</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Handbags&SmallClassName=Replica Chanel" target="_blank">Chanel Handbag</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Handbags&SmallClassName=Replica LV" target="_blank">Louis Vitton Handbag</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Handbags&SmallClassName=Replica Juicy" target="_blank">Juicy Handbag</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Handbags&SmallClassName=Replica Burberry" target="_blank">Burberry Handbag</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Handbags&SmallClassName=Replica Gucci" target="_blank">Gucci Handbag</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Handbags&SmallClassName=Replica Prada" target="_blank">Prada Handbag</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Handbags&SmallClassName=Replica DG Handbag" target="_blank">D&G Handbag</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Handbags&SmallClassName=Jimmy Choo Handbag" target="_blank">Jimmy Choo Handbag</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica T-shirt&SmallClassName=Polo(men)" target="_blank">Polo T-shirt</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica T-shirt&SmallClassName=AF(men)" target="_blank">A&F T-shirt</a> <a href="http://www.didtrade.com/Product.asp?BigClassName=Replica http://www.didtrade.com/Product.asp?BigClassName=Replica Suit&SmallClassName=Fashion Suit" target="_blank">Fashion Suit</a>
- btilly 16y agoThe solution to this puzzle has a lot in common with http://projecteuler.net/index.php?section=problems&id=188 http://projecteuler.net/index.php?section=problems&id=18....
- pageman 16y agoand the answer to that is ... :P
- MarkBook 16y agoIf 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
- jules 16y agoThe 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.
- 16y ago
- sublimeloge 16y agoHey 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.