Tugas yang dihadapi adalah, diberi nomor n
, menemukan bilangan prima terkecil yang dimulai dengan SETIDAKNYA n
angka 2
di awal bilangan. Ini adalah urutan yang saya temukan di OEIS ( A068103 ).
17 angka pertama dalam urutan diberikan di bawah ini, jika Anda ingin lebih, saya harus benar-benar pergi mengimplementasikan urutan, yang saya tidak keberatan lakukan.
0 = 2
1 = 2
2 = 223
3 = 2221
4 = 22229
5 = 2222203
6 = 22222223 # Notice how 6 and 7 are the same!
7 = 22222223 # It must be **AT LEAST** 6, but no more than necessary.
8 = 222222227
9 = 22222222223 # Notice how 9 and 10 are the same!
10 = 22222222223 # It must be **AT LEAST** 9, but no more than necessary.
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221
Hanya berpikir ini akan menjadi kombinasi yang keren dari manipulasi string, deteksi prima dan urutan. Ini adalah kode-golf , jumlah byte terendah akan dinyatakan sebagai pemenang mungkin di akhir bulan.
x
. Misalnya jika bahasa Anda hanya mendukung bilangan bulat 32-bit, Anda dapat menjelaskannya.Jawaban:
Brachylog ,
1211 byteCobalah online!
Ini secara mengejutkan diterjemahkan ke dalam Brachylog. Ini adalah fungsi, bukan program penuh (walaupun memberikan penerjemah
Z
sebagai argumen baris perintah menyebabkannya menambahkan pembungkus yang sesuai untuk membuat fungsi menjadi program; itulah yang saya lakukan untuk membuat tautan TIO berfungsi). Sangat disayangkan bahwaj
tampaknya -1-diindeks dan perlu koreksi untuk memungkinkannya.Anda dapat membuat argumen yang masuk akal bahwa hal
=
itu tidak perlu, tetapi saya berpikir bahwa mengingat bagaimana masalahnya, itu adalah; tanpa, fungsi menggambarkan himpunan semua bilangan prima yang dimulai dengan angka2
s yang diberikan , dan tanpa beberapa pernyataan eksplisit bahwa program harus melakukan sesuatu dengan deskripsi ini (dalam hal ini, menghasilkan nilai pertama), mungkin tidak mematuhi spesifikasi.Penjelasan
Ketika digunakan sebagai fungsi yang mengembalikan integer, tidak ada yang pernah meminta nilai melewati yang pertama, jadi yang pertama adalah yang harus kita khawatirkan.
Satu kehalusan (ditunjukkan dalam komentar):
:Acb
danb:Ac
secara matematis setara (karena satu menghapus dari awal dan yang lain menambah akhirnya, dengan wilayah di antaranya tidak pernah tumpang tindih); Saya sebelumnya punyab:Ac
, yang lebih alami, tetapi rusak pada input 0 (yang saya duga adalah karenac
menolak untuk menyatukan daftar kosong untuk apa pun; banyak Brin bawaan bawaan cenderung untuk memecah daftar kosong untuk beberapa alasan).:Acb
memastikan bahwac
tidak perlu melihat daftar kosong, yang berarti bahwa kasus input 0 sekarang dapat berfungsi juga.sumber
0
, tanpa alasan yang jelas (Brachylog tampaknya alergi terhadap nol karena beberapa alasan; saya menduga yangc
bertanggung jawab). Yang mengatakan, itu cukup mudah untuk diperbaiki, jadi saya akan memperbaikinya sekarang.b:Ac
tidak berfungsi karena untuk input0
Anda mendapatkan2b:Ac
:2b
memberi0
dan Anda tidak dapat menggunakanc
dengan nol di depan. Alasan untuk ini adalah untuk menghindari loop tak terbatas dalam kasus umum di mana Anda selalu bisa menambahkan nol dan memiliki hasil yang sama.:2rj
alih-alih,2:?j
r
; itu hanya perbaikan biasa. Saya mengerti apa yang terjadic
(Anda tidak ingin banyak hasil ketika dijalankan mundur); namun, peningkatan yang mungkin terjadi adalah untuk tidak mengizinkan input yang merosot hanya jika mereka tidak terikat, sementara memungkinkan mereka ketika input sudah terikat pada nilai yang merosot.Java (OpenJDK 8) ,
164110 byteTerima kasih kepada @FryAmTheEggman untuk banyak byte!
Cobalah online!
sumber
new String(new char[i]))
membuat string panjang unary sama dengan angka. Kemudian regex cocok dengan angka gabungan dengan memeriksa apakah pengulangan satu set angka cocok dengan seluruh string (pada dasarnya divisi percobaan). Jika saya benar, itu berarti Anda harus bisa bermain golf bagian kedua untuk tidak memilikinya?
, saya akan memberi tahu Anda dengan pasti ketika saya sampai di komputer.Pyth, 12 byte
Dalam pseudocode:
Ulangi
lambda
mulai dariT=1
, bertambah 1 hingga kondisi terpenuhi. String2
s harus berupa substring dari awal string, yaitu metode indeks harus kembali0
. Jika substring tidak ditemukan maka ia akan kembali-1
yang dengan nyaman juga benar, sehingga tidak ada kasus luar biasa.Anda dapat mencobanya secara online di sini , tetapi server hanya mengizinkan input
4
.sumber
Perl, 50 byte
49 byte kode +
-p
bendera.Masukkan input tanpa baris akhir final. Contohnya:
Ini membutuhkan waktu beberapa saat untuk menjalankan angka yang lebih besar dari 4 karena menguji setiap angka (ada 2 tes: yang pertama
/^2{$_}/
memeriksa apakah ada cukup 2 di awal, dan yang kedua(1x$\)!~/^1?$|^(11+)\1+$/
menguji primality (dengan kinerja yang sangat buruk)).sumber
Haskell, 73 byte
Contoh penggunaan:
f 3
->2221
.Paksaan.
[1..n]>>"2"
membuat daftarn
2
s yang dibandingkan dengann
karakter pertama dalam representasi string dari prime saat ini.sumber
Mathematica, 103 byte
Fungsi tanpa nama mengambil argumen integer non-negatif
#
dan mengembalikan integer. Ini benar-benar menguji semua bilangan bulat positif pada gilirannya sampai ia menemukan satu yang keduanya dimulai dengan#
2s dan prima. Sangat lambat untuk input di atas 5.hasil sebelumnya: Mathematica, 155 byte
Mathematica akan lebih baik untuk bermain golf jika tidak diketik dengan kuat; kita harus secara eksplisit beralih antara tipe integer / list / string.
Algoritma ini beroperasi pada daftar digit , anehnya, dimulai dengan
{2,...,2,1}
. Selama itu bukan digit dari bilangan prima itu menambahkan satu ke digit terakhir, menggunakan aturan{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}
... dan kemudian secara manual mengimplementasikan membawa-satu-ke-the-digit berikutnya selama salah satu digit sama dengan 10, menggunakan aturan{a__,b_,10,c___}->{a,b+1,0,c}
... dan kemudian, jika kita sudah sejauh ini sehingga yang terakhir dari yang2
s telah berubah menjadi3
, mulai lagi dengan digit lain di ujungnya, menggunakan aturan{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}
. Pada/. 23->2
akhirnya hanya memperbaiki kasus khusus di mana inputnya adalah1
: kebanyakan bilangan prima tidak dapat berakhir2
, tetapi2
bisa. (Beberapa kesalahan diludahkan pada input0
dan1
, tetapi fungsi menemukan jalannya ke jawaban yang benar.)Algoritma ini cukup cepat: sebagai contoh, pada laptop saya dibutuhkan kurang dari 3 detik untuk menghitung bahwa prime pertama dimulai dengan 1.000
2
s22...220521
.sumber
Pyth, 17 byte
Tampaknya tidak dapat menyelesaikannya
n = 4
secara daring, tetapi secara teori memang benar.Penjelasan
sumber
Perl 6 , 53 byte
Cobalah
Diperluas:
sumber
Jelly , 14 byte
Sangat tidak efisien. Cobalah online!
sumber
Pyke, 14 byte
Coba di sini!
12 byte setelah perbaikan bug dan fitur baru
Coba di sini!
sumber
Sage,
6968 byteMenggunakan generator untuk menemukan yang pertama (dari yang terkecil) dari banyak istilah yang tak terhingga.
sumber
Japt, 20 byte
Uji secara online! Ini selesai dalam dua detik pada mesin saya untuk semua input hingga 14, dan setelah itu secara alami kehilangan presisi (JavaScript hanya memiliki presisi integer hingga 2 53 ).
Banyak terima kasih kepada @obarakon untuk mengerjakan ini :-)
Penjelasan
Dalam versi terbaru Japt, ini bisa 12 byte:
Uji secara online! Selesai dalam setengah detik pada mesin saya untuk semua input hingga 14.
sumber
2222203
, hanya222223
dan segera sesudahnya2222210
. Ini juga gagal pada input apa pun yang membutuhkan tiga atau lebih digit tambahan setelah string2
s, seperti input 15.PHP, 76 byte
mengambil input dari argumen baris perintah. Jalankan dengan
-r
.kerusakan
sumber
Bash (+ coreutils), 53 byte
Bekerja hingga 2 ^ 63-1 (9223372036854775807) , membutuhkan banyak waktu untuk menyelesaikan untuk N> 8.
Golf
Uji
sumber
Python 3, 406 byte
kode uji
hasil tes
Saya memutuskan untuk mencari kecepatan pada rentang yang cukup besar, daripada ukuran byte. :) Saya menggunakan tes primality Miller-Rabin deterministik yang dijamin hingga 3317044064679887385961981 dengan set saksi ini. Bilangan prima yang lebih besar akan selalu berhasil lulus tes, tetapi beberapa komposit juga dapat lulus, meskipun kemungkinannya sangat rendah. Namun, saya juga menguji angka output untuk i> 22 menggunakan pyecm sebuah program faktorisasi Kurva Elliptic, dan mereka tampaknya prima.
sumber
p()
panggilan ... OTOH, akan sulit untuk menulis program yang secara signifikan lebih kecil yang dapat memberikan hasil yang benar untuk i> 20 dalam waktu kurang dari satu detik (yang tidak "menipu" dengan memanggil built-in pemeriksa primality). :)Python 3, 132 byte
Setiap harapan kinerja telah dikorbankan untuk jumlah byte yang lebih kecil.
sumber
Java, 163 byte
kode uji
keluaran:
582.5858 milidetik
Penjelasan: loop atas bilangan bulat dan menambahkannya sebagai string ke string root, yang merupakan string "2's" yang diberikan, dan memverifikasi apakah itu prima atau tidak.
sumber
isProbablePrime
memiliki positif palsu sesekali . Itu akan membatalkan jawaban, karena ada keadaan di mana ia mengembalikan nilai yang salah.