Corridas de dígitos en Pi

13

Su objetivo es generar la secuencia estrictamente creciente de dígitos consecutivos e idénticos de pi (π). Cada término en la secuencia debe ser un dígito más largo que el anterior. Entonces 3(0º dígito de pi) es la primera vez que ocurre una serie de dígitos (longitud 1). El siguiente en ocurrir es 33(dígitos 24 y 25 de pi). Por supuesto, esta secuencia requiere que los dígitos de pi estén en la base 10 .

Los conocidos hasta ahora , y los primeros seis, todos ocurren dentro de los primeros 800 dígitos:

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

Tenga en cuenta que los nueve consecutivos ocurren todos juntos, en la misma ejecución, por lo que si la próxima ejecución más grande que encontró son 1000 0s consecutivos , esto llenaría múltiples términos de la secuencia.

No he encontrado más términos con mi programa. Sé que no hay más términos dentro de los primeros 50000 dígitos o más. Mi programa estaba tardando demasiado con 500000 dígitos, así que me di por vencido.

Implementación de referencia

Puedes:

  • Salida de la secuencia para siempre
  • Toma un número entero ny encuentra los primeros nnúmeros en la secuencia
  • Tome un número entero ny encuentre los números en la secuencia contenida en los primeros ndígitos de pi.

Asegúrese de especificar cuál hace su código. El número npuede ser cero o uno indexado.

Inspirado por esta pregunta de mathoverflow .

mbomb007
fuente
1
Relacionado : esa serie de 9s causó dolores de cabeza por muchas respuestas: P
Mego
¿Se le permite iniciar la salida con la secuencia vacía?
LegionMammal978
2
Además, el siguiente término de la secuencia parece ser 3333333 en los dígitos 10 ^ -710100 a 10 ^ -710106. El valor para n = 8 no aparece en los primeros 5 000 000 dígitos.
LegionMammal978
44
Dos términos más: 44444444 en los dígitos 10 ^ -22931745 a 10 ^ -22931752 y 777777777 en los dígitos 10 ^ -24658601 a 10 ^ -24658609. El valor para n = 10 no aparece en los primeros 100 000 000 dígitos.
LegionMammal978
1
Un término más: 6666666666 en 10 ^ -386980412. El undécimo término no aparece en los primeros 2 000 000 000 dígitos.
primo

Respuestas:

5

Mathematica, 85 bytes

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

Función anónima. Toma n como entrada y devuelve los elementos de la secuencia en los primeros n dígitos de π. La salida es en forma de {0, 3, 33, 111, ...}.

LegionMammal978
fuente
4

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

El número máximo de dígitos para verificar se toma de stdin. 10,000 dígitos terminan en aproximadamente 2 segundos con PyPy 5.3.

Uso de muestra

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

Algo útil

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

He cambiado de Chudnovsky a Ramanujan 39 por esto. Chudnovsky se quedó sin memoria en mi sistema poco después de 100 millones de dígitos, pero Ramanujan llegó a 400 millones, en solo unos 38 minutos. Creo que este es otro caso en el que la tasa de crecimiento de términos más lenta gana al final, al menos en un sistema con recursos limitados.

Uso de muestra

$ 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

Generadores ilimitados más rápidos

La implementación de referencia dada en la descripción del problema es interesante. Utiliza un generador ilimitado, tomado directamente del papel Algoritmos de espiga no limitada para los dígitos de Pi . Según el autor, las implementaciones proporcionadas son "deliberadamente oscuras", por lo que decidí hacer nuevas implementaciones de los tres algoritmos enumerados por el autor, sin ofuscación deliberada. También agregué un cuarto, basado en 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)

Notas

Arriba hay 6 implementaciones: las dos implementaciones de referencia proporcionadas por el autor (denotado _ref), y cuatro que calculan términos en lotes, generando múltiples dígitos a la vez ( _md). Todas las implementaciones han sido confirmadas a 100,000 dígitos. Al elegir tamaños de lote, elegí valores que lentamente pierden precisión con el tiempo. Por ejemplo, g1_mdgenera 10 dígitos por lote, con 33 iteraciones. Sin embargo, esto solo producirá ~ 9.93 dígitos correctos. Cuando se agote la precisión, la condición de verificación fallará, lo que desencadenará la ejecución de un lote adicional. Esto parece ser más eficaz que la precisión lenta y adicionalmente innecesaria con el tiempo.

  • g1 (Leibniz / Euler)
    Se jmantiene una variable adicional que representa 2*i+1. El autor hace lo mismo en la implementación de referencia. Calcular por nseparado es mucho más simple (y menos oscuro), porque utiliza los valores actuales de q, ry t, en lugar de los siguientes.
  • g2 (Lambert)
    El cheque n == q/ses ciertamente bastante laxo. Eso debería leer n == (q*(k+2*j+4)+r)/(s*(k+2*j+4)+t), dónde jestá 2*i-1y kestá i*i. En iteraciones más altas, los términos ry se tvuelven cada vez menos significativos. Como es, es bueno para los primeros 100,000 dígitos, por lo que probablemente sea bueno para todos. El autor no proporciona implementación de referencia.
  • g3 (Gosper)
    El autor conjetura que no es necesario verificar que nno cambiará en las iteraciones posteriores, y que solo sirve para ralentizar el algoritmo. Aunque probablemente sea cierto, el generador está reteniendo ~ 13% más dígitos correctos de los que ha generado actualmente, lo que parece un poco inútil. He agregado el cheque nuevamente y espero hasta que 50 dígitos sean correctos, generándolos todos a la vez, con una ganancia notable en el rendimiento.
  • g4 (Ramanujan 39)
    Calculado como

    Desafortunadamente, sno se pone a cero, debido a la composición inicial (3528 ÷), pero sigue siendo significativamente más rápido que g3. La convergencia es de ~ 5.89 dígitos por término, se generan 3511 dígitos a la vez. Si eso es demasiado, generar 271 dígitos por 46 iteraciones también es una opción decente.

