Computing truncated digits sums of powers of pi 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 &rightarrow;     1
     2 &rightarrow;    14
     3 &rightarrow;     6
     4 &rightarrow;    13
     5 &rightarrow;    24
    50 &rightarrow;   211
   500 &rightarrow;  2305
  5000 &rightarrow; 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.
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&gt;&gt;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 &quot;wrong&quot; 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.