Berechnen von abgeschnittenen Ziffernsummen von Potenzen von pi

12

Bei einer positiven Ganzzahl n wird die Summe der ersten n Dezimalstellen des Bruchteils von π n ausgegeben .

Beispiel Ein- und Ausgänge:

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

Eingebaute Funktionen, die Ziffern von π berechnen oder entweder Potenzreihen oder fortgesetzte Brüche auswerten, sind nicht zulässig. Standard-Schlupflöcher gelten . Die Ein- / Ausgabe kann in einem praktischen Format erfolgen (stdin, stdout, Funktion in / output usw.).

Kürzester Code in Bytes gewinnt.

orlp
quelle
Sind andere Triggerfunktionen, die zur Berechnung von pi verwendet werden könnten, aber nicht unbedingt direkt, wie Arcustangens- oder imaginäre Logarithmen, ebenfalls verboten? Gibt es auch eine Obergrenze für n, nach der ein Fehler auftreten kann?
FryAmTheEggman
@FryAmTheEggman Wenn diese Triggerfunktionen beliebige Ziffern von pi berechnen können, dann sind sie ja verboten. Ihr Programm sollte theoretisch für jedes n funktionieren , aber es wird vergeben, wenn entweder die Laufzeit oder der Speicher zu hoch wird.
Orlp

Antworten:

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

~ 4x schnellere 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]))

Die Eingabe erfolgt aus stdin. Die Ausgabe für n = 5000 dauert mit dem zweiten Skript ca. 14 Sekunden (mit dem ersten Skript ca. 60 Sekunden).


Beispielnutzung:

$ 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

Die verwendete Formel lautet wie folgt:

wo A n ist die n - te Alternating Anzahl , die formal als die Anzahl der alternierenden Permutationen auf einem Satz von Größe definiert werden kann n (siehe auch: A000111 ). Alternativ kann die Sequenz als die Zusammensetzung der Tangentenzahlen und Sekantenzahlen ( A 2n = Sn , A 2n + 1 = Tn ) definiert werden, dazu später mehr.

Der kleine Korrekturfaktor c n konvergiert schnell gegen 1, wenn n groß wird, und ist gegeben durch:

Für n = 1 bedeutet dies die Auswertung der Leibniz-Reihe . Annähern π als 10 ½ , kann die Anzahl der Begriffe erforderlich wie folgt berechnet:

die konvergiert (aufgerundet) auf 17 , obwohl kleinere Werte von n wesentlich mehr erfordern.

Für die Berechnung von A n gibt es mehrere Algorithmen und sogar eine explizite Formel, aber alle von ihnen durch quadratische sind n . Ich habe ursprünglich eine Implementierung von Seidels Algorithmus codiert , aber es wird zu langsam, um praktisch zu sein. Für jede Iteration muss ein zusätzlicher Term gespeichert werden, und der Betrag der Terme nimmt sehr schnell zu (die "falsche" Art von O (n 2 ) ).

Das erste Skript verwendet eine Implementierung eines Algorithmus, der ursprünglich von Knuth und Buckholtz angegeben wurde :

Sei T 1, k = 1 für alle k = 1..n

Nachfolgende Werte von T sind durch die Wiederholungsbeziehung gegeben:

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

A n ist dann gegeben durch T n, 1

(siehe auch: A185414 )

Obwohl nicht explizit angegeben, berechnet dieser Algorithmus gleichzeitig die Tangentenzahlen und die Sekantenzahlen. Das zweite Skript verwendet eine Variation dieses Algorithmus von Brent und Zimmermann , die je nach Parität von n entweder T oder S berechnet . Die Verbesserung ist quadratisch um n / 2 , daher die Verbesserung der Geschwindigkeit um das Vierfache.

primo
quelle
1
Hervorragende Erklärung der Mathematik hinter Ihrer Antwort.
Logic Knight
3

Python 2, 246 Bytes

Ich habe eine ähnliche Herangehensweise an meine Antwort bei π mit quadratischer Konvergenz berechnen . Die letzte Zeile nimmt die N-te Potenz von pi und summiert die Ziffern. Der N = 5000-Test dauert ungefähr eine Minute.

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

Einige 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

Der 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]))
Logik-Ritter
quelle
Linie 8, können Sie drehen a=jund p=jzu a=p=jiirc. Könnte sein.
Elias Benevedes
Vielen Dank. Es gibt weitere Golf-Optimierungen für diesen Code, aber er wird ohne ein Umschreiben mit einem Algorithmus ohne Dezimalzahl nicht wettbewerbsfähig sein.
Logic Knight
1

Pyth, 33

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

Basierend auf dieser Antwort von isaacg . Könnte wahrscheinlich mehr Golf gespielt werden. Schleppend.

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
quelle
1
Diese Antwort benötigt wirklich mindestens eine ausreichende Erklärung, um zu rechtfertigen, dass sie genügend Ziffern berechnet, um die richtige Antwort zu erhalten.
Peter Taylor
@PeterTaylor Ich werde morgen eine Erklärung hinzufügen, kurz bevor ich ins Bett gehe.
Orlp
Jede Iteration erzeugt ein korrektes Bit (siehe Anhang A ). 2n Ziffern sollten ~ 6.64n Iterationen erfordern.
Primo