Cálculo de dígitos truncados sumas de poderes de pi

12

Dado un número entero positivo n , la suma de los primeros n dígitos decimales de la parte fraccionaria de π n .

Ejemplo de entradas y salidas:

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

Las funciones integradas que calculan dígitos de π o que evalúan series de potencia o fracciones continuas no están permitidas. Se aplican lagunas estándar . La entrada / salida puede estar en un formato conveniente (stdin, stdout, función in / output, etc.).

El código más corto en bytes gana.

orlp
fuente
¿Hay otras funciones trigonométricas que podrían usarse para calcular pi, pero no necesariamente de manera directa, como los argargentes o logaritmos imaginarios también prohibidos? Además, ¿hay un límite superior para n que pueda fallar después?
FryAmTheEggman
@FryAmTheEggman Si esas funciones trigonométricas pueden calcular dígitos arbitrarios de pi, entonces sí, están prohibidas. Su programa debería funcionar en teoría para cualquier n , pero se le perdona si el tiempo de ejecución o la memoria se vuelven demasiado altos.
orlp

Respuestas:

4

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]))

~ Versión 4 veces más rápida: 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]))

La entrada se toma de stdin. La salida para n = 5000 tarda aproximadamente 14 segundos con el segundo script (o 60 segundos con el primero).


Uso de la muestra:

$ 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

La fórmula utilizada es la siguiente:

donde A n es el enésimo número alterno , que se puede definir formalmente como el número de permutaciones alternas en un conjunto de tamaño n (ver también: A000111 ). Alternativamente, la secuencia se puede definir como la composición de los números de tangente y los números de la secuencia ( A 2n = S n , A 2n + 1 = T n ), más sobre eso más adelante.

El pequeño factor de corrección c n converge rápidamente a 1 cuando n se hace grande y viene dado por:

Para n = 1 , esto equivale a evaluar la Serie Leibniz . Aproximando π como 10 ½ , el número de términos requeridos puede calcularse como:

que converge (redondeado) a 17 , aunque los valores más pequeños de n requieren considerablemente más.

Para el cálculo de A n hay varios algoritmos, e incluso una fórmula explícita, pero todos ellos son cuadrática por n . Originalmente codifiqué una implementación del algoritmo de Seidel , pero resulta demasiado lento para ser práctico. Cada iteración requiere que se almacene un término adicional, y los términos aumentan en magnitud muy rápidamente (el tipo "incorrecto" de O (n 2 ) ).

El primer script usa una implementación de un algoritmo originalmente proporcionado por Knuth y Buckholtz :

Sea T 1, k = 1 para todo k = 1..n

Los valores posteriores de T están dados por la relación de recurrencia:

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

Entonces A n viene dada por T n, 1

(ver también: A185414 )

Aunque no se indica explícitamente, este algoritmo calcula tanto los números de tangente como los números de secuencia simultáneamente. El segundo script utiliza una variación de este algoritmo de Brent y Zimmermann , que calcula T o S , dependiendo de la paridad de n . La mejora es cuadrática por n / 2 , de ahí la mejora de velocidad ~ 4x.

primo
fuente
1
Excelente explicación de las matemáticas detrás de su respuesta.
Logic Knight
3

Python 2, 246 bytes

He tomado un enfoque similar a mi respuesta en Calcular π con convergencia cuadrática . La última línea toma la enésima potencia de pi y suma los dígitos. La prueba N = 5000 lleva un minuto más o menos.

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]))

Algunas pruebas:

$ 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

El código no golfista:

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]))
Caballero Lógico
fuente
Línea 8, puede girar a=jy p=ja a=p=jiirc. Tal vez.
Elias Benevedes
Gracias. Hay más optimizaciones de golf para este código, pero no será competitivo sin una reescritura usando un algoritmo sin Decimal.
Logic Knight
1

Pyth, 33

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

Basado en esta respuesta por isaacg . Probablemente podría jugar más golf. Lento.

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.
orlp
fuente
1
Esta respuesta realmente necesita al menos una explicación suficiente para justificar que calcula suficientes dígitos para obtener la respuesta correcta.
Peter Taylor
@PeterTaylor Agregaré una explicación mañana, a punto de irme a la cama.
orlp
Cada iteración produce un bit correcto (ver Apéndice A ). Los dígitos 2n deben requerir ~ 6.64n iteraciones.
primo