12
\$\begingroup\$

Given a positive integer n output the sum of the first n decimal digits of the fractional part of πn.

Example input and outputs:

1 → 1
2 → 14
3 → 6
4 → 13
5 → 24
50 → 211
500 → 2305
5000 → 22852

Built-in functions computing digits of π or evaluating either power series or continued fractions are not allowed. Standard loopholes apply. Input/output can be in a convenient format (stdin, stdout, function in/output, etc).

Shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Are other trig functions that could be used to calculate pi, but not necessarily directly, like arctangent or imaginary logarithms also banned? Also, is there an upper limit to n that it can fail after? \$\endgroup\$ – FryAmTheEggman Mar 26 '15 at 18:22
  • \$\begingroup\$ @FryAmTheEggman If those trig functions can compute arbitrary digits of pi, then yes they're banned. Your program should work in theory for any n, but it's forgiven if either runtime or memory becomes too high. \$\endgroup\$ – orlp Mar 26 '15 at 18:25
4
\$\begingroup\$

Python - 191 Bytes

t=i=1L;k=n=input();f=2000*20**n;A=range(n+1)
for k in range(2,n):A=[(A[j-1]+A[j+1])*j>>1for j in range(n-k+1)];f*=k
while k:k=(1-~i*n%4)*f/A[1]/i**n;t+=k;i+=2
print sum(map(int,`t`[-n-4:-4]))

~4x faster version - 206 bytes

t=i=1L;k=n=input();f=2000*20**n;A=[0,1]+[0]*n
for k in range(1,n):
 f*=k
 for j in range(-~n/2-k+1):A[j]=j*A[j-1]+A[j+1]*(j+2-n%2)
while k:k=(1-~i*n%4)*f/A[1]/i**n;t+=k;i+=2
print sum(map(int,`t`[-n-4:-4]))

Input is taken from stdin. Output for n = 5000 takes approximately 14s with the second script (or 60s with the first).


Sample usage:

$ echo 1 | python pi-trunc.py
1

$ echo 2 | python pi-trunc.py
14

$ echo 3 | python pi-trunc.py
6

$ echo 4 | python pi-trunc.py
13

$ echo 5 | python pi-trunc.py
24

$ echo 50 | python pi-trunc.py
211

$ echo 500 | python pi-trunc.py
2305

$ echo 5000 | python pi-trunc.py
22852

The formula used is the following:

where An is the nth Alternating Number, which can be formally defined as the number of alternating permutations on a set of size n (see also: A000111). Alternatively, the sequence can be defined as the composition of the Tangent Numbers and Secant Numbers (A2n = Sn, A2n+1 = Tn), more on that later.

The small correction factor cn rapidly converges to 1 as n becomes large, and is given by:

For n = 1, this amounts to evaluating the Leibniz Series. Approximating π as 10½, the number of terms required can be calculated as:

which converges (rounded up) to 17, although smaller values of n require considerably more.

For the calculation of An there are several algorithms, and even an explicit formula, but all of them are quadratic by n. I originally coded an implementation of Seidel's Algorithm, but it turns to be too slow to be practical. Each iteration requires an additional term to be stored, and the terms increase in magnitude very rapidly (the "wrong" kind of O(n2)).

The first script uses an implementation of an algorithm originally given by Knuth and Buckholtz:

Let T1,k = 1 for all k = 1..n

Subsequent values of T are given by the recurrence relation:

Tn+1,k = 1/2 [ (k - 1) Tn,k-1 + (k + 1) Tn,k+1 ]

An is then given by Tn,1

(see also: A185414)

Although not explicitly stated, this algorithm calculates both the Tangent Numbers and the Secant Numbers simultaneously. The second script uses a variation of this algorithm by Brent and Zimmermann, which calculates either T or S, depending on the parity of n. The improvement is quadratic by n/2, hence the ~4x speed improvement.

\$\endgroup\$
  • 1
    \$\begingroup\$ Excellent explanation of the maths behind your answer. \$\endgroup\$ – Logic Knight May 30 '15 at 3:33
3
\$\begingroup\$

Python 2, 246 bytes

I have taken a similar approach to my answer at Calculate π with quadratic convergence . The last line takes the Nth power of pi and sums the digits. The N=5000 test takes a minute or so.

from decimal import*
d=Decimal
N=input()
getcontext().prec=2*N
j=d(1)
h=d(2)
f=h*h
g=j/h
a=j
b=j/h.sqrt()
t=j/f
p=j
for i in bin(N)[2:]:e=a;a,b=(a+b)/h,(a*b).sqrt();c=e-a;t-=c*c*p;p+=p
k=a+b
l=k*k/f/t
print sum(map(int,`l**N`.split('.')[1][:N]))

Some tests:

$ echo 1 | python soln.py
1
$ echo 3 | python soln.py
6
$ echo 5 | python soln.py
24
$ echo 500 | python soln.py
2305
$ echo 5000 | python soln.py
22852

The ungolfed code:

from decimal import *
d = Decimal

N = input()
getcontext().prec = 2 * N

# constants:
one = d(1)
two = d(2)
four = two*two
half = one/two

# initialise:
a = one
b = one / two.sqrt()
t = one / four
p = one

for i in bin(N)[2:] :
    temp = a;
    a, b = (a+b)/two, (a*b).sqrt();
    pterm = temp-a;
    t -= pterm*pterm * p;
    p += p

ab = a+b
pi = ab*ab / four / t
print sum(map(int, `pi ** N`.split('.')[1][:N]))
\$\endgroup\$
  • \$\begingroup\$ Line 8, you can turn a=j and p=j to a=p=j iirc. Maybe. \$\endgroup\$ – Elias Benevedes May 29 '15 at 16:01
  • \$\begingroup\$ Thanks. There are more golfing optimisations for this code, but it will not be competitive without a rewrite using an algorithm without Decimal. \$\endgroup\$ – Logic Knight May 30 '15 at 3:37
1
\$\begingroup\$

Pyth, 33

s<>j^u+/*GHhyHy^TyQr*TQ0ZQT_y*QQQ

Based on this answer by isaacg. Could probably be golfed more. Slow.

s<>j            Digit sum of...
  ^                 
    u               Evaluate pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + ...))))
      +
        /
          *GH
          hyH
        y^TyQ       Except we generate a large integer containing 2n digits,
                    rather than a fraction.
      r*TQ0         Experimentally verified that 10*n iterations will give enough
                    precision for 2n digits (# digits correct grows faster than 2n).
      Z
    Q               To the nth power.
  T_y*QQQ         Get the last 2n^2 digits (all the fractional digits) and get the
                  first n fractional digits.
\$\endgroup\$
  • 1
    \$\begingroup\$ This answer really needs at least sufficient explanation to justify that it computes enough digits to get the right answer. \$\endgroup\$ – Peter Taylor Mar 27 '15 at 8:38
  • \$\begingroup\$ @PeterTaylor I'll add an explanation tomorrow, just about to go to bed. \$\endgroup\$ – orlp Mar 27 '15 at 9:05
  • \$\begingroup\$ Each iteration produces one correct bit (see Appendix A). 2n digits should require ~6.64n iterations. \$\endgroup\$ – primo May 29 '15 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.