snake arithmetic

[paradox.is.taken]

As a mathematician I really enjoyed that one. I guess the best way to solve it is to realize that the number is question is connected to the infinite sum 1/1/3+1/5/7+1/9/11+1/13/15+....

I used mathematica which instantly spit out that the answer is pi/8, so I am wondering whats the best way to prove that? I am guessing something about complex analysis when we use function with poles at a bunch of integers, but everything is blurry? Any fast cool tricks for doing that or you guys coded your way out of this one...

btw, there is a similar site www.projecteuler.net where you do little programming/math challenges very similar to the ones here (no hacking though).

[gfoot]

I just wrote a python program to sum the series - the convergence is terrible though. After summing 1/10th of the terms, the increment was small enough that the answer was within six hundred or so of the current amount, but I guessed it would be much smaller - I tried 1, 2, 3, ..., 10, 11 until the site accepted the answer. Not elegant.

[MerickOWA]

I enjoyed it. It was a good refresher on infinite series sum. I enjoyed simplifying the problem down to the point where I could actually do a summation in code.

My only problem was getting enough bits in my summation so that it would be accurate enough to get the correct answer.

[paradox.is.taken]

yeah i tried to sum it up in python but regular float didn't have enough percision, or maybe i should have just started summing it up from the smallest to the biggest ... Anyways the ratio N/D actually is a converging sum. So I just used the convergent value which is (1+7pi/8 ), now the answer for every b (big enough, like the one given) is int(b*(1+7pi/8 )). go ahead and try it

Now i feel better about having a really ugly runaway robot solver, that has been working for the last 2 days straight Currently at level 506.

[gfoot]

I liked Runaway Robot, it was interesting how at various points it scaled so badly I had to rework my algorithm, but the reworking was always quite accessible. The last few levels do seem much harder. Even though you're in sight of the finish, if you're not solving 506 in good time I imagine you'll need to optimize your algorithm before you hit 511+. It really helps - I was putting up with solve times from several minutes to several hours, until my last rewrite - now it solves them in a few seconds. I only wish the puzzle was extended so I can see just how far it can go before falling over again.

I haven't had the same feeling from any of the other puzzles - perhaps because they're harder. I nearly got it from Modulo, until I found that my genius algorithm change actually didn't help much at all.

[MerickOWA]

After thinking about Runaway robot for a bit, its easily a polynomial solution and not an exponential solution like some of the others.

It would take an extremely large instruction set with an even larger board. I think trying to generate such a board would be even more of a challenge than the solution

[bok]

Indeed, the intention of the challenge was to figure out that it was based on the convergence of the infinite series 1/1 - 1/3 + 1/5 - 1/7 + 1/9 ....
This is often called the Leibniz formula. You can find a proof for the computation at: http://en.wikipedia.org/wiki/Leibniz_formula_for_pi

The sad thing that I did not notice when I made the challenge is that it is possible to get to the answer quickly without figuring out the formula. The series converges very slowly, but if you look at the terms in the sequence, you'll see that they alternate successively above and below the limit value. And if you average one term and the next, you'll see that this average converges quite quickly.

Next time, it won't be so easy

[tails]

I have some doubt about the answer.
I think it must be 3748893571890 instead of 3748893571891.

N(4b)/D(4b)
= 1 + 7 * Sum{k=2,4,6,...,4b} 1/((2k-1)(2k-3))
= 1 + 7 * Sum{k=1,2,3,...,2b} 1/((4k-1)(4k-3))
= 1 + 7 * ( Sum{k=1,2,...,Inf} 1/((4k-1)(4k-3)) - Sum{k=2b+1,2b+2,...,Inf} 1/((4k-1)(4k-3)) )
= 1 + 7 * ( Pi/8 - Sum{k=2b+1,2b+2,...,Inf} 1/((4k-1)(4k-3)) )
~ 1 + 7 * ( Pi/8 - Integral{k=2b+1,Inf} 1/((4k-1)(4k-3)) )
~ 1 + 7 * ( Pi/8 - 3.125e-14 )
~ 1 + 7/8 Pi - 2.188e-13
~ 3.74889357189085

[dloser]

I have some doubt about the answer.
I think it must be 3748893571890 instead of 3748893571891.

I agree with tails. The program gives an approximation of the infinite sum, but there is still a small but relevant error (about 0.9). I used Mathematica's RSolve on a simplified version of the algorithm (my limited mathematics skills make me not recognise infinite sums, apparently; not that it would have helped me). This essentially gives me a term "S + a ( PolyGamma[3/8 + x/2] - PolyGamma[1/8 + x/2] )" (where PolyGamma is the "digamma function", if that helps anyone). For big x (and especially b), the two PolyGamma terms almost cancel each other out, but not completely at the given precision.

