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.

  • \$\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\$ Commented Mar 26, 2015 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
    Commented Mar 26, 2015 at 18:25

3 Answers 3


Python - 191 Bytes

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

for k in range(1,n):
 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

$ echo 2 | python pi-trunc.py

$ echo 3 | python pi-trunc.py

$ echo 4 | python pi-trunc.py

$ echo 5 | python pi-trunc.py

$ echo 50 | python pi-trunc.py

$ echo 500 | python pi-trunc.py

$ echo 5000 | python pi-trunc.py

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.

  • 1
    \$\begingroup\$ Excellent explanation of the maths behind your answer. \$\endgroup\$ Commented May 30, 2015 at 3:33

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*
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
print sum(map(int,`l**N`.split('.')[1][:N]))

Some tests:

$ echo 1 | python soln.py
$ echo 3 | python soln.py
$ echo 5 | python soln.py
$ echo 500 | python soln.py
$ echo 5000 | python soln.py

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]))
  • \$\begingroup\$ Line 8, you can turn a=j and p=j to a=p=j iirc. Maybe. \$\endgroup\$ Commented May 29, 2015 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\$ Commented May 30, 2015 at 3:37

Pyth, 33


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 + ...))))
        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).
    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.
  • 1
    \$\begingroup\$ This answer really needs at least sufficient explanation to justify that it computes enough digits to get the right answer. \$\endgroup\$ Commented Mar 27, 2015 at 8:38
  • \$\begingroup\$ @PeterTaylor I'll add an explanation tomorrow, just about to go to bed. \$\endgroup\$
    – orlp
    Commented Mar 27, 2015 at 9:05
  • \$\begingroup\$ Each iteration produces one correct bit (see Appendix A). 2n digits should require ~6.64n iterations. \$\endgroup\$
    – primo
    Commented May 29, 2015 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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