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.).
code-golf
math
arithmetic
pi
orlp
fuente
fuente
Respuestas:
Python - 191 bytes
~ Versión 4 veces más rápida: 206 bytes
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:
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 :
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.
fuente
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.
Algunas pruebas:
El código no golfista:
fuente
a=j
yp=j
aa=p=j
iirc. Tal vez.Pyth, 33
Basado en esta respuesta por isaacg . Probablemente podría jugar más golf. Lento.
fuente