As for the proving question of paradox.is.taken, I would suggest first deriving a nice recursive definition of the function lambda x. (N(4*x)*b)/D(4*x) (the relevance of which becomes clear when when unfolding N once in the original expression, if it wasn't clear already). Then, as you get something of the form f(x+2) = f(x)+g(x), it is probably easiest to make variants f2 and g2 with f2(x) = f(2x) and g2(x) = g(2x). This f2 can be easily written as (b plus) a sum (for 1 to x) over g2. As g2(x) is of the form c/(d-x+x^2), I guess you should recognise the sum as something similar to the polygamma/digamma function. The only two differences are that digamma corresponds to an infinite sum and sums a term of the form 1/(e*x+x^2). The first is easily overcome by writing the sum over g2 as an infinite sum minus another infinite sum (leaving only the first x terms).

The only thing I don't see yet is how to get the 1/(e*x+x^2) form. However, in the PolyGammas in the term above (which should correspond to the "minus another infinite sum"; the PolyGammas for the first infinite sum are hidden in S as they do not depend on x), strongly indicates where the solution to this part can be found.

In any case, thanks for the very nice challenge. For me it's one of those challenges which you are able to do on your own but still teach you something you didn't know in the end. Those are the best.

Edit: corrected some wrong observations.

[nighthalk]

after refinding it to 1/3/5+1/7/9+1/11/13..... i let python go to about 100000 then purly to see if it happened to match anything i did devide by pi and noticed Decimal('0.12499998215157996184') so i was like "hmmmm" 1+7/8*PI() in excel, looked right, did it in python times by 10^11 got working answer =P converges HORRIBLY slow otherwise.

[MyNameIsAlreadyTaken]

The first time I tried to solve it, I seem to have made a mistake in my calculation.

However, when I tried it again, I was able to simplify the formula to:

f(n) := D(n)/N(n)
f(n) = f(n - 2) + 7/2 * (1/(2n - 1) - 1/(2n - 3))

After some trial and error, I found the taylorseries of arctan() and could calculate the solution using my calculator:
floor(((arctan(1))*7/2 + 1) * b)

[laz0r]

I, too, used Mathematica to get a solution of 3748893571890 (one less than the accepted answer):

Code: Select all

In[1]:= RSolve[{d[0] == 1, d[n] == (2 n - 1) d[n - 1]}, d[n], n]
Out[1]= {{d[n] -> 2^(-1 + n) Pochhammer[3/2, -1 + n]}}
In[2]:= d[n_] := 2^(-1 + n) Pochhammer[3/2, -1 + n]

In[3]:= RSolve[{defn[0] == 1, defn[1] == 1, 
  defn[n] == (4 n^2 - 8 n + 3) defn[n - 2] + 7 d[n - 2]}, defn[n], n]

Out[3]= {{defn[n] -> (1/(8 (1 + 2 n) Sqrt[\[Pi]]))
   Gamma[1/2 + n] (-7 (-1)^n 2^(1 + n) - 7 (-1)^(2 n) 2^(1 + n) + 2^(
      3 + n) + 11 2^(2 + n) n - 7 (-1)^n 2^(2 + n) n + 
      7 (-2)^n \[Pi] + 7 (-1)^n 2^(1 + n) n \[Pi] + 
      7 (-1)^(2 n) 2^(1 + n) LerchPhi[-1, 1, 3/2 + n] + 
      7 (-1)^(2 n) 2^(2 + n) n LerchPhi[-1, 1, 3/2 + n])}}
In[4]:= defn[n_] := 
 1/(8 (1 + 2 n) Sqrt[\[Pi]])
   Gamma[1/2 + n] (-7 (-1)^n 2^(1 + n) - 7 (-1)^(2 n) 2^(1 + n) + 2^(
    3 + n) + 11 2^(2 + n) n - 7 (-1)^n 2^(2 + n) n + 7 (-2)^n \[Pi] + 
    7 (-1)^n 2^(1 + n) n \[Pi] + 
    7 (-1)^(2 n) 2^(1 + n) LerchPhi[-1, 1, 3/2 + n] + 
    7 (-1)^(2 n) 2^(2 + n) n LerchPhi[-1, 1, 3/2 + n])

In[5]:= FullSimplify[
 Quotient[defN[b*4]*b, defD[b*4]], {b > 0, Element[b, Integers]}]

Out[5]= Floor[
 1/8 b (8 + 7 \[Pi] + 7 PolyGamma[0, 1/4 + 2 b] - 
    7 PolyGamma[0, 3/4 + 2 b])]

In[6]:= %5 /. b -> 1000000000000

Out[6]= 3748893571890

Also a slightly less readable but far more concise one:

Code: Select all

FullSimplify[
  Quotient[n[4 i] i, d[4 i]] //. 
   Flatten@{First@
      RSolve[n[0] == 1 && n[1] == 1 && 
        n[i] == (4 i i - 8 i + 3) n[i - 2] + 7 d[i - 2], n, i],
     First@RSolve[d[0] == 1 && d[i] == d[i - 1] (2 i - 1), d, i]}, 
  i \[Element] Integers && i > 0] /. i -> 1000000000000

[Hippo]

I computed it by pencil and paper I got 1+7/8\pi as the limit ratio so scaling it to 13 digits gave the answer but the answer was not accepted . I bet the tail should be small so I guessed one less, two less, htree less ... and they were not accepted either. So I tried one more, even when I know the sequence is growing to the limit ... and it was accepted.

[outsider]

I used the value of 8/pi form OEIS and got 3748893571891.069, so the accepted answer is the exact solution.
But as tails pointed out correctly the the correct solution should by one less, because the python code is only a approximation.
I think the poster of this challenge hasn't run the python code himself

[Hippo]

I used the value of 8/pi form OEIS and got 3748893571891.069, so the accepted answer is the exact solution.
But as tails pointed out correctly the the correct solution should by one less, because the python code is only a approximation.
I think the poster of this challenge hasn't run the python code himself

I must agree, my fault I have used 3141592653589*7/8+1000000000000
as approxmation, but 3141592653589793238462*7/8+1000000000000000000000 shows I had to be more accurate.