Tujuan Anda adalah untuk menampilkan urutan pi (π) yang terus meningkat secara konsisten dan berurutan. Setiap istilah dalam urutan harus satu digit lebih panjang dari sebelumnya. Jadi 3(digit ke-0 pi) adalah pertama kalinya serangkaian digit terjadi (panjang 1). Selanjutnya yang terjadi adalah 33(digit 24 dan 25 pi). Tentu saja, urutan ini membutuhkan digit pi berada di basis 10 .

Yang diketahui sejauh ini , dan enam pertama semuanya terjadi dalam 800 digit pertama:

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

Perhatikan bahwa sembilan berturut-turut semua terjadi bersamaan, dalam proses yang sama, jadi jika proses lebih besar berikutnya yang Anda temukan terjadi 1000 kali berturut-turut 0, ini akan mengisi beberapa istilah dalam urutan.

Saya belum menemukan ketentuan dengan program saya. Saya tahu tidak ada istilah lagi dalam 50000 digit pertama atau lebih. Program saya terlalu lama dengan 500.000 digit, jadi saya menyerah.

Implementasi Referensi

Kamu boleh:

• Keluarkan urutan selamanya
• Ambil bilangan bulat ndan temukan nangka pertama dalam urutan
• Ambil bilangan bulat ndan temukan angka dalam urutan yang terdapat pada ndigit pertama pi.

Pastikan untuk menentukan kode mana yang Anda lakukan. Jumlahnya nmungkin nol atau satu diindeks.

Terinspirasi oleh pertanyaan aliran matematika ini .

Mathematica, 85 byte

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

Fungsi anonim. Mengambil n sebagai input, dan mengembalikan elemen urutan dalam n digit pertama n . Output dalam bentuk {0, 3, 33, 111, ...}.

Python 2, 110 byte

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

Jumlah digit maksimum untuk diperiksa diambil dari stdin. 10.000 digit selesai dalam 2s dengan PyPy 5.3.

Contoh Penggunaan

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

Sesuatu yang Berguna

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

Saya telah beralih dari Chudnovsky ke Ramanujan 39 untuk ini. Chudnovsky kehabisan memori pada sistem saya tak lama setelah 100 juta digit, tetapi Ramanujan mencapai 400 juta, hanya dalam waktu 38 menit. Saya pikir ini adalah kasus lain adalah tingkat pertumbuhan yang lebih lambat menang pada akhirnya, setidaknya pada sistem dengan sumber daya terbatas.

Contoh Penggunaan

$ 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

Generator Tanpa Batas Lebih Cepat

Implementasi referensi yang diberikan dalam deskripsi masalah menarik. Ini menggunakan generator tanpa batas, diambil langsung dari kertas Algoritma Keran Tanpa Batas untuk Digit Pi . Menurut penulis, implementasi yang disediakan adalah "sengaja tidak jelas", jadi saya memutuskan untuk membuat implementasi baru dari ketiga algoritma yang terdaftar oleh penulis, tanpa kebingungan yang disengaja. Saya juga menambahkan yang keempat, berdasarkan 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)

Catatan

Di atas adalah 6 implementasi: dua implementasi referensi yang disediakan oleh penulis (dilambangkan _ref), dan empat yang menghitung istilah dalam batch, menghasilkan beberapa digit sekaligus (_md ). Semua implementasi telah dikonfirmasi hingga 100.000 digit. Saat memilih ukuran batch, saya memilih nilai yang secara perlahan kehilangan presisi seiring waktu. Misalnya, g1_mdmenghasilkan 10 digit per batch, dengan 33 iterasi. Namun, ini hanya akan menghasilkan ~ 9,93 digit yang benar. Ketika presisi habis, kondisi pemeriksaan akan gagal, memicu bets tambahan untuk dijalankan. Ini tampaknya lebih berkinerja daripada mendapatkan secara ekstra, presisi yang tidak dibutuhkan seiring waktu.

• g1 (Leibniz / Euler)
  Suatu variabel tambahan jdisimpan, mewakili 2*i+1. Penulis melakukan hal yang sama dalam implementasi referensi. Menghitung nsecara terpisah jauh lebih sederhana (dan kurang jelas), karena menggunakan nilai saat ini q,r dan t, daripada yang berikutnya.
• g2 (Lambert)
  Cek n == q/sini diakui cukup longgar. Itu harus membaca n == (q*(k+2*j+4)+r)/(s*(k+2*j+4)+t), di mana jadalah 2*i-1dan kadalah i*i. Pada iterasi yang lebih tinggi, rdan tistilah menjadi semakin kurang signifikan. Seperti, ini bagus untuk 100.000 digit pertama, jadi mungkin bagus untuk semua. Penulis tidak memberikan implementasi referensi.
