Bilangan prima yang benar dan terpotong

11

Sebuah prime benar-truncatable adalah perdana di mana setiap prefix adalah perdana (dalam basis 10). Sebuah kiri-truncatable prima adalah persis sebaliknya, di mana setiap postfix adalah prima (bilangan prima yang dimulai dengan 0 tidak diperbolehkan). Kedua urutan ini terbatas (Hanya ada 83 truncatable kanan, sementara ada 4260 truncatable kiri).

Anda perlu menulis sebuah program yang menerima sejumlah tunggal sebagai input, dan menghasilkan n th prima kanan truncatable. Namun, ketika program dibaca diatur mundur , itu harus menghasilkan perdana terpotong kiri ke- n .

Untuk mengatur program mundur, kami membagi program menjadi kata-kata, lalu membalik urutan kata-kata. Sebuah kata dapat terdiri dari sejumlah karakter.

Misalnya, jika yang berikut adalah program Anda:

hello world
1234567890

Berikut ini semua akan dimungkinkan pengaturan mundur:

Membagi pada setiap karakter:

0987654321
dlrow olleh

Memisahkan di ruang putih:

1234567890
world hello

Membelah secara sewenang-wenang (pipa ditambahkan untuk kejelasan):

hel|lo w|orld
1|23456|7|8|90

908723456orld
1lo whel

Saat mengatur program Anda mundur, semua spasi putih harus dipertimbangkan dan dibalik, sama seperti karakter lainnya.

Masukan uji maju:

1:  2
2:  3
21: 379
60: 239933
83: 73939133

Input tes mundur:

1:    2
2:    3
39:   647
187:  29173
4260: 357686312646216567629137

Program harus dapat berjalan dalam jumlah waktu yang wajar (kurang dari satu menit)

Ini adalah , sehingga program dengan byte paling sedikit menang!

Nathan Merrill
sumber
tidak. Atom setelahnya lo wadalah orld\n1. Baris baru tidak mengakhiri atom
Nathan Merrill
Ah terima kasih. Mengerti sekarang Menghapus dua komentar saya sebelumnya untuk menghindari kebingungan
Luis Mendo

Jawaban:

6

Jelly , 26 23 byte

Meneruskan

Ѷp9¶7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Cobalah online!

Kata-kata

Ñ p 9 7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Ke belakang

7ÆR2ĿV€$ÆPÐf$ÐĿFị@¶9p¶Ñ

Cobalah online!

Kata-kata

7ÆR2ĿV€$ÆPÐf$ÐĿFị@ 9 p Ñ

Bagaimana itu bekerja

Semua program Jelly terdiri dari tautan (Jelly mengambil fungsi), yang dipisahkan oleh linefeeds atau pilcrows ( ). Yang terakhir adalah tautan utama ; itu disebut secara otomatis ketika program dijalankan.

Program forward berfungsi sebagai berikut.

Ñ                   Helper link. Unused.


p9                  Helper link. Take the Cartesian product with [1, ..., 9].


7ÆR2ĿV€$ÆPÐf$ÐĿFị@  Main link. Argument: n

7ÆR                 Yield all primes up to 7.
             ÐĿ     
            $ÐĿ     Combine the two quicklinks to the left into a monadic chain,
                    and call it repeatedly until the results are no longer unique.
                    Return the array of all intermediate results.
       $              Combine the two links to the left into a monadic chain.
   2Ŀ               Call the helper link on line 2.
     Ṿ€                 Eval each array in the product. This casts to string
                        before evaluating, thus concatenating both numbers.
        ÆPÐf        Filter by primality; keep only primes.
               F    Flatten the resulting array.
                ị@  Retrieve the element at index n.

Program mundur hampir persis sama; hanya ada dua perbedaan.

  • Tautan utama sekarang Ñ, yang hanya memanggil tautan di bawahnya (membungkus), yaitu, tautan utama program penerusan.

  • 9pbukannya p9mengembalikan produk Cartesian yang dibalik.

Dennis
sumber
4

Python 2, 143 139 byte

I=1
a={2}
def f(s):
 for d in'123456789':u=d[I:]+s+d*I;z=int(u);z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)
f('')
lambda n:sorted(a)[~-n]
I=0

Terdiri dari lima bagian:

  1. I=1
  2. Baris baru
  3. a={2}…[~-n]
  4. Baris baru
  5. I=0

Jadi pembalikan hanya membalik nilai I.

Penjelasan

Fungsi fmelakukan pencarian rekursif untuk bilangan prima terpotong kiri (LTPs) atau bilangan prima terpotong-kanan (RTP), tergantung pada nilai global I. Nilai-nilai ini ditambahkan ke set a. Kemudian, lambda n:sorted(a)[~-n]kembalikan yang nke-satu.

Mari kita mendefinisikan sebuah daun sebagai LTP, RTP, beberapa digit bukan nol + LTP, atau RTP + beberapa digit bukan nol. Ini semua adalah nilai-nilai yang fbisa ingin memeriksa keutamaan.

Saya merancang tes pseudoprime Fermat yang bekerja untuk semua daun:

      

(63973 adalah nomor Carmichael .)

Jika tes ini mengembalikan nilai true, maka zharus ditambahkan ke set adan kita harus mengulanginya str(z). Bit kode yang bertanggung jawab adalah:

z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)

Pertama, kami ingin menangani kasus ini z == 2. Kami melakukannya dengan hanya menghindarinya di sini dan melakukan pengkodean-keras 2saat kami mendefinisikannya a! (EDIT: Dan tidak ada yang berbahaya terjadi jika kita juga menangkap z == 1.) Jadi kita dapat mengasumsikan itu z ≥ 3sekarang.

Saya telah menerjemahkan beberapa "dan" ke dalam perbandingan rantai pendek hubungan pendek: tiga perbandingan pertama harus berhasil sebelum a.add(z)dan f(u)pernah dievaluasi. Inilah semua peran mereka:

  1. z%91>0mengkodekan kondisi pertama kami. (63973 dapat dibagi dengan 91, yang bukan daun itu sendiri, jadi itulah bagaimana kita mengenalinya.)
  2. 0<2itu selalu benar, tetapi rantai lebih pendek dari and.
  3. 2==pow(2,z,z) mengkodekan kondisi kedua kami.
  4. pow(2,z,z)>a.add(z)memicu penambahan, dan selalu benar, karena set.addpengembalian None, dan bilangan bulat selalu lebih besar dari None.
  5. a.add(z)<f(u)memicu rekursi. Nilai kebenarannya tidak penting.

Ucapan Terima Kasih

  • Dennis menyimpan empat byte ( u=[d+s,s+d][I]u=d[I:]+s+d*I; z==2z<3dan trik mod 91 ). Terima kasih!
Lynn
sumber