Votre objectif est de produire la séquence strictement croissante de chiffres consécutifs identiques de pi (π). Chaque terme de la séquence doit avoir un chiffre de plus que le précédent. Donc 3(0ème chiffre de pi) est la première fois qu'une série de chiffres se produit (longueur 1). Le prochain à se produire est 33(chiffres 24 et 25 de pi). Bien sûr, cette séquence nécessite que les chiffres de pi soient en base 10 .

Ceux connus jusqu'à présent , et les six premiers se produisent tous dans les 800 premiers chiffres:

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

Notez que les neuf consécutifs se produisent tous ensemble, dans la même exécution, donc si la prochaine exécution plus importante que vous avez trouvée était de 1000 0s consécutifs , cela remplirait plusieurs termes de la séquence.

Je n'ai plus trouvé de termes avec mon programme. Je sais qu'il n'y a plus de termes dans les 50000 premiers chiffres ou plus. Mon programme prenait trop de temps avec 500 000 chiffres, j'ai donc abandonné.

Implémentation de référence

Tu peux:

• Sortez la séquence pour toujours
• Prenez un entier net trouvez les premiers nnombres de la séquence
• Prenez un entier net trouvez les nombres dans la séquence contenue dans les premiers nchiffres de pi.

Assurez-vous de spécifier celui que votre code fait. Le nombre npeut être zéro ou un indexé.

Inspiré par cette question mathoverflow .

Mathematica, 85 octets

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

Fonction anonyme. Prend n en entrée et renvoie les éléments de la séquence dans les n premiers chiffres de π. La sortie est sous la forme de {0, 3, 33, 111, ...}.

Python 2, 110 octets

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

Le nombre maximum de chiffres à vérifier est pris à partir de stdin. 10000 chiffres se termine en environ 2s avec PyPy 5.3.

Exemple d'utilisation

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

Quelque chose d'utile

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

Je suis passé de Chudnovsky à Ramanujan 39 pour cela. Chudnovsky a manqué de mémoire sur mon système peu de temps après 100 millions de chiffres, mais Ramanujan est arrivé à 400 millions, en seulement 38 minutes environ. Je pense que c'est un autre cas où le taux de croissance plus lent des termes l'emporte finalement, au moins sur un système avec des ressources limitées.

Exemple d'utilisation

$ 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

Des générateurs illimités plus rapides

L'implémentation de référence donnée dans la description du problème est intéressante. Il utilise un générateur illimité, directement extrait du document Unbounded Spigot Algorithms for the Digits of Pi . Selon l'auteur, les implémentations fournies sont "délibérément obscures", j'ai donc décidé de faire de nouvelles implémentations des trois algorithmes répertoriés par l'auteur, sans obstruction délibérée. J'ai également ajouté un quatrième, basé sur 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)

Remarques

Ci-dessus se trouvent 6 implémentations: les deux implémentations de référence fournies par l'auteur (notées _ref), et quatre qui calculent les termes par lots, générant plusieurs chiffres à la fois ( _md). Toutes les implémentations ont été confirmées à 100 000 chiffres. Lors du choix des tailles de lot, j'ai choisi des valeurs qui perdent lentement en précision avec le temps. Par exemple, g1_mdgénère 10 chiffres par lot, avec 33 itérations. Cependant, cela ne produira que ~ 9,93 chiffres corrects. Lorsque la précision est épuisée, la condition de vérification échoue, ce qui déclenche l'exécution d'un lot supplémentaire. Cela semble être plus performant que la précision supplémentaire lentement gagnée, inutile au fil du temps.

• g1 (Leibniz / Euler)
  Une variable supplémentaire jest conservée, représentant 2*i+1. L'auteur fait de même dans l'implémentation de référence. Le calcul nséparé est beaucoup plus simple (et moins obscur), car il utilise les valeurs actuelles de q, ret t, plutôt que la suivante.
• g2 (Lambert)
  Le chèque n == q/sest certes assez laxiste. Cela devrait lire n == (q*(k+2*j+4)+r)/(s*(k+2*j+4)+t), où jest 2*i-1et kest i*i. Aux itérations supérieures, les termes ret tdeviennent de moins en moins significatifs. En l'état, c'est bon pour les 100 000 premiers chiffres, donc c'est probablement bon pour tous. L'auteur ne fournit aucune implémentation de référence.
