Temukan bilangan prima di Pi

30

Bilangan prima ada di mana-mana ...

mereka bersembunyi di dalam Pi

3.141592653 58979 3238 462643 3832 795028841 971693993751

Mari kita dapatkan bilangan prima itu!

Tantangan

Diberikan sebagai input bilangan bulat n>0, cari tahu berapa bilangan prima yang disembunyikan di dalam ndigit pertamaPi

Contohnya

Karena n=3kita harus mencari bilangan prima di [3,1,4]. Ada 2 Primes (3,31), sehingga kode Anda harus keluaran 2
Untuk n=10, pertama 10 digit yang [3,1,4,1,5,9,2,6,5,3]dan kode Anda harus output 12karena [2, 3, 5, 31, 41, 53, 59, 653, 4159, 14159, 314159, 1592653]disembunyikan (dan ditemukan!)

Uji Kasus

input -> output

1->1  
3->2  
13->14  
22->28  
42->60  
50->93

150->197  
250->363  
500->895

Aturan

Kode Anda harus dapat menemukan semua bilangan prima setidaknya untukn=50
Ya, Anda dapat meng-hardcode 50 digit pertama Pijika Anda suka
Entri hardcoding jawaban tidak valid

Ini adalah Jawaban terpendek dalam byte menang!


sumber
6
"Anda dapat meng-hardcode 50 digit pertama Pi jika Anda mau" . Masalah pertama terpecahkan! Sekarang untuk tes primitif golf hingga bilangan bulat 50 digit ... O_o (Ini adalah tantangan yang bagus, tetapi matematika bawaan built-in atau perpustakaan mungkin diperlukan.)
Arnauld
3
@totallyhuman Urutan itu bahkan belum di OEIS! Saatnya klaim Anda terkenal?
Sanchises
3
IMO memungkinkan hardcoding dari 50 nilai pertama merusak tantangan ini. Tantangan ini pada dasarnya adalah dua bagian, 1) mencoba mengompresi 50 nilai pertama, atau 2) benar-benar melakukan tantangan.
JAD
2
Biasanya dalam tantangan semacam ini, di mana perhitungan menjadi lebih sulit / lebih lambat / intensif memori, itu sudah cukup bagi program untuk bekerja secara teoritis, daripada menetapkan cutoff sewenang-wenang dan memungkinkan hardcoding.
JAD
3
@BillSteihn Memperbarui aturan setelah ada beberapa jawaban yang bertentangan dengan semangat situs web ini. Sudahkah Anda memposting pertanyaan ini di Sandbox ? Anda akan mendapat umpan balik sangat awal sehingga jawaban dengan kode sandi akan masuk.
Olivier Grégoire

Jawaban:

20

05AB1E ,  10  8 byte

-2 byte terima kasih kepada Adnan ( pvectoris)

<žsþŒÙpO

Cobalah online! (akan bekerja hingga n = 98413 tetapi akan sangat lambat bahkan untuk n = 50 karena kebutuhan untuk menguji jumlah besar untuk primality - TIO time out pada 60 detik untuk n = 50.)

Bagaimana?

<žsþŒÙpO - implicitly push input, n
<        - decrement = n-1
 žs      - pi to that many decimal places (i.e. to n digits)
   þ     - only the digits (get rid of the decimal point)
    Œ    - all sublists
     Ù   - unique values
      p  - is prime? (vectorises) 1 if so, 0 otherwise
       O - sum
         - implicitly print the top of the stack
Jonathan Allan
sumber
<žsþŒÙpOseharusnya bekerja selama 8 byte
Adnan
Ah ya pvektorisasi terima kasih!
Jonathan Allan
2
Iya nih! Akhirnya jawaban kode golf sangat singkat yang saya benar-benar mengerti! : D
Fabian Röling
11

Mathematica, 76 byte

