Ваша цель - вывести строго возрастающую последовательность последовательных одинаковых цифр числа pi (π). Каждый член в последовательности должен быть на одну цифру длиннее предыдущего. Таким образом 3(0-ая цифра числа пи) - это первый раз, когда происходит серия цифр (длина 1). Следующее происходит 33(цифры 24 и 25 от пи). Конечно, эта последовательность требует, чтобы цифры числа pi находились в базе 10 .

Те, которые известны до сих пор , и первые шесть встречаются в первых 800 цифрах:

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

Обратите внимание, что все последовательные девятки встречаются вместе в одном и том же прогоне, поэтому, если следующий крупный прогон, который вы обнаружили, будет 1000 последовательных 0с, это будет заполнять несколько членов последовательности.

Я не нашел больше условий с моей программой. Я знаю, что в первых 50000 цифрах и более больше нет терминов. Моя программа заняла слишком много времени с 500000 цифр, поэтому я сдался.

Реализация эталона

Ты можешь:

• Выведите последовательность навсегда
• Возьмите целое число nи найдите первые nчисла в последовательности
• Возьмите целое число nи найдите числа в последовательности, содержащейся в первых nцифрах числа пи.

Обязательно укажите, какой код делает ваш. Число nможет быть нулевым или индексированным.

Вдохновлен этим вопросом Mathoverflow .

Mathematica, 85 байт

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

Анонимная функция. Принимает n в качестве входных данных и возвращает элементы последовательности в первых n цифрах π. Вывод в виде {0, 3, 33, 111, ...}.

Python 2, 110 байт

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

Максимальное количество проверяемых цифр берется из стандартного ввода. 10000 цифр заканчиваются примерно через 2 с PyPy 5.3.

Образец использования

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

Что-то полезное

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

Для этого я перешел с Чудновского на Рамануджана 39. У Чудновского не хватило памяти в моей системе вскоре после 100 миллионов цифр, но Рамануджан довел ее до 400 миллионов всего за 38 минут. Я думаю, что это еще один случай, когда более медленный темп роста выигрывает в конце, по крайней мере, в системе с ограниченными ресурсами.

Образец использования

$ 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

Более быстрые неограниченные генераторы

Ссылочная реализация, приведенная в описании проблемы, интересна. Он использует неограниченный генератор, взятый непосредственно из статьи « Неограниченные алгоритмы Spigot для цифр числа Пи» . По словам автора, представленные реализации являются «намеренно неясными», поэтому я решил сделать свежие реализации всех трех алгоритмов, перечисленных автором, без преднамеренного запутывания. Я также добавил четвертый, основанный на Рамануджане # 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)

Примечания

Выше приведены 6 реализаций: две ссылочные реализации, предоставленные автором (обозначены _ref), и четыре, которые вычисляют термины в пакетах, генерируя несколько цифр одновременно ( _md). Все реализации были подтверждены до 100 000 цифр. При выборе размеров партии я выбирал значения, которые со временем постепенно теряют точность. Например, g1_mdгенерирует 10 цифр на пакет с 33 итерациями. Однако это даст только ~ 9,93 правильных цифр. Когда прекратится точность, условие проверки не будет выполнено, что приведет к запуску дополнительной партии. Это кажется более производительным, чем постепенно увеличивающаяся, ненужная точность с течением времени.

• g1 (Лейбниц / Эйлер)
  Сохраняется дополнительная переменная j, представляющая 2*i+1. Автор делает то же самое в ссылочной реализации. Расчет nотдельно гораздо проще (и менее неясный), потому что он использует текущие значения q, rи t, а не на следующем.
• g2 (Ламберт)
  Проверка, n == q/sпо общему признанию, довольно слабая. Это следует читать n == (q*(k+2*j+4)+r)/(s*(k+2*j+4)+t), где jесть 2*i-1и kесть i*i. При более высоких итераций rи tусловия становятся все менее значимыми. Как, это хорошо для первых 100 000 цифр, так что это, вероятно, хорошо для всех. Автор не предоставляет справочную реализацию.
• g3 (Госпер)
  Автор полагает, что нет необходимости проверять, что nне изменится на последующих итерациях, и что это только замедляет алгоритм. Хотя, вероятно, это правда, генератор держит на ~ 13% больше правильных цифр, чем генерировал в настоящее время, что кажется несколько расточительным. Я добавил чек обратно и жду, пока 50 цифр будут правильными, генерируя их все сразу, с заметным приростом производительности.
• g4 (Рамануджан 39)
  Рассчитано как
  
  К сожалению, sне обнуляется из-за начального (3528 ÷) состава, но все равно значительно быстрее, чем g3. Сходимость составляет ~ 5,89 цифр за семестр, за один раз генерируется 3511 цифр. Если это немного, генерирование 271 цифры за 46 итераций также является достойным выбором.

Задержки

Взятые на моей системе, только для сравнения. Время указано в секундах. Если время заняло больше 10 минут, я больше не проводил никаких тестов.

            |  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 

Интересно, что в g2конечном итоге обгоняет g3, несмотря на более медленную скорость сближения. Я подозреваю, что это потому, что операнды растут значительно медленнее, выигрывая в долгосрочной перспективе. Самая быстрая g4_mdимплентация примерно в 235 раз быстрее, чем имплементация g3_refна 500 000 цифр. Тем не менее, таким образом все еще существуют значительные издержки для потоковых цифр. Вычисление всех цифр напрямую с использованием Ramanujan 39 ( источник Python ) примерно в 10 раз быстрее.

Почему не Чудновский?

Алгоритм Чудновского требует квадратного корня с полной точностью, в котором я, честно говоря, не уверен, как работать - предполагая, что это вообще может быть. Рамануджан 39 несколько особенный в этом отношении. Тем не менее, кажется, что этот метод может быть полезен для машиноподобных формул, таких как те, что используются y-cruncher, так что это может быть целью, которую стоит изучить.

Haskell, 231 байт

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) 

Это использует Алгоритмы неограниченного Spigot для цифр числа Пи от Джереми Гиббонс, 2004. Результат p. Технически, он должен поддерживать бесконечные выходные последовательности, но это может занять некоторое время (и ограничено вашей памятью).

Python 2, 298 байт

Обратите внимание, что код для генерации pi взят из реализации 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

Моя первая попытка игры в гольф на Python. Выводит последовательность навсегда.

Python 3.5, 278 263 байта:

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

Это принимает в n качестве входных данных первые nцифры πи затем выводит члены последовательности в этих первых nцифрах. Теперь он использует встроенный в Python десятичный модуль, чтобы выйти за пределы ограничений Python с плавающей запятой, а затем устанавливает точность, или эпсилон, сколь угодно большого количества пользовательского ввода. Затем, чтобы вычислить π, это проходит 50 итераций с использованием эффективного алгоритма Гаусса-Лежандра , поскольку алгоритм, по-видимому, удваивает количество правильных цифр каждый раз, и, следовательно, за 50 итераций мы можем получить 2^50или 1,125,899,906,842,624исправить цифры. Наконец, после выполнения вычислений whileдля поиска и печати используется регулярное выражение с форматированием строки в цикле.re сопоставлять объекты (что, я надеюсь, хорошо) для всех непрерывных, повторяющихся цифр на 1 цифру длиннее, чем в предыдущей итерации цикла.

Я смог использовать этот алгоритм для успешного и точного вычисления πдо 10,000,000(десяти миллионов) цифр, что заняло около 4 часов и 12 минут. Следующим был окончательный результат:

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

Итак, я могу с уверенностью сказать, что 8-е число в последовательности даже не встречается в пределах первых 10 миллионов цифр! πэто одно случайное число ...