• g3 (Gosper)
  L'auteur suppose qu'il est inutile de vérifier que ncela ne changera pas dans les itérations suivantes, et qu'il ne sert qu'à ralentir l'algorithme. Bien que cela soit probablement vrai, le générateur conserve environ 13% de chiffres corrects de plus qu'il n'en a actuellement généré, ce qui semble quelque peu inutile. J'ai ajouté la vérification et attendez que 50 chiffres soient corrects, en les générant tous en même temps, avec un gain notable de performances.
• g4 (Ramanujan 39)
  Calculé comme
  
  Malheureusement, sne met pas à zéro, en raison de la composition initiale (3528 ÷), mais il est toujours beaucoup plus rapide que g3. La convergence est d'environ 5,89 chiffres par trimestre, 3511 chiffres sont générés à la fois. Si c'est un peu trop, générer 271 chiffres pour 46 itérations est également un choix décent.

Timings

Pris sur mon système, à des fins de comparaison uniquement. Les heures sont répertoriées en secondes. Si un chronométrage a duré plus de 10 minutes, je n'ai effectué aucun autre test.

            |  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 

Il est intéressant de noter qu'il g2finit par dépasser g3, malgré un taux de convergence plus lent. Je soupçonne que c'est parce que les opérandes se développent à un rythme beaucoup plus lent, gagnant à long terme. L'implmentation la plus rapide g4_mdest environ 235x plus rapide que l' g3_refimplmentation sur 500 000 chiffres. Cela dit, il y a encore des frais généraux importants pour diffuser des chiffres de cette manière. Le calcul direct de tous les chiffres à l'aide de Ramanujan 39 ( source python ) est environ 10 fois plus rapide.

Pourquoi pas Chudnovsky?

L'algorithme Chudnovsky nécessite une racine carrée de haute précision, dans laquelle je ne suis honnêtement pas sûr de savoir comment travailler - en supposant que ce soit le cas. Le Ramanujan 39 est quelque peu spécial à cet égard. Cependant, la méthode semble être propice à des formules de type Machin, telles que celles utilisées par y-cruncher, ce qui pourrait être une avenue à explorer.

Haskell, 231 octets

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) 

Celui-ci utilise les algorithmes Spigot illimités pour les chiffres de Pi de Jeremy Gibbons, 2004. Le résultat est p. Techniquement, il devrait prendre en charge des séquences de sortie infinies, mais cela peut prendre un certain temps (et est limité par votre mémoire).

Python 2, 298 octets

Notez que le code pour générer pi est tiré de l'implémentation de l'OP.

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

Ma première tentative de golf en Python. Sort la séquence pour toujours.

Python 3.5, 278 263 octets:

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

Cela prend en nentrée les premiers nchiffres de π, puis sort les membres de la séquence dans ces premiers nchiffres. Maintenant, cela utilise le module décimal intégré de Python pour aller au-delà des limitations en virgule flottante de Python, puis définit la précision, ou epsilon, pour autant les entrées utilisateur. Ensuite, pour calculer π, cela passe par 50 itérations en utilisant l' algorithme efficace de Gausse-Legendre , puisque l'algorithme double apparemment le nombre de chiffres corrects à chaque fois, et donc, en 50 itérations, nous pouvons obtenir 2^50ou 1,125,899,906,842,624corriger les chiffres. Enfin, une fois les calculs effectués, il utilise une expression régulière avec un format de chaîne dans une whileboucle pour rechercher et imprimerre faire correspondre les objets (que j'espère bien) pour tous les chiffres continus et récurrents 1 chiffre de plus que lors de l'itération précédente dans la boucle.

J'ai pu utiliser cet algorithme pour calculer avec succès et précision πjusqu'à 10,000,000(dix millions) de chiffres, ce qui a pris environ 4 heures et 12 minutes. Voici le résultat final:

<_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'> 

Donc, je peux dire avec confiance que le 8e numéro de la séquence ne se produit même pas dans les 10 premiers millions de chiffres! πest un nombre aléatoire ...