Tr[1^Union@Select[FromDigits/@Subsequences@#&@@RealDigits[Pi,10,#],PrimeQ]]&
J42161217
sumber
Oh, tidak adil, saya tidak terbiasa dengan golf Mathematica. : P (+1)
totallyhuman
@totallyhuman Kami memposting ini pada saat yang sama. ini sangat aneh!
J42161217
Saya memasukkan jawaban saya menggunakan beberapa trik sintaksis tetapi saya tetap menggunakan fungsi yang saya gunakan sebelumnya. Saya harap kamu tidak keberatan.
totallyhuman
Tr[1^...]Itu cara yang cerdas untuk menemukan panjang daftar, bagus!
numbermaniac
6

Mathematica, 104 97 90 byte

Length@DeleteDuplicates@Select[FromDigits/@Subsequences@First@RealDigits[Pi,10,#],PrimeQ]&

Hahahaha, saya berhasil membuat ini berhasil. Saya tidak tahu cara menggunakan Mathematica. XD

Memasukkan:

[50]
benar-benar manusiawi
sumber
1
Anda memposting beberapa detik di depan saya. dan jawaban kami sangat mirip! +1
J42161217
Apakah Anda yakin tentang angka yang baru saja Anda posting (periksa ulang pembulatan angka) Saya melihat hasil yang sedikit berbeda menggunakan Python dan sympy
Jonathan Allan
@ JonathanAllan 50 96OP mengatakan 50 digit berisi 93 bilangan prima, jadi akurasi Sympy mungkin tidak aktif ..?
totallyhuman
@ JonathanAllan Apakah Sympy menggunakan uji primitif probabilistik atau deterministik? (Pertanyaan yang sama untuk PrimeQ Mathematica.)
Arnauld
@Arnauld poin bagus, tidak yakin.
Jonathan Allan
3

Python 3 , 274 237 207 194 189 byte

-37 byte, terima kasih kepada Wheat Wizard! -14 byte terima kasih kepada Mr.Xcoder.

Hardcode 50 digit pertama pi tetapi secara manual menghitung semua yang lain.

x=int(input());l="31415926535897932384626433832795028841971693993751"[:x]
print(sum(all(i%m for m in range(2,i))for i in{int(i)for w in range(x)for i in[l[j:j-~w]for j in range(x-w)]}-{1}))

Cobalah online!

benar-benar manusiawi
sumber
l=list("31415...)harus menghemat ~ 40 karakter. Dan perubahan itu memungkinkan Anda mengganti map(str,i)dengan adil i.
AShelly
195 byte dengan menghapus beberapa kode aneh.
Tn. Xcoder
194 byte dengan mendeklarasikanlen(l)
Tn. Xcoder
1

R, 156 123 byte

cat(cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1,0,6,0,3,2,0,0,0,0,0,0,4,3,3,6,0,4,8,2,5,3,6,0,5))[scan()])

Solusi super menarik. Bekerja pada yang tepat.

Disimpan 33 byte berkat @Giuseppe.

R (+ angka dan gmp), 198 byte

function(n,x=unique(gmp::as.bigz(unlist(sapply(1:n,function(x)substring(gsub("[.]","",numbers::dropletPi(50)),x,x:n))))))min(length(x),sum(sapply(sapply(x[x>0&!is.na(x)],gmp::factorize),length)==1))

Solusi yang tepat. Dibawa nsebagai input.

Menggunakan numbers::dropletPi(50)untuk menghasilkan 50 tempat desimal pertama dari pi. gsubmenghilangkan titik desimal. substringmembutuhkan setiap kemungkinan substring (kejutan kejutan) pi hingga n.

Daftar kembali diratakan dan diubah menjadi gmp's bigzFormat. Format ini diperlukan untuk menyimpan bilangan bulat dengan panjang 50. uniquemengambil nilai unik dari vektor itu. Hasil ini disimpan di x.

Lalu kami memeriksa keutamaan. Ini rumit, karena ada banyak kasus tepi dan gangguan:

  • Untuk tinggi n, ada 0di pi. Ini mengarah ke substring dengan nol di depannya. as.bigzmenghasilkan NAdengan itu, yang harus dihapus.

  • Pada catatan yang sama, substring "0"akan macet gmp::factorize, jadi harus dihapus juga.

  • Untuk n=1, x = 3. Yang dengan sendirinya ok, tapi bigzrepresentasi 3iterable, jadi sapplyakan bingung dan melaporkan 16 bilangan prima. Untuk tujuan ini kami mengambil minimum dari panjang vektor x, dan jumlah bilangan prima di dalamnya.

  • gmp::isprimetampaknya tidak bisa menangani angka-angka besar dengan andal. Jadi alih-alih kita menggunakan gmp::factorizedan mengecek panjang outputnya adalah 1.

Jadi secara keseluruhan, kami menghapus 0dan NAdari x. Kami memfaktisasi semua xdan memeriksa panjangnya. Kami menghitung jumlah kemunculan 1dan mengembalikan min(occurences, length(x)).

JAD
sumber
Anda disana! Sekarang mari kita lihat apakah seseorang di luar sana dapat mengalahkan ini dengan solusi yang lebih menarik. bisa jadi kamu!
gunakan cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1,0,6,0,3,2,0,0,0,0,0,0,4,3,3,6,0,4,8,2,5,3,6,0,5))bukan vektor Anda untuk 123 byte :)
Giuseppe
@Giuseppe Bagus. 'Kompresi' itu pasti akan mengalahkan solusi sah apa pun.
JAD
Saya pikir itu tidak mungkin di R tanpa hardcoding atau memperkenalkan paket lain karena R hanya memiliki 32-bit int, yang tentunya tidak akan mewakili integer 50 digit.
Giuseppe
1
Ya, saya mungkin memikirkan ini lagi. 82 byte hardcoded
Giuseppe
0

Jelly , 59 32 byte

-27 byte terima kasih kepada Erik the Outgolfer.

“!⁶⁷¬,6½ạEC.wʠ€Ẉ!+Ẉfṭ¡’Ṿḣ³ẆVQÆPS

Cobalah online!

Penjelasan

“...’Ṿḣ³ẆVQÆPS

“...’           compressed string that evaluates to first 50 digits of pi (314159...)
     Ṿ          uneval; stringify
      ḣ³        first n characters of the string where n is the first command-line argument
        Ẇ       all sublists
         V      convert all elements to integers
          Q     deduplicate
           ÆP   convert all prime elements to 1 and others to 0
             S  sum
benar-benar manusiawi
sumber
Mengapa Anda mengirim spam ini dengan jawaban?
Zacharý
Karena tidak ada orang lain yang menjawab, dan saya memukul topi perwakilan. : P
totallyhuman