Ihr Ziel ist es, die streng ansteigende Folge von aufeinanderfolgenden, identischen Stellen von pi (π) auszugeben. Jeder Begriff in der Sequenz muss eine Ziffer länger als der vorherige sein. So 3(0 - te Ziffer von Pi) ist das erste Mal , wenn ein Lauf von Ziffern auftritt (Länge 1). Das nächste Vorkommen ist 33(Ziffern 24 und 25 von pi). Natürlich erfordert diese Sequenz, dass sich die Ziffern von pi in der Basis 10 befinden .

Die bisher bekannten und die ersten sechs kommen alle innerhalb der ersten 800 Ziffern vor:

3
33
111
9999
99999
999999
3333333
44444444
777777777
6666666666
... (not in first 2 billion digits)

Beachten Sie, dass die aufeinanderfolgenden Neunen alle zusammen im selben Durchlauf auftreten. Wenn also der nächste größere Durchlauf 1000 aufeinanderfolgende 0Sekunden enthält, werden dadurch mehrere Terme der Sequenz ausgefüllt.

Ich habe mit meinem Programm keine Begriffe mehr gefunden. Ich weiß, dass die ersten 50000 oder mehr Ziffern keine weiteren Begriffe enthalten. Mein Programm hat mit 500000 Ziffern zu lange gedauert, also habe ich aufgegeben.

Referenzimplementierung

Du darfst:

• Gib die Sequenz für immer aus
• Nimm eine ganze Zahl nund finde die ersten nZahlen in der Folge
• Nehmen Sie eine ganze Zahl nund suchen Sie die Zahlen in der Reihenfolge, die in den ersten nZiffern von pi enthalten ist.

Stellen Sie sicher, dass Sie angeben, welchen Code Ihr Code verwendet. Die Zahl nkann null oder eins sein.

Inspiriert von dieser Mathoverflow-Frage .

Mathematica, 85 Bytes