• g3 (Gosper)
  Penulis menduga bahwa tidak perlu memeriksa yang ntidak akan berubah dalam iterasi berikutnya, dan bahwa itu hanya berfungsi untuk memperlambat algoritma. Meskipun mungkin benar, generator memegang ~ 13% angka yang lebih benar daripada yang dihasilkan saat ini, yang tampaknya agak boros. Saya telah menambahkan check-in kembali, dan menunggu hingga 50 digit benar, menghasilkan semuanya sekaligus, dengan perolehan kinerja yang nyata.
• g4 (Ramanujan 39)
  Dihitung sebagai
  
  Sayangnya, stidak nol, karena komposisi awal (3528 ÷), tetapi masih secara signifikan lebih cepat daripada g3. Konvergensi adalah ~ 5,89 digit per term, 3511 digit dihasilkan pada suatu waktu. Jika itu sedikit banyak, menghasilkan 271 digit per 46 iterasi juga merupakan pilihan yang layak.

Pengaturan waktu

Diambil di sistem saya, hanya untuk tujuan perbandingan. Waktu tercantum dalam hitungan detik. Jika waktu yang dibutuhkan lebih dari 10 menit, saya tidak menjalankan tes lebih lanjut.

            |  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 

Sangat menarik yang g2akhirnya menyusul g3, meskipun tingkat konvergensi lebih lambat. Saya menduga ini karena operan tumbuh pada tingkat yang secara signifikan lebih lambat, menang dalam jangka panjang. g4_mdImplmentasi tercepat adalah sekitar 235x lebih cepat daripada g3_refimplmentasi pada 500.000 digit. Yang mengatakan, masih ada overhead yang signifikan untuk streaming digit dengan cara ini. Menghitung semua digit secara langsung menggunakan Ramanujan 39 ( sumber python ) kira-kira 10x lebih cepat.

Kenapa tidak Chudnovsky?

Algoritma Chudnovsky membutuhkan akar kuadrat presisi penuh, yang sejujurnya saya tidak yakin bagaimana cara kerjanya - dengan asumsi bisa saja sama sekali. Ramanujan 39 agak istimewa dalam hal ini. Namun, metode ini sepertinya kondusif untuk formula mirip Machin, seperti yang digunakan oleh y-cruncher, sehingga mungkin jalan yang layak dijelajahi.

Haskell, 231 byte

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) 

Ini menggunakan Algoritma Spigot Tidak Terbatas untuk Digit Pi oleh Jeremy Gibbons, 2004. Hasilnya adalah p. Secara teknis, ini harus mendukung urutan output yang tak terbatas, tetapi itu mungkin memakan waktu cukup lama (dan dibatasi oleh memori Anda).

Python 2, 298 byte

Catatan, kode untuk menghasilkan pi diambil dari implementasi 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

Upaya pertama saya bermain golf di Python. Output urutan selamanya.

Python 3.5, 278 263 byte:

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

Ini menerima nsebagai input untuk ndigit pertama πdan kemudian menampilkan anggota urutan dalam ndigit pertama . Sekarang, ini menggunakan modul desimal built-in Python untuk melampaui batasan floating-point Python, dan kemudian mengatur presisi, atau epsilon, sejauh apa pun input pengguna. Kemudian, untuk menghitung π, ini melewati 50 iterasi menggunakan algoritma Gausse-Legendre yang efisien , karena algoritma tampaknya menggandakan jumlah digit yang benar setiap kali, dan oleh karena itu, dalam 50 iterasi, kita bisa mendapatkan 2^50atau1,125,899,906,842,624 mengoreksi digit. Akhirnya, setelah perhitungan selesai, ia menggunakan ekspresi reguler dengan pemformatan string dalam satu whilelingkaran untuk menemukan dan mencetakre mencocokkan objek (yang saya harap tidak apa-apa) untuk semua digit berulang 1 digit lebih lama dari pada iterasi sebelumnya melalui loop.

Saya dapat menggunakan algoritma ini untuk berhasil dan akurat menghitung πhingga 10,000,000(sepuluh juta) digit, yang membutuhkan waktu sekitar 4 jam dan 12 menit untuk menyelesaikannya. Berikut ini adalah hasil akhir:

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

Jadi, saya dapat dengan yakin mengatakan bahwa nomor 8 dalam urutan itu bahkan tidak muncul dalam 10 juta digit pertama! πadalah satu nomor acak ...