Ini adalah urutan A054261
The th nomor penahanan utama adalah jumlah terendah yang berisi pertama bilangan prima sebagai substring. Misalnya, angka adalah angka terendah yang berisi 3 bilangan prima pertama sebagai substring, menjadikannya bilangan penampung prima ke-3.
Sepele untuk mengetahui bahwa empat nomor penahanan prima pertama adalah , , dan , tetapi kemudian semakin menarik. Karena prime berikutnya adalah 11, nomor kontainmen prime berikutnya bukan , tetapi karena terkecil dengan properti.
Namun, tantangan sebenarnya datang ketika Anda melampaui 11. Nomor penahanan utama berikutnya adalah . Perhatikan bahwa dalam nomor ini, substring dan tumpang tindih. Nomor11
13
3
juga tumpang tindih dengan nomor tersebut 13
.
Mudah untuk membuktikan bahwa urutan ini meningkat, karena nomor berikutnya harus memenuhi semua kriteria nomor sebelum itu, dan memiliki satu substring lagi. Namun, urutannya tidak meningkat secara ketat, seperti yang ditunjukkan oleh hasil untuk n=10
dan n=11
.
Tantangan
Tujuan Anda adalah menemukan sebanyak mungkin nomor penahanan utama. Program Anda harus menampilkannya secara berurutan, mulai dari 2 dan naik.
Aturan
- Anda diizinkan untuk nomor perdana hard-code.
- Anda tidak diizinkan untuk nomor penahanan utama kode keras (
2
adalah satu-satunya pengecualian), atau angka ajaib yang membuat tantangan sepele. Tolong berbaik hatilah. - Anda dapat menggunakan bahasa apa pun yang Anda inginkan. Harap sertakan daftar perintah untuk menyiapkan lingkungan untuk mengeksekusi kode.
- Anda bebas menggunakan CPU dan GPU, dan Anda dapat menggunakan multithreading.
Mencetak gol
Skor resmi akan dari laptop saya (dell XPS 9560). Tujuan Anda adalah menghasilkan sebanyak mungkin angka penahanan utama dalam 5 menit.
Spesifikasi
- 2.8GHz Intel Core i7-7700HQ (boost 3.8GHz) 4 core, 8 thread.
- 16GB 2400MHz DDR4 RAM
- NVIDIA GTX 1050
- Linux Mint 18.3 64-bit
Jumlah yang ditemukan sejauh ini, bersama dengan prime terakhir ditambahkan ke nomor:
1 => 2 ( 2)
2 => 23 ( 3)
3 => 235 ( 5)
4 => 2357 ( 7)
5 => 112357 ( 11)
6 => 113257 ( 13)
7 => 1131725 ( 17)
8 => 113171925 ( 19)
9 => 1131719235 ( 23)
10 => 113171923295 ( 29)
11 => 113171923295 ( 31)
12 => 1131719237295 ( 37)
13 => 11317237294195 ( 41)
14 => 1131723294194375 ( 43)
15 => 113172329419437475 ( 47)
16 => 1131723294194347537 ( 53)
17 => 113172329419434753759 ( 59)
18 => 2311329417434753759619 ( 61)
19 => 231132941743475375961967 ( 67)
20 => 2311294134347175375961967 ( 71)
21 => 23112941343471735375961967 ( 73)
22 => 231129413434717353759619679 ( 79)
23 => 23112941343471735359619678379 ( 83)
24 => 2311294134347173535961967837989 ( 89)
25 => 23112941343471735359619678378979 ( 97)
26 => 2310112941343471735359619678378979 (101)
27 => 231010329411343471735359619678378979 (103)
28 => 101031071132329417343475359619678378979 (107)
29 => 101031071091132329417343475359619678378979 (109)
30 => 101031071091132329417343475359619678378979 (113)
31 => 101031071091131272329417343475359619678378979 (127)
32 => 101031071091131272329417343475359619678378979 (131)
33 => 10103107109113127137232941734347535961967838979 (137)
34 => 10103107109113127137139232941734347535961967838979 (139)
35 => 10103107109113127137139149232941734347535961967838979 (149)
36 => 1010310710911312713713914923294151734347535961967838979 (151)
Terima kasih kepada Ardnauld, Ourous, dan japh karena telah memperpanjang daftar ini.
Perhatikan bahwa n = 10
dan n = 11
adalah angka yang sama, karena adalah angka terendah yang berisi semua angka , tetapi juga berisi .
Untuk referensi, Anda dapat menggunakan fakta bahwa skrip Python asli yang saya tulis untuk menghasilkan daftar di atas menghitung 12 istilah pertama dalam waktu sekitar 6 menit.
Aturan tambahan
Setelah hasil pertama masuk, saya menyadari bahwa ada peluang bagus bahwa hasil teratas dapat berakhir dengan skor yang sama. Dalam hal jika seri, pemenang akan menjadi orang dengan waktu tersingkat untuk menghasilkan hasilnya. Jika dua atau lebih jawaban menghasilkan hasil yang sama cepatnya, itu hanya akan menjadi kemenangan yang diikat.
Catatan akhir
5 menit runtime hanya dilakukan untuk memastikan skor yang adil. Saya akan sangat tertarik melihat apakah kita dapat mendorong urutan OEIS lebih lanjut (sekarang ini berisi 17 angka). Dengan kode Ourous ', saya telah menghasilkan semua angka sampai n = 26
, tetapi saya berencana membiarkan kode berjalan untuk jangka waktu yang lebih lama.
Papan angka
- Python 3 + Google OR-Tools : 169
- Scala : 137 (tidak resmi)
- Pemecah TSP Concorde : 84 (tidak resmi)
- Perakitan C ++ (GCC) + x86 : 62
- Bersih : 25
- JavaScript (Node.js) : 24
sumber
n=11
sepele karena Anda hanya perlu memverifikasi yangn=10
juga memenuhi persyaratan baru. Saya juga berpendapat bahwa hard-coding hanya membantu sampain=17
, karena tidak ada angka yang diketahui melebihi titik sejauh yang saya bisa mengetahuinya.[1,22,234,2356,112356,113256,1131724,113171924,1131719234,113171923294,113171923294,1131719237294]
dan memulai pencarian dari masingJawaban:
Python 3 + Google OR-Tools , skor 169 dalam 295 detik (skor resmi)
Bagaimana itu bekerja
Setelah membuang bilangan prima berlebihan yang terkandung dalam bilangan prima lainnya, gambarlah grafik berarah dengan tepi dari setiap prime ke setiap sufiksnya, dengan jarak nol, dan edge ke setiap prime dari masing-masing awalannya, dengan jarak yang ditentukan oleh jumlah digit tambahan . Kami mencari jalur terpendek leksikografis pertama melalui grafik mulai dari awalan kosong, melewati setiap prime (tetapi tidak harus melalui setiap awalan atau akhiran), dan berakhir di akhiran kosong.
Misalnya, berikut adalah tepi jalur optimal ε → 11 → 1 → 13 → 3 → 31 → 1 → 17 → ε → 19 → ε → 23 → ε → 29 → ε → 5 → ε untuk n = 11, sesuai ke string keluaran 113171923295.
Dibandingkan dengan pengurangan langsung ke masalah salesman keliling , perhatikan bahwa dengan menghubungkan bilangan prima secara tidak langsung melalui simpul sufiks / awalan ekstra ini, alih-alih secara langsung satu sama lain, kami telah secara dramatis mengurangi jumlah tepian yang perlu kami pertimbangkan. Tetapi karena node tambahan tidak perlu dilalui tepat sekali, ini bukan lagi contoh TSP.
Kami menggunakan pemecah kendala CP-SAT tambahan dari Google OR-Tools, pertama-tama untuk meminimalkan panjang total jalur, kemudian untuk meminimalkan setiap kelompok digit tambahan secara berurutan. Kami menginisialisasi model dengan hanya kendala lokal: setiap prime mendahului satu sufiks dan berhasil satu awalan, sementara setiap sufiks / awalan mendahului dan berhasil dalam jumlah bilangan prima yang sama. Model yang dihasilkan dapat berisi siklus terputus; jika demikian, kami menambahkan batasan konektivitas tambahan secara dinamis dan jalankan kembali solver.
Kode
Hasil
Berikut adalah 1000 nomor penahanan prima pertama , dihitung dalam 1½ hari pada sistem 8-core / 16-thread.
sumber
C ++ (GCC) + rakitan x86, skor
323662 dalam 259 detik (resmi)Hasil dihitung sejauh ini. Komputer saya kehabisan memori setelah
65
.Semua ini setuju dengan hasil dari pemecah berbasis Concorde , sehingga mereka memiliki peluang bagus untuk menjadi benar.
Changelog:
Perhitungan yang salah untuk panjang konteks yang diperlukan. Versi sebelumnya adalah 1 terlalu besar, dan juga memiliki bug. Nilai:
3234Menambahkan pengoptimalan dengan konteks yang sama. Nilai:
3436Merombak algoritma untuk menggunakan string bebas konteks dengan benar, ditambah beberapa optimasi lainnya. Nilai:
3662Menambahkan penulisan yang tepat.
Menambahkan varian bilangan prima.
Bagaimana itu bekerja
Peringatan: ini adalah dump otak. Gulir ke akhir jika Anda hanya menginginkan kodenya.
Singkatan:
Program ini pada dasarnya menggunakan algoritma pemrograman dinamis buku teks untuk TSP.
Itu banyak bug potensial. Setelah bermain-main dengan entri anselmus dan gagal membujuk salah hasil dari itu, saya setidaknya harus membuktikan bahwa pendekatan saya secara keseluruhan benar.
Meskipun solusi berbasis Concorde (jauh, jauh) lebih cepat, itu didasarkan pada pengurangan yang sama, jadi penjelasan ini berlaku untuk keduanya. Selain itu, solusi ini dapat diadaptasi untuk OEIS A054260 , urutan bilangan prima yang mengandung prime; Saya tidak tahu bagaimana menyelesaikannya secara efisien dalam kerangka TSP. Jadi masih agak relevan.
Pengurangan TSP
Mari kita mulai dengan benar-benar membuktikan bahwa mengurangi menjadi TSP benar. Kami memiliki serangkaian string, katakanlah
dan kami ingin menemukan superstring terkecil yang berisi barang-barang ini.
Mengetahui panjangnya sudah cukup
Untuk PCN, jika ada beberapa string terpendek, kita harus mengembalikan yang terkecil secara leksikografis. Tetapi kita akan melihat masalah yang berbeda (dan lebih mudah).
Jika kita dapat menyelesaikan Panjang SCS, kita dapat merekonstruksi solusi terkecil dan mendapatkan PCN. Jika kami tahu bahwa solusi terkecil dimulai dengan awalan kami, kami mencoba memperluasnya dengan menambahkan setiap item, dalam urutan leksikografis, dan menyelesaikannya untuk panjangnya lagi. Ketika kami menemukan item terkecil yang panjang solusinya sama, kami tahu bahwa ini harus menjadi item berikutnya dalam solusi terkecil (mengapa?), Jadi tambahkan dan kembalikan pada item yang tersisa. Metode untuk mencapai solusi ini disebut pengurangan diri .
Turing grafik tumpang tindih maksimal
Misalkan kita mulai memecahkan SCS untuk contoh di atas dengan tangan. Kami mungkin akan:
13
dan37
, karena mereka sudah substring dari barang-barang lainnya. Setiap solusi yang mengandung137
, misalnya, juga harus mengandung13
dan37
.113,137 → 1137
,211,113 → 2113
dllIni sebenarnya adalah hal yang benar untuk dilakukan, tetapi mari kita buktikan demi kelengkapan. Ambil solusi SCS; misalnya, superstring terpendek
A
adalahdan itu dapat didekomposisi menjadi gabungan dari semua item di
A
:(Kami mengabaikan item yang berlebihan
13, 37
.) Perhatikan bahwa:Kami akan menunjukkan bahwa setiap superstring terpendek dapat diurai seperti ini:
Untuk setiap pasangan item yang berdekatan
x,y
,y
mulai dan berakhir di posisi lebih lambat darix
. Jika ini tidak benar, maka itux
adalah substringy
atau sebaliknya. Tapi kami sudah menghapus semua item yang merupakan substring, sehingga tidak bisa terjadi.Misalkan item yang berdekatan dalam urutan memiliki tumpang tindih kurang dari maksimal, misalnya
21113
bukannya2113
. Tapi itu akan membuat ekstra1
berlebihan. Tidak ada item yang lebih baru membutuhkan inisial1
(seperti dalam 2 1 113), karena itu terjadi lebih awal dari113
, dan semua item yang muncul setelah113
tidak dapat mulai dengan digit sebelumnya113
(lihat poin 1). Argumen serupa mencegah ekstra terakhir1
(seperti dalam 211 1 3) yang digunakan oleh item apa pun sebelumnya211
. Tapi superstring terpendek kami , menurut definisi, tidak akan memiliki angka yang berlebihan, sehingga tumpang tindih non-maksimal tidak akan terjadi.Dengan properti ini, kami dapat mengonversi masalah SCS menjadi TSP:
x
,y
, menambahkan tepi darix
key
yang berat badannya jumlah simbol tambahan ditambahkan dengan menambahkany
untukx
dengan tumpang tindih maksimal. Sebagai contoh, kami akan menambahkan tepi dari211
dengan113
dengan bobot 1, karena2113
menambahkan satu digit lagi211
. Ulangi untuk ujung dariy
kex
.Jalur apa pun pada grafik ini, dari awalan awal, sesuai dengan gabungan maksimal-tumpang tindih semua item di jalur itu, dan bobot total jalur sama dengan panjang string gabungan. Karena itu, setiap tur berbobot terendah, yang mengunjungi semua item setidaknya satu kali, sesuai dengan superstring terpendek.
Dan itulah reduksi dari SCS (dan SCS-Length) ke TSP.
Algoritma pemrograman dinamis
Ini adalah algoritma klasik, tetapi kami akan memodifikasinya sedikit, jadi inilah pengingat cepat.
(Saya telah menulis ini sebagai algoritme untuk SCS-Length alih-alih TSP. Mereka pada dasarnya setara, tetapi kosakata SCS membantu ketika kita sampai pada optimasi spesifik SCS.)
Panggil set item input
A
dan awalan yang diberikanP
. Untuk setiap-k
elemen subsetS
diA
, dan setiap elemene
dariS
, kami menghitung panjang string terpendek yang dimulai denganP
, berisi semuaS
, dan diakhiri dengane
. Ini melibatkan menyimpan tabel dari nilai(S, e)
ke SCS-Lengths mereka.Ketika kita sampai ke setiap subset
S
, tabel harus sudah berisi hasilS - {e}
untuk semuae
dalamS
. Karena tabel bisa menjadi cukup besar, saya menghitung hasilnya untuk semua-k
subset elemen, laluk+1
, dll. Untuk ini, kita hanya perlu menyimpan hasilnya untukk
dank+1
pada satu waktu. Ini mengurangi penggunaan memori dengan faktor kasarsqrt(|A|)
.Satu detail lagi: alih-alih menghitung panjang minimum SCS, saya benar-benar menghitung total tumpang tindih maksimum antara item. (Untuk mendapatkan Panjang SCS, cukup kurangi total tumpang tindih dari jumlah panjang item.) Menggunakan tumpang tindih membantu beberapa optimasi berikut.
[2.] Konteks barang
Sebuah konteks adalah akhiran terpanjang item yang dapat tumpang tindih dengan item berikut. Jika barang kami adalah
113,211,311
, maka11
konteks untuk211
dan311
. (Ini juga merupakan konteks awalan untuk113
, yang akan kita lihat di bagian [4.])Dalam algoritme DP di atas, kami melacak solusi SCS yang diakhiri dengan setiap item, tetapi kami tidak benar-benar peduli item mana yang diakhiri SCS. Yang perlu kita ketahui hanyalah konteksnya. Jadi, misalnya, jika dua SCS untuk set yang sama berakhir pada
23
dan43
, setiap SCS yang melanjutkan dari satu juga akan bekerja untuk yang lain.Ini adalah optimasi yang signifikan, karena bilangan prima non-sepele hanya berakhir pada digit
1 3 7 9
. Keempat konteks satu digit1,3,7,9
(ditambah konteks kosong) sebenarnya cukup untuk menghitung PCNs untuk bilangan prima hingga131
.[3.] Item bebas konteks
Yang lain telah menunjukkan bahwa banyak bilangan prima dimulai dengan angka
2,4,5,6,8
, seperti23,29,41,43...
. Tak satu pun dari ini dapat tumpang tindih dengan bilangan prima sebelumnya (selain dari2
dan5
, bilangan prima tidak dapat berakhir dengan angka-angka ini;2
dan5
sudah akan dihapus sebagai berlebihan). Dalam kode, ini disebut sebagai string bebas konteks .Jika input kami memiliki item bebas konteks, setiap solusi SCS dapat dipecah menjadi blok
dan tumpang tindih di setiap blok tidak tergantung pada blok lainnya. Kami dapat mengocok blok atau menukar item di antara blok yang memiliki konteks yang sama, tanpa mengubah panjang SCS.
Jadi, kita hanya perlu melacak kemungkinan multiset konteks, satu untuk setiap blok.
Contoh lengkap: untuk bilangan prima kurang dari 100, kami memiliki 11 item bebas konteks dan konteksnya:
Konteks multiset awal kami:
Kode mengacu pada ini sebagai konteks gabungan , atau ccontext . Kemudian, kita hanya perlu mempertimbangkan himpunan bagian dari item yang tersisa:
[4.] Penggabungan konteks
Begitu kita mencapai bilangan prima dengan 3 digit atau lebih, ada lebih banyak redundansi:
Kelompok-kelompok ini memiliki konteks awal dan akhir yang sama (biasanya — itu tergantung pada bilangan prima lainnya yang ada di input), sehingga mereka tidak bisa dibedakan ketika tumpang tindih item lainnya. Kami hanya peduli tumpang tindih, sehingga kami dapat memperlakukan bilangan prima dalam kelompok konteks yang sama ini sebagai tidak bisa dibedakan. Sekarang himpunan bagian DP kami diringkas menjadi multisubset
(Ini juga mengapa pemecah memaksimalkan panjang tumpang tindih alih-alih meminimalkan panjang SCS: optimasi ini mempertahankan panjang tumpang tindih.)
Ringkasan: optimasi tingkat tinggi
Berjalan dengan
INFO
output debug akan mencetak statistik sukaBaris khusus ini adalah untuk SCS-Length dari 62 bilangan prima pertama,
2
untuk293
.1,3,7,11,13,27
ditambah string kosong.43,47,53,59,61,89,211,223,227,229,241,251,257,263,269,281,283
. Ini dan awalan yang diberikan (dalam hal ini, string kosong) membentuk dasar dari konteks gabungan awal .N_search
), ada 16 grup dengan konteks sama nontrivial .Dengan mengeksploitasi struktur ini, perhitungan SCS-Length hanya perlu memeriksa 8498336
(multiset, ccontext)
kombinasi. Pemrograman dinamis langsung akan mengambil43×2^43 > 3×10^14
langkah - langkah, dan dengan kasar memaksa permutasi akan mengambil6×10^52
langkah - langkah. Program masih perlu menjalankan SCS-Length beberapa kali lagi untuk merekonstruksi solusi PCN, tetapi itu tidak memakan waktu lebih lama.[5., 6.] Optimalisasi tingkat rendah
Alih-alih melakukan operasi string, pemecah Panjang SCS bekerja dengan indeks item dan konteks. Saya juga menghitung jumlah tumpang tindih antara setiap konteks dan pasangan item.
Kode awalnya menggunakan GCC
unordered_map
, yang tampaknya merupakan tabel hash dengan bucket daftar tertaut dan ukuran hash utama (yaitu divisi mahal). Jadi saya menulis tabel hash saya sendiri dengan probing linier dan kekuatan dua ukuran. Ini menghasilkan 3x speedup dan 3x pengurangan memori.Setiap status tabel terdiri dari beberapa item, konteks gabungan, dan jumlah yang tumpang tindih. Ini dikemas ke dalam entri 128-bit: 8 untuk jumlah tumpang tindih, 56 untuk multiset (sebagai bitet dengan enkode run-length), dan 64 untuk ccontext (RLE 1-dibatasi). Pengkodean dan penguraian ulang ccontext adalah bagian tersulit dan saya akhirnya menggunakan yang baru
PDEP
instruksi (ini sangat baru, GCC belum memiliki intrinsik untuk itu).Akhirnya, mengakses tabel hash benar-benar lambat ketika
N
menjadi besar, karena tabel tersebut tidak muat di cache lagi. Tetapi satu-satunya alasan kami menulis ke tabel hash, adalah untuk memperbarui jumlah tumpang tindih yang paling dikenal untuk setiap negara. Program membagi langkah ini menjadi antrian prefetch, dan loop bagian dalam mengambil setiap tabel pencarian beberapa iterasi sebelum benar-benar memperbarui slot itu. Speedup 2 × lain di komputer saya.Bonus: peningkatan lebih lanjut
AKA Bagaimana Concorde begitu cepat?
Saya tidak tahu banyak tentang algoritma TSP, jadi di sini adalah tebakan kasar.
Concorde menggunakan metode branch-and-cut untuk menyelesaikan TSP.
Gagasan yang jelas dapat kami coba:
Namun, kombinasi branch-and-cut sangat kuat, jadi kita mungkin tidak bisa mengalahkan pemecah canggih seperti Concorde, untuk nilai yang besar
N
.Bonus bonus: bilangan prima penahanan utama
Berbeda dengan solusi berbasis Concorde, program ini dapat dimodifikasi untuk menemukan bilangan prima yang mengandung terkecil ( OEIS A054260 ). Ini melibatkan tiga perubahan:
Ubah kode pemecah Panjang SCS untuk mengategorikan solusi berdasarkan apakah jumlah digitnya dapat dibagi dengan 3. Ini melibatkan penambahan entri lain, digit jumlah mod 3, ke masing-masing negara DP. Ini sangat mengurangi kemungkinan solver utama terjebak dengan permutasi non-prima. Ini adalah perubahan yang saya tidak tahu bagaimana menerjemahkan ke TSP. Itu dapat dikodekan dengan ILP, tetapi kemudian saya harus belajar tentang hal ini yang disebut "ketimpangan subtour" dan bagaimana menghasilkan itu.
Bisa jadi semua PCN terpendek dapat dibagi oleh 3. Dalam hal itu, prime prime kontainment terkecil harus setidaknya satu digit lebih panjang dari PCN. Jika pemecah SCS-Length kami mendeteksi ini, kode rekonstruksi solusi memiliki opsi untuk menambahkan satu digit tambahan pada titik mana pun dalam proses. Ia mencoba menambahkan setiap kemungkinan digit
0..9
dan setiap item yang tersisa ke awalan solusi saat ini, dalam urutan leksikografis seperti sebelumnya.Dengan perubahan ini, saya bisa mendapatkan solusinya hingga
N=62
. Kecuali untuk47
, di mana kode rekonstruksi macet dan menyerah setelah 1 juta langkah (saya belum tahu mengapa, belum). Prima penahanan utama adalah:Kode
Kompilasi dengan
Untuk versi bilangan prima, tautkan juga dengan GMPlib, mis
Program ini menggunakan instruksi PDEP, yang hanya tersedia pada prosesor x86 terbaru (Haswell +). Baik komputer saya dan maxb mendukungnya. Jika milik Anda tidak, program akan dikompilasi dalam versi perangkat lunak yang lambat. Peringatan kompilasi akan dicetak saat ini terjadi.
Cobalah online!
Dan versi utama hanya pada TIO . Maaf, tapi saya tidak golf program ini dan ada batas panjang posting.
sumber
debug_dummy
, Anda dapat menggunakan#define DEBUG(x) void(0)
.debug_dummy
karena saya ingin argumen menjadi tipe diperiksa dan dievaluasi bahkan ketika debugging tidak aktif.N=32
hanya membutuhkan sekitar 500MB, saya pikir.main
, tetapi saya menemukannya dari tautan TIO.JavaScript (Node.js) , skor 24 dalam 241 detik
Hasil
Algoritma
Ini adalah pencarian rekursif yang mencoba semua cara yang memungkinkan untuk menggabungkan angka, dan akhirnya mengurutkan daftar yang dihasilkan dalam urutan leksikografis ketika simpul daun tercapai.
Di awal setiap iterasi, setiap entri yang dapat ditemukan di entri lain dihapus dari daftar.
Percepatan signifikan dicapai dengan melacak node yang dikunjungi, sehingga kami dapat membatalkan lebih awal ketika operasi yang berbeda mengarah ke daftar yang sama.
Sebuah percepatan kecil dicapai dengan memperbarui dan mengembalikan daftar jika memungkinkan daripada menghasilkan salinan, seperti yang disarankan oleh
pengguna anonimNeil.Contoh
Kode
Cobalah online!
sumber
Pemecah Concorde TSP , skor 84 dalam 299 detik
Yah ... saya merasa konyol karena baru menyadari ini sekarang.
Semua ini pada dasarnya adalah masalah salesman keliling . Untuk setiap pasangan bilangan prima
p
danq
, tambahkan tepi yang beratnya adalah jumlah digit yang ditambahkan olehq
(menghapus digit yang tumpang tindih). Juga, tambahkan tepi awal ke setiap primep
, yang beratnya adalah panjangnyap
. Jalur salesman keliling terpendek cocok dengan panjang nomor penahanan perdana terkecil.Kemudian pemecah TSP tingkat industri, seperti Concorde , akan menyelesaikan masalah ini.
Entri ini mungkin harus dianggap tidak bersaing.
Hasil
Solver mencapai
N=350
sekitar 20 jam CPU. Hasil lengkapnya terlalu panjang untuk satu posting SE, dan OEIS tidak menginginkan begitu banyak istilah. Inilah 200 yang pertama:Kode
Berikut ini adalah skrip Python 3 untuk memanggil pemecah Concorde berulang kali hingga membangun solusi.
Concorde gratis untuk penggunaan akademis. Anda dapat mengunduh biner yang dapat dieksekusi dari Concorde yang dibangun dengan paket pemrograman liniernya sendiri QSopt, atau jika Anda entah bagaimana memiliki lisensi untuk IBM CPLEX, Anda dapat membangun Concorde dari sumber untuk menggunakan CPLEX.
sumber
Bersih , skor 25 dalam 231 detik (skor resmi)
Hasil
1 < n <= 23
dalam4236 detik pada TIOn = 24 (2311294134347173535961967837989)
dalam3224 detik secara lokaln = 25 (23112941343471735359619678378979)
dalam210160 detik secara lokaln = 1
untukn = 25
ditemukan dalam 231 detik untuk skor resmi (diedit oleh maxb)Ini menggunakan pendekatan yang mirip dengan solusi JS Arnauld berdasarkan penolakan permutasi berulang, menggunakan set pohon khusus untuk mendapatkan banyak kecepatan.
Untuk setiap prime yang perlu masuk dalam nomor:
Kemudian, untuk setiap pasangan sub-string yang kami gabungkan, hapus semua sub-string dari pasangan yang bergabung dari daftar sub-string dan ulangi lagi.
Setelah tidak ada lagi sub-string yang dapat digabungkan ke sub-string lainnya pada lengan rekursi kami, kami menggunakan susunan pohon yang sudah dipesan untuk dengan cepat menemukan nomor terendah yang berisi sub-string.
Hal-hal yang harus diperbaiki / ditambahkan:
Ada penurunan kinerja yang besar antara
19 -> 20
dan24 -> 25
karena penanganan duplikat oleh langkah uji coba gabungan dan langkah penolakan kandidat, tetapi ini telah diperbaiki.Optimasi:
removeOverlap
dirancang untuk selalu memberikan satu set sub-string yang sudah dalam urutan optimaluInsertMSpec
mengurangi check-if-is-member dan masukkan-new-member ke satu set traversalcontainmentNumbersSt
memeriksa apakah solusi sebelumnya berfungsi untuk nomor baruCobalah online!
Simpan ke
main.icl
dan kompilasi dengan:clm -fusion -b -IL Dynamics -IL StdEnv -IL Platform main
Ini menghasilkan file
a.out
yang harus dijalankan sebagaia.out -h <heap_size>M -s <stack_size>M
, di mana<heap_size> + <stack_size>
memori yang akan digunakan oleh program dalam megabita.(Saya biasanya mengatur stack ke 50MB, tapi saya jarang punya program yang menggunakan sebanyak itu)
sumber
Scala , skor 137Edit:
Kode di sini terlalu menyederhanakan masalah.
Dengan demikian, solusinya bekerja untuk banyak input, tetapi tidak untuk semua.
Pos Asli:
Ide dasar
Masalah yang lebih sederhana
Mari kita sederhanakan masalahnya terlebih dahulu: Kami mencari string yang berisi semuan bilangan prima pertama, singkatnya mungkin. (belum tentu angka terendah)
Pertama, kami membuat himpunan bilangan prima, dan menghapus semua, yang sudah substring orang lain. Kemudian, kita bisa menerapkan beberapa aturan, yaitu jika hanya ada satu string yang berakhir dalam urutan dan hanya satu yang dimulai dengan urutan yang sama, kita bisa menggabungkannya. Yang lain adalah bahwa jika sebuah string dimulai dan diakhiri dengan urutan yang sama (seperti yang dilakukan 101), kita dapat menambahkan / menambahkannya ke string lain tanpa mengubah itu berakhir. (Aturan-aturan itu hanya menghasilkan dalam kondisi tertentu, jadi berhati-hatilah ketika menerapkannya)
Jika kita tidak memiliki sisa ujung / awal string yang sama, kita bisa menggabungkannya dan memiliki string sepanjang minimal yang berisi semuan bilangan prima pertama.
Aturan-aturan itu tidak sepele untuk dipecahkan, tetapi sebagian besar waktu, mereka cukup untuk menyelesaikan masalah ini (saya pikir ..)O ( n4) atau kurang.
Ada kasus (yaitu dalam generasi untukn = 128 ), di mana aturan itu tidak cukup. Di sana, kita harus kembali ke algoritma yang mengambil waktu NP.
Masalah sebenarnya
Dengan algoritma dari atas, kita dapat menghitung panjangnyak hasilnya. Bayangkan kita memiliki permulaan yang diberikan oleh dewa:
Kemudian kita bisa mengambil algoritme kami dari masalah yang disederhanakan untuk menguji apakah ada urutan yang dimulai dengann bilangan prima dan memiliki panjang k . Jika ada, kita dapat melanjutkan dengan angka berikutnya, karena angka terkecil yang dicari tidak boleh lebih besar dari itu. Jika tidak, kami menambah digit terakhir, jadi kami dapat O ( n ⋅ log( n ) ) × waktu untuk algoritma yang lebih sederhana .
10103
0
, berisi semua10103
1
dan mengujinya. Dimulai dengan string kosong, kita dapat menghasilkan nomor yang diinginkanDengan demikian, jika aturan dalam algoritma di atas selalu mencukupi, masalahnya akan ditunjukkan tidak menjadi NP-hard.
Bagian "pemecahan TSP" dalam program saya dilakukan hanya dengan penyederhanaan, jika mungkin (itu mungkin untuk 127 angka pertama). (Jika memungkinkan, kami bisa menerjemahkan ekor-rekursifn = 128 .
findSeq
ke loop, sehingga kami bisa membuktikannya tidak menjadi NP-keras). Itu hanya menjadi rumit, jika penyederhanaan tidak cukup, apa yang terjadi pertama kaliCoba online
Batas waktu scastie setelah 30an, jadi berhenti padan ≈ 75
https://scastie.scala-lang.org/Y9aPRusTRY2ve4avaKAsrA
Kode
Seperti yang ditunjukkan Anders Kaseorg dalam komentar, kode ini dapat mengembalikan hasil yang tidak optimal (dengan demikian, salah).
Hasil
Hasil untukn ∈ [ 1 , 200 ] sesuai dengan yang dari japh kecuali
187
,188
,189
,193
.sumber
1234
,3423
,2345
, Anda menghasilkan123453423
bukannya optimal12342345
.457, 571, 757
(semua bilangan prima).findSeq
akan kembali7574571
untuk ini tetapi yang terpendek adalah457571
. Jadi pendekatan Anda bermain api. Terpilih karena keberanian berani.