FromDigits/@DeleteDuplicatesBy[Join@@Subsets/@Split@RealDigits[Pi,10,#][[1]],Length]&

Anonyme Funktion. Nimmt n als Eingabe und gibt die Elemente der Sequenz in den ersten n Stellen von π zurück. Die Ausgabe erfolgt in Form von {0, 3, 33, 111, ...}.

Python 2, 110 Bytes

n=input()
x=p=7*n|1
while~-p:x=p/2*x/p+2*10**n;p-=2
l=m=0
for c in`x`:
 l=l*(p==c)+1;p=c
 if l>m:m=l;print p*l

Die maximale Anzahl der zu überprüfenden Stellen wird von stdin übernommen. 10.000 Stellen werden mit PyPy 5.3 in ungefähr 2 Sekunden beendet.

Beispielnutzung

$ echo 10000 | pypy pi-runs.py
3
33
111
9999
99999
999999

Etwas Nützliches

from sys import argv
from gmpy2 import mpz

def pibs(a, b):
  if a == b:
    if a == 0:
      return (1, 1, 1123)
    p = a*(a*(32*a-48)+22)-3
    q = a*a*a*24893568
    t = 21460*a+1123
    return (p, -q, p*t)
  m = (a+b) >> 1
  p1, q1, t1 = pibs(a, m)
  p2, q2, t2 = pibs(m+1, b)
  return (p1*p2, q1*q2, q2*t1 + p1*t2)

if __name__ == '__main__':
  from sys import argv
  digits = int(argv[1])

  pi_terms = mpz(digits*0.16975227728583067)
  p, q, t = pibs(0, pi_terms)

  z = mpz(10)**digits
  pi = 3528*q*z/t

  l=m=0
  x=0
  for c in str(pi):
   l=l*(p==c)+1;p=c
   if l>m:m=l;print x,p*l
   x+=1

Ich habe dafür von Chudnovsky zu Ramanujan 39 gewechselt. Chudnovsky hatte kurz nach 100 Millionen Stellen keinen Speicher mehr auf meinem System, aber Ramanujan schaffte es in nur 38 Minuten auf 400 Millionen. Ich denke, dies ist ein weiterer Fall, in dem die langsamere Wachstumsrate der Terms am Ende zumindest auf einem System mit begrenzten Ressourcen gewinnt.

Beispielnutzung

$ python pi-ramanujan39-runs.py 400000000
0 3
25 33
155 111
765 9999
766 99999
767 999999
710106 3333333
22931752 44444444
24658609 777777777
386980421 6666666666

Schnellere, unbegrenzte Generatoren

Die in der Problembeschreibung angegebene Referenzimplementierung ist interessant. Es wird ein unbegrenzter Generator verwendet, der direkt aus dem Artikel Unbounded Spigot Algorithms for the Digits of Pi stammt . Dem Autor zufolge sind die bereitgestellten Implementierungen "absichtlich undurchsichtig", weshalb ich mich entschied, alle drei vom Autor aufgelisteten Algorithmen ohne absichtliche Verschleierung neu zu implementieren. Ich habe auch eine vierte hinzugefügt, basierend auf Ramanujan # 39 .

try:
  from gmpy2 import mpz
except:
  mpz = long

def g1_ref():
  # Leibniz/Euler, reference
  q, r, t = mpz(1), mpz(0), mpz(1)
  i, j = 1, 3
  while True:
    n = (q+r)/t
    if n*t > 4*q+r-t:
      yield n
      q, r = 10*q, 10*(r-n*t)
    q, r, t = q*i, (2*q+r)*j, t*j
    i += 1; j += 2

def g1_md():
  # Leibniz/Euler, multi-digit
  q, r, t = mpz(1), mpz(0), mpz(1)
  i, j = 1, 3
  z = mpz(10)**10
  while True:
    n = (q+r)/t
    if n*t > 4*q+r-t:
      for d in digits(n, i>34 and 10 or 1): yield d
      q, r = z*q, z*(r-n*t)
    u, v, x = 1, 0, 1
    for k in range(33):
      u, v, x = u*i, (2*u+v)*j, x*j
      i += 1; j += 2
    q, r, t = q*u, q*v+r*x, t*x

def g2_md():
  # Lambert, multi-digit
  q, r, s, t = mpz(0), mpz(4), mpz(1), mpz(0)
  i, j, k = 1, 1, 1
  z = mpz(10)**49
  while True:
    n = (q+r)/(s+t)
    if n == q/s:
      for d in digits(n, i>65 and 49 or 1): yield d
      q, r = z*(q-n*s), z*(r-n*t)
    u, v, w, x = 1, 0, 0, 1
    for l in range(64):
      u, v, w, x = u*j+v, u*k, w*j+x, w*k
      i += 1; j += 2; k += j
    q, r, s, t = q*u+r*w, q*v+r*x, s*u+t*w, s*v+t*x

def g3_ref():
  # Gosper, reference
  q, r, t = mpz(1), mpz(180), mpz(60)
  i = 2
  while True:
    u, y = i*(i*27+27)+6, (q+r)/t
    yield y
    q, r, t, i = 10*q*i*(2*i-1), 10*u*(q*(5*i-2)+r-y*t), t*u, i+1

def g3_md():
  # Gosper, multi-digit
  q, r, t = mpz(1), mpz(0), mpz(1)
  i, j = 1, 60
  z = mpz(10)**50
  while True:
    n = (q+r)/t
    if n*t > 6*i*q+r-t:
      for d in digits(n, i>38 and 50 or 1): yield d
      q, r = z*q, z*(r-n*t)
    u, v, x = 1, 0, 1
    for k in range(37):
      u, v, x = u*i*(2*i-1), j*(u*(5*i-2)+v), x*j
      i += 1; j += 54*i
    q, r, t = q*u, q*v+r*x, t*x

def g4_md():
  # Ramanujan 39, multi-digit
  q, r, s ,t = mpz(0), mpz(3528), mpz(1), mpz(0)
  i = 1
  z = mpz(10)**3511
  while True:
    n = (q+r)/(s+t)
    if n == (22583*i*q+r)/(22583*i*s+t):
      for d in digits(n, i>597 and 3511 or 1): yield d
      q, r = z*(q-n*s), z*(r-n*t)
    u, v, x = mpz(1), mpz(0), mpz(1)
    for k in range(596):
      c, d, f = i*(i*(i*32-48)+22)-3, 21460*i-20337, -i*i*i*24893568
      u, v, x = u*c, (u*d+v)*f, x*f
      i += 1
    q, r, s, t = q*u, q*v+r*x, s*u, s*v+t*x

def digits(x, n):
  o = []
  for k in range(n):
    x, r = divmod(x, 10)
    o.append(r)
  return reversed(o)

Anmerkungen

Oben sind 6 Implementierungen aufgeführt: die zwei vom Autor bereitgestellten Referenzimplementierungen (bezeichnet _ref) und vier, die Terme in Stapeln berechnen, wobei mehrere Ziffern gleichzeitig generiert werden ( _md). Alle Implementierungen wurden mit 100.000 Ziffern bestätigt. Bei der Auswahl der Losgrößen habe ich Werte gewählt, die mit der Zeit langsam an Genauigkeit verlieren. Zum Beispiel g1_mderzeugt 10 Stellen pro Charge, mit 33 Iterationen. Dies ergibt jedoch nur ~ 9,93 korrekte Ziffern. Wenn die Genauigkeit nicht mehr ausreicht, schlägt die Prüfbedingung fehl und es wird ein zusätzlicher Stapel ausgeführt. Dies scheint performanter zu sein, als mit der Zeit langsam mehr und nicht mehr benötigte Präzision zu erlangen.

• g1 (Leibniz / Euler)
  Eine zusätzliche Variable jwird beibehalten und repräsentiert 2*i+1. Der Autor macht dasselbe in der Referenzimplementierung. Die Berechnung ngetrennt ist viel einfacher (und weniger dunkel), weil es die aktuellen Werte verwendet q, rund t, anstatt die nächste.
• g2 (Lambert)
  Der Scheck n == q/sist zugegebenermaßen ziemlich lasch. Das sollte heißen n == (q*(k+2*j+4)+r)/(s*(k+2*j+4)+t), wo jist 2*i-1und kist i*i. Bei höheren Iterationen, die rund twerden Begriffe immer mehr an Bedeutung. So wie es ist, ist es gut für die ersten 100.000 Stellen, also ist es wahrscheinlich gut für alle. Der Autor stellt keine Referenzimplementierung zur Verfügung.
• g3 (Gosper)
  Der Autor vermutet, dass es unnötig ist, zu überprüfen, ob nsich dies bei nachfolgenden Iterationen nicht ändert, und dass dies nur dazu dient, den Algorithmus zu verlangsamen. Wahrscheinlich stimmt das, aber der Generator behält ~ 13% mehr korrekte Ziffern bei, als er derzeit generiert hat, was etwas verschwenderisch zu sein scheint. Ich habe das Einchecken wieder aufgenommen und gewartet, bis 50 Ziffern korrekt sind, und sie alle auf einmal generiert, mit einem spürbaren Leistungsgewinn.
• g4 (Ramanujan 39)
  Berechnet als Aufgrund der anfänglichen (3528 ÷) Komposition ist es
  
  leider skeine Null, aber dennoch deutlich schneller als g3. Die Konvergenz beträgt ~ 5,89 Stellen pro Term, wobei jeweils 3511 Stellen generiert werden. Wenn das ein bisschen zu viel ist, ist das Generieren von 271 Stellen pro 46 Iterationen ebenfalls eine gute Wahl.

Timings

Auf meinem System aufgenommen, nur zu Vergleichszwecken. Die Zeiten sind in Sekunden angegeben. Wenn ein Timing länger als 10 Minuten dauerte, habe ich keine weiteren Tests durchgeführt.

            |  g1_ref |  g1_md  |  g2_md  |  g3_ref |  g3_md  |  g4_md 
------------+---------+---------+---------+---------+---------+--------
    10,000  |  1.645  |  0.229  |  0.093  |  0.312  |  0.062  |  0.062 
    20,000  |  6.859  |  0.937  |  0.234  |  1.140  |  0.250  |  0.109 
    50,000  |  55.62  |  5.546  |  1.437  |  9.703  |  1.468  |  0.234 
   100,000  |  247.9  |  24.42  |  5.812  |  39.32  |  5.765  |  0.593 
   200,000  |  2,158  |  158.7  |  25.73  |  174.5  |  33.62  |  2.156 
   500,000  |    -    |  1,270  |  215.5  |  3,173  |  874.8  |  13.51 
 1,000,000  |    -    |    -    |  1,019  |    -    |    -    |  58.02 

Es ist interessant , dass g2schließlich einholt g3, trotz einer geringeren Rate der Konvergenz. Ich vermute, das liegt daran, dass die Operanden deutlich langsamer wachsen und sich langfristig durchsetzen. Die schnellste Implementierung g4_mdist ungefähr 235x schneller als die g3_refImplementierung auf 500.000 Stellen. Das heißt, es gibt immer noch einen erheblichen Overhead für das Streamen von Ziffern auf diese Weise. Die direkte Berechnung aller Ziffern mit Ramanujan 39 ( Python-Quelle ) ist ungefähr 10-mal so schnell.

Warum nicht Chudnovsky?

Der Chudnovsky-Algorithmus erfordert eine Quadratwurzel mit voller Genauigkeit, in der ich ehrlich gesagt nicht sicher bin, wie ich arbeiten soll - vorausgesetzt, es könnte überhaupt möglich sein. Ramanujan 39 ist in dieser Hinsicht etwas Besonderes. Die Methode scheint jedoch Machin-ähnlichen Formeln, wie sie von y-cruncher verwendet werden, förderlich zu sein, so dass es sich möglicherweise um eine Möglichkeit handelt, die es wert ist, erkundet zu werden.

Haskell, 231 Bytes

import Data.List
g(q,r,t,k,n,l)|4*q+r-t<n*t=n:g(10*q,10*(r-n*t),t,k,div(10*(3*q+r))t-10*n,l)|0<1=g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)
p=nubBy(\x y->length x==length y).concatMap inits.group$g(1,0,1,1,3,3) 

Hierbei werden die Unbounded Spigot-Algorithmen für die Ziffern von Pi von Jeremy Gibbons, 2004, verwendet. Das Ergebnis ist p. Technisch sollte es unendliche Ausgabesequenzen unterstützen, aber das kann eine Weile dauern (und ist durch Ihren Speicher begrenzt).

Python 2, 298 Bytes

Beachten Sie, dass der Code zum Generieren von pi der Implementierung des OP entnommen ist.

def p():
 q,r,t,j=1,180,60,2
 while 1:
  u,y=3*(3*j+1)*(3*j+2),(q*(27*j-12)+5*r)//(5*t)
  yield y
  q,r,t,j=10*q*j*(2*j-1),10*u*(q*(5*j-2)+r-y*t),t*u,j+1
p=p()
c=r=0
d=[0]
while 1:
 t=p.next()
 if t==d[len(d)-1]:d.append(t)
 else:d=[t]
 if len(d)>r:r=len(d);print"".join([`int(x)`for x in d])
 c+=1

Mein erster Golfversuch in Python. Gibt die Sequenz für immer aus.

Python 3.5, 278 263 Bytes:

import decimal,re;decimal.getcontext().prec=int(input());D=decimal.Decimal;a=p=1;b,t=1/D(2).sqrt(),1/D(4)
for i in[1]*50:z=(a+b)/2;b=(a*b).sqrt();t-=p*(a-z)**2;a=z;p*=2;pi=(z*2)**2/(4*t);i=0;C=lambda r:re.search(r'(\d)\1{%s}'%r,str(pi))
while C(i):print(C(i));i+=1

Dies nimmt nals Eingabe die ersten nZiffern von auf πund gibt dann die Mitglieder der Sequenz in diesen ersten nZiffern aus. Hierbei wird das in Python integrierte Dezimalmodul verwendet , um die Gleitkomma-Beschränkungen von Python zu überschreiten. Anschließend wird die Genauigkeit oder das Epsilon auf die Benutzereingaben festgelegt. Zur Berechnung πwerden dann 50 Iterationen unter Verwendung des effizienten Gausse-Legendre-Algorithmus durchlaufen , da der Algorithmus anscheinend jedes Mal die Anzahl der korrekten Stellen verdoppelt, und daher können wir in 50 Iterationen auf die richtigen Stellen aufsteigen2^50 oder diese 1,125,899,906,842,624korrigieren. Nachdem die Berechnungen abgeschlossen sind, wird ein regulärer Ausdruck mit Zeichenfolgenformatierung in einer whileSchleife zum Suchen und Drucken verwendetre Übereinstimmungsobjekte (von denen ich hoffe, dass sie in Ordnung sind) für alle fortlaufenden, sich wiederholenden Ziffern, die eine Stelle länger sind als in der vorherigen Iteration durch die Schleife.

Mit diesem Algorithmus konnte ich erfolgreich und genau πbis zu 10,000,000(zehn Millionen) Stellen berechnen , was ungefähr 4 Stunden und 12 Minuten dauerte. Das Folgende war die endgültige Ausgabe:

<_sre.SRE_Match object; span=(0, 1), match='3'>
<_sre.SRE_Match object; span=(25, 27), match='33'>
<_sre.SRE_Match object; span=(154, 157), match='111'>
<_sre.SRE_Match object; span=(763, 767), match='9999'>
<_sre.SRE_Match object; span=(763, 768), match='99999'>
<_sre.SRE_Match object; span=(763, 769), match='999999'>
<_sre.SRE_Match object; span=(710101, 710108), match='3333333'> 

Ich kann also mit Sicherheit sagen, dass die achte Zahl in der Folge nicht einmal innerhalb der ersten 10 Millionen Ziffern vorkommt! πist eine Zufallszahl ...