Tiempos

Tomado en mi sistema, solo para fines de comparación. Los tiempos se enumeran en segundos. Si un tiempo tardó más de 10 minutos, no ejecuté más pruebas.

            |  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 interesante que g2finalmente supere g3, a pesar de una tasa de convergencia más lenta. Sospecho que esto se debe a que los operandos crecen a un ritmo significativamente más lento, ganando a la larga. La implicación más rápida g4_mdes aproximadamente 235 veces más rápida que la g3_refimplicación en 500,000 dígitos. Dicho esto, todavía hay una sobrecarga significativa para la transmisión de dígitos de esta manera. Calcular todos los dígitos directamente usando Ramanujan 39 ( fuente de Python ) es aproximadamente 10 veces más rápido.

¿Por qué no Chudnovsky?

El algoritmo de Chudnovsky requiere una raíz cuadrada de precisión completa, que honestamente no estoy seguro de cómo trabajar, suponiendo que pueda serlo. Ramanujan 39 es algo especial en este sentido. Sin embargo, parece que el método podría conducir a fórmulas similares a las de Machin, como las utilizadas por y-cruncher, por lo que podría ser una vía que vale la pena explorar.

primo
fuente
TIL Ideone es compatible con Pypy. Entonces, ¿el segundo programa está diseñado para la velocidad?
mbomb007
@ mbomb007 "¿Entonces el segundo programa está diseñado para la velocidad?" Es. Creo que el desafío habría sido tan interesante como un código más rápido .
primo
Mismo. Yo consideré los dos. No sé cómo se siente la gente acerca de volver a publicar bajo una etiqueta diferente. Podría ser más útil si se agrega al OEIS (que no contiene esta secuencia)
mbomb007
3

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) 

Utiliza los algoritmos de espiga ilimitada para los dígitos de Pi de Jeremy Gibbons, 2004. El resultado es p. Técnicamente, debería admitir secuencias de salida infinitas, pero eso puede llevar un tiempo (y está limitado por su memoria).

Zeta
fuente
3

Python 2, 298 bytes

Tenga en cuenta que el código para generar pi se toma de la implementación del 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

Mi primer intento de jugar golf en Python. Emite la secuencia para siempre.

acrolito
fuente
¿Podría explicar cómo calcula πaquí? Usted, por supuesto, calcula pi, ¿verdad?
R. Kap
No puedo probar en este momento, pero ¿no estás calculando πpara siempre allí?
Yytsi
@TuukkaX no aparece, ya que tiene una yieldque lo detiene, pero no soy muy bueno en python
Downgoat
Downgoat es correcto: utiliza una función de generador .
Mego
1
Escribí todo el código, no miré su implementación, excepto la pparte
acrolith
3

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

Esto toma ncomo entrada para los primeros ndígitos de πy luego genera los miembros de la secuencia en esos primeros ndígitos. Ahora, esto usa el módulo decimal incorporado de Python para ir más allá de las limitaciones de punto flotante de Python, y luego establece la precisión, o épsilon, a la cantidad de entradas del usuario. Luego, para calcular π, esto pasa por 50 iteraciones usando el eficiente algoritmo Gausse-Legendre , ya que el algoritmo aparentemente duplica el número de dígitos correctos cada vez, y por lo tanto, en 50 iteraciones, podemos obtener 2^50o 1,125,899,906,842,624corregir dígitos. Finalmente, después de realizar los cálculos, utiliza una expresión regular con formato de cadena en un whilebucle para buscar e imprimirre emparejar objetos (que espero que esté bien) para todos los dígitos continuos y recurrentes 1 dígito más que en la iteración anterior a través del bucle.

Pude usar este algoritmo para calcular con éxito y precisión πhasta 10,000,000(diez millones) dígitos, lo que tardó aproximadamente 4 horas y 12 minutos en completarse. El siguiente fue el resultado 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'> 

¡Entonces, puedo decir con confianza que el octavo número en la secuencia ni siquiera aparece dentro de los primeros 10 millones de dígitos! πes un número aleatorio ...

R. Kap
fuente