Jumlahnya 113
adalah prima pertama yang panjangnya 3
prima, jumlah digital 5 = 1 + 1 + 3
prima, dan produk digital 3 = 1 * 1 * 3
prima.
Prime yang memiliki 3 properti ini akan disebut prime prime . Bilangan prima 11117
dan 1111151
contoh lainnya.
Tujuan
Tulis sebuah program yang dapat menemukan bilangan prima terbesar yang sangat mungkin dalam waktu kurang dari satu jam di komputer pribadi modern yang layak (seperti spesifikasi pilihan di sini ).
Anda seharusnya tidak hanya memberi kami prima tertinggi yang besar. Anda harus menunjukkan kepada kami proses pencarian Anda dengan kode yang benar-benar berfungsi. Anda dapat membangun di atas solusi Anda atau orang lain tetapi pastikan untuk memberi mereka pujian. Kami agak secara komunikatif berusaha menemukan prime tertinggi tertinggi yang dapat direalisasikan pada komputer normal dalam satu jam.
Mencetak gol
Pengajuan yang menemukan pemenang tertinggi tertinggi menang. Jika ternyata ada banyak bilangan prima tertinggi maka pengajuan pertama yang menghasilkan kemenangan tertinggi tertinggi.
(Jika Anda dapat membuktikan secara matematis bahwa ada banyak prima tertinggi atau tidak terhingga, saya akan memberi Anda 200 perwakilan bayaran hanya karena. :))
Detail
- Anda dapat menggunakan sumber apa pun untuk menghasilkan bilangan prima Anda (mis. Internet).
- Anda dapat menggunakan metode pengujian prima probabilistik.
- Semuanya ada di base 10.
- Nol dan satu TIDAK dianggap prima.
- Primes yang mengandung
0
memiliki produk digital0
sehingga jelas mereka tidak bisa menjadi yang tertinggi. Untuk menjaga agar halaman tidak berantakan, beri bilangan prima tertinggi (100+ digit) dalam bentuk:
{[number of 1's before the prime digit]}[prime digit]{[number of 1's after the prime digit]}
Jadi
1111151
bisa dinyatakan sebagai{5}5{1}
.
sumber
Jawaban:
Perl, 15101 digit, {83} 7 {15017}, 8 menit. Maks ditemukan: 72227 digit
Menggunakan modul saya Math :: Prime :: Util dan bagian belakang GMP -nya . Ini memiliki sejumlah tes komposit termasuk is_prob_prime () dengan tes ES BPSW (sedikit lebih ketat daripada ispseudoprime Pari), is_prime () yang menambahkan satu MR berbasis acak, dan is_provable_prime () yang akan menjalankan BLS75 T5 atau ECPP. Pada ukuran dan tipe ini, melakukan pembuktian akan memakan waktu lama. Saya melemparkan tes MR lain di sub verifikasi pedantic. Kali pada Core2 E7500 yang jelas bukan komputer tercepat saya (dibutuhkan 2,5 menit pada i7-4770K saya).
Seperti yang ditunjukkan Tim S., kami dapat terus mencari nilai yang lebih besar, sampai pada titik di mana tes tunggal memakan waktu satu jam. Pada ~ 15000 digit pada E7500 ini, dibutuhkan sekitar 26 detik untuk tes MR dan 2 menit untuk is_prime penuh (divisi percobaan ditambah MR basis-2 ditambah ES Lucas plus satu MR basis acak). I7-4770K saya lebih cepat 3x. Saya mencoba beberapa ukuran, terutama melihat bagaimana hasilnya pada hasil orang lain. Saya mencoba 8k, 20k, dan 16k, membunuh masing-masing setelah ~ 5 menit. Saya kemudian mencoba 15k dalam progres untuk ~ 10m masing-masing dan beruntung pada yang keempat.
Tes PRP OpenPFGW tentu saja lebih cepat setelah melewati 4000 atau lebih digit, dan memang jauh lebih cepat dalam kisaran 50k +. Namun, tes ini memiliki jumlah positif palsu yang cukup banyak, yang menjadikannya sebagai pra-tes yang bagus tetapi seseorang masih ingin memverifikasi hasilnya dengan sesuatu yang lain.
Ini bisa diparalelkan dengan benang perl atau menggunakan MCE yang mirip dengan contoh pencari perdana Fibonacci paralel dalam modul.
Pengaturan waktu dan hasil pada i7-4770K idle menggunakan inti tunggal:
Untuk hasil 32k digit, saya memulai 6 skrip yang berjalan pada waktu yang sama, masing-masing dengan argumen berurutan mulai dari 32000. Setelah 26,5 menit satu selesai dengan hasil 3203 digit yang ditunjukkan. Untuk 57k saya membiarkan skrip berturut-turut menjalankan 6 sekaligus selama satu jam dalam penambahan input 500 hingga hasil 57k kembali dalam 57 menit. Hasil digit 72k ditemukan dengan melakukan bilangan prima berturut-turut dari 70k ke atas, jadi pasti tidak ditemukan dalam satu jam (meskipun begitu Anda tahu harus mulai dari mana, itu).
Naskah:
sumber
gmpy2
, dan PyPy denganmy_math
): codepad.org/aSzc0esTforprimes { ...do stuff... } 1e7;
yang 10x atau lebih cepat (pujian ke Pari / GP untuk banyak ide hebat). Saya selalu menghargai umpan balik, jadi beri tahu saya jika ada sesuatu yang tidak berjalan sesuai keinginan Anda.Python 2.7 di PyPy, {2404} 3 {1596} (~ 10 ^ 4000)
Menemukan ini sekitar 50 menit setelah mulai dari 4000. Oleh karena itu, saya akan memperkirakan ini adalah batas atas dari pendekatan kode ini.
Ubah: Saya perhatikan bahwa beberapa panjang tampaknya lebih bermanfaat untuk menghasilkan prime semacam ini daripada yang lain, jadi saya memutuskan untuk hanya memeriksa 50 lokasi acak digit yang bukan 1 bukannya semua lokasi yang mungkin, sebelum pindah di. Saya tidak sepenuhnya yakin ini akan meningkatkan kinerja, atau 50 benar, tetapi kita akan lihat.
Daftar kemungkinan dihasilkan berdasarkan fakta bahwa untuk persyaratan produk yang harus dipenuhi, nomor harus semua yang kecuali prima. Selain itu, prime tidak boleh 2 karena hubungan jumlah dan panjang, dan jumlah digital tidak boleh dibagi tiga, memberikan persyaratan% 3.
is_prime diambil dari http://codepad.org/KtXsydxK , yang ditulis oleh @primo
Catatan: fungsi is_prime ini sebenarnya adalah tes pseudoprime Baillie-PSW, tetapi tidak ada contoh tandingan yang diketahui, jadi saya tidak akan khawatir tentang perbedaannya.
sumber
is_very_very_very_very_very_very_very_probably_prime()
...PARI / GP, 4127 digit
(10 4127 -1) / 9 + 2 * 10 515
Ini adalah pencarian yang cukup mudah: periksa hanya panjang digit prima, lalu hitung bilangan prima yang mungkin digunakan, lalu ulangi semua kemungkinan. Saya khusus menggunakan kasus-kasus umum di mana ada 0 atau 1 digit prima yang cocok untuk digunakan.
Ini membutuhkan waktu 36 menit untuk menghitung pada satu inti dari mesin yang cukup lama. Saya tidak akan kesulitan menemukan yang terbaik lebih dari 5000 digit dalam satu jam, saya yakin, tapi saya juga tidak sabar.
Solusi yang lebih baik adalah dengan menggunakan bahasa apa pun yang masuk akal untuk melakukan segalanya kecuali loop yang paling dalam, lalu buat file abc untuk primeform yang dioptimalkan untuk jenis perhitungan tertentu. Ini harus dapat mendorong perhitungan hingga setidaknya 10.000 digit.
Sunting : Saya menerapkan solusi hibrida yang dijelaskan di atas, tetapi pada mesin lama saya, saya tidak dapat menemukan istilah pertama dengan> = 10.000 digit dalam waktu kurang dari satu jam. Kecuali saya menjalankannya pada sesuatu yang lebih cepat saya harus mengubah ke target yang kurang tinggi.
sumber
Mathematica 3181 digit
Pembaruan: Ada beberapa kesalahan serius dalam pengiriman pertama saya. Saya dapat meluangkan waktu untuk memeriksa hasilnya untuk yang satu ini. Output diformat sebagai daftar digit. Itu membuat mudah memeriksa masing-masing kondisi.
Contoh
Ini adalah tes pertama saya, pencarian solusi dengan 3181 digit. Ditemukan kasus pertama dalam 26 detik.
Mari kita bahas alasannya. Kemudian kita akan masuk ke program itu sendiri.
Mari kita mulai, seperti yang saya lakukan, "Apa prime 450?" Bisakah kita menemukan solusi dengan angka sebanyak itu (3181)?
Nomornya ditemukan dengan bergabung dengan angka.
Tapi alih-alih menampilkannya, kita bisa bertanya apa digit dan di mana mereka berada.
Ini berarti ada 3180 contoh digit 1, dan satu instance digit 7.
Di posisi apa angka 7?
Jadi digit 7 adalah digit ke 142. Yang lainnya adalah 1.
Tentu saja, produk digit harus prima, yaitu 7.
Dan jumlah digit juga prima.
Dan kita tahu bahwa jumlah digit adalah yang utama. Ingat, kami memilih perdana ke-450, yaitu 3118.
Jadi semua syarat sudah terpenuhi.
sumber
4002 * 1 + 7 = 4009
dan bukan 4003 sesuai dengan spesifikasi.Python 2.7, 6217 digit: {23} 5 {6193} 6 mnt 51 dtk
Saya sedang mengerjakan versi saya sendiri dan kecewa melihat @issacg telah mengalahkan saya dengan pukulan dengan pendekatan yang sangat mirip, walaupun dengan is_ (very_probably) _prime (). Namun, saya melihat bahwa saya memiliki beberapa perbedaan signifikan yang menghasilkan jawaban yang lebih baik dalam waktu yang lebih singkat (ketika saya juga menggunakan is_prime). Untuk memperjelas ini, ketika juga mulai dari 4000, saya sampai pada jawaban 4001 digit yang lebih baik ({393} 7 {3607}) hanya dalam 26 menit, 37 detik menggunakan juru bahasa Python standar (juga pada versi 2.7), bukan PyPy versi. Juga, saya tidak 'melihat' memeriksa nomor. Semua kandidat diperiksa.
Inilah peningkatan utama:
Gunakan generator prima ( https://stackoverflow.com/questions/567222/simple-prime-generator-in-python/568618#568618 ) untuk membuat daftar bilangan prima yang akan diperiksa dan (versinya "primes kecil") dan untuk menghasilkan panjang nomor yang memenuhi syarat.
Kami ingin menghabiskan waktu mencari prime prima terbesar dari panjang yang diberikan, bukan yang terkecil, jadi, saya membangun angka terbesar yang mungkin pertama untuk memeriksa, bukan yang terkecil. Kemudian, begitu satu ditemukan, kita dapat langsung beralih ke panjang berikutnya.
EDIT: Sekarang dengan multiprocessing
Ini adalah perubahan signifikan ke versi sebelumnya. Sebelumnya, saya perhatikan bahwa mesin 8-core saya hampir tidak berfungsi, jadi, saya memutuskan untuk mencoba tangan saya di multiprocessing dengan Python (pertama kali). Hasilnya sangat bagus!
Dalam versi ini, 7 proses anak-anak melahirkan, yang mengambil 'tugas' dari antrian kemungkinan potensial (num_length + digit yang memenuhi syarat). Mereka bergerak melalui mencoba berbagai posisi [7,5,3] hingga menemukan satu. Jika ya, informasikan proses master dari panjang terpanjang baru yang telah ditemukan. Jika anak-anak mengerjakan num_length yang lebih pendek, mereka hanya menebus, dan mendapatkan panjang berikutnya.
Saya mulai menjalankan ini dengan 6000, dan masih berjalan, tapi sejauh ini, saya sangat senang dengan hasilnya.
Program ini belum berhenti dengan benar, tetapi bukan masalah besar bagi saya.
Sekarang kodenya:
sumber
my_math
juga dapat digunakan untuk menghasilkan daftar bilangan prima, à lawhile prime < 20006: prime = next_prime(prime)
. Tampaknya sekitar 3 kali lebih cepatgen_primes
, dan jauh lebih efisien memori.C, GMP - {7224} 5 {564} = 7789
Kudos to @issacg dan kalian semua untuk inspirasi dan triknya.
Dan juga penanya ulung @ Calvin Hobbies untuk pertanyaan ini.
Menyusun:
gcc -I/usr/local/include -o p_out p.c -pthread -L/usr/local/lib -lgmp
Jika Anda merasa ingin menyumbangkan kekuatan komputasi Anda atau ingin tahu kinerja, silakan menyalin kode dan kompilasi. ;) Anda perlu GMP diinstal.
sumber
PFGW, 6067 digit, {5956} 7 {110}
Jalankan PFGW dengan file input berikut dan
-f100
untuk menentukan angka-angka. Dalam sekitar 2-3 menit CPU di komputer saya (i5 Haswell), ia menemukan PRP (10 ^ (6073-6) -1) / 9 + 6 * 10 ^ 110, atau {5956} 7 {110} . Saya memilih 6000 digit sebagai titik awal sebagai nomor tanpa lengan saya yang sedikit lebih tinggi dari semua pengiriman sebelumnya.Berdasarkan seberapa cepat saya dapat menemukan yang satu ini, saya dapat dengan mudah menambah jumlah digit dan masih menemukan PRP dalam satu jam. Dengan bagaimana aturan ditulis, saya bahkan mungkin menemukan ukuran di mana CPU saya, berjalan pada semua 4 core, dapat menyelesaikan satu tes PRP dalam satu jam, membutuhkan waktu lama untuk menemukan PRP, dan meminta "pencarian" saya hanya terdiri dari satu PRP.
PS Dalam beberapa hal, ini bukan solusi "kode" karena saya tidak menulis apa pun selain file input ... tapi kemudian, banyak solusi satu-baris Mathematica untuk masalah matematika dapat dijelaskan dengan cara yang sama, seperti yang bisa menggunakan perpustakaan yang melakukan kerja keras untuk Anda. Pada kenyataannya, saya pikir sulit untuk menarik garis yang bagus di antara keduanya. Jika Anda suka, saya bisa menulis skrip yang membuat file input PFGW dan memanggil PFGW. Script bahkan dapat mencari secara paralel, untuk menggunakan semua 4 core dan mempercepat pencarian dengan ~ 4 kali (pada CPU saya).
PPS Saya pikir LLR dapat melakukan tes PRP untuk angka-angka ini, dan saya berharap itu jauh lebih cepat daripada PFGW . Program pengayakan khusus juga bisa lebih baik dalam memfaktorkan angka-angka ini daripada PFGW satu per satu. Jika Anda menggabungkan ini, saya yakin Anda bisa mendorong batas lebih tinggi dari solusi saat ini.
sumber
Python 2.7, 17-19 digit
Ditemukan 511111111111111 (13 digit) dalam 3 detik dan 17 digit prime tertinggi ini dalam 3 menit. Saya kira mesin target bisa menjalankan ini dan mendapatkan 19 digit prime tertinggi dalam waktu kurang dari satu jam. Pendekatan ini tidak skala dengan baik karena membuat bilangan prima hingga setengah dari jumlah digit target dalam memori. Pencarian 17 digit membutuhkan penyimpanan array 100 juta boolean. 19 digit membutuhkan array elemen 1B, dan memori akan habis sebelum mencapai 23 digit. Runtime mungkin juga demikian.
Pendekatan uji primality yang tidak melibatkan sejumlah besar pembagi bilangan prima akan jauh lebih baik.
sumber
Mathematica
42114259 digitDengan nomor:
{1042} 7 {3168}{388} 3 {3870}Yang dihasilkan oleh kode berikut:
Lemparan tersebut menyebabkannya berhenti menguji untuk nomor lain dengan angka yang sama dengan yang saat ini ditemukan. karena ia mulai menguji pada digit paling signifikan, ini berarti bahwa ia selalu mengembalikan angka terbesar kecuali jika jumlah digit adalah anggota dari triplet utama.
Cukup mulai menguji tepat di bawah nilai salah satu jawaban sebelumnya :)
Setelah selesai, nomor tersebut disimpan dalam variabel curlargest
sumber
JavaScript, 3019 digit, {2.273} 5 {745}
Ini menggunakan tes MillerRabin yang disertakan dalam BigInteger.js oleh Tom Wu.
Mulai dari 0 => 2.046 digit = {1799} 7 {263} dalam satu jam .
Mulai dari 3000 => 3.019 digit = {2.273} 5 {745} dalam satu jam, kurang dari 3 detik .
Ketika dimulai dari 0, program melompati dan mulai mencari lagi pada panjang 1,5X panjang s-prime terakhir yang ditemukan. Kemudian ketika saya melihat seberapa cepat itu berjalan saya kira itu akan menemukan satu mulai dari 3000 dalam satu jam - yang dilakukan hanya dengan 3 detik.
Anda dapat mencobanya di sini: http://goo.gl/t3TmTk
(Setel untuk menghitung semua s-primes, atau lewati.)
Program ini bekerja dengan membangun string semua "1", tetapi dengan satu "3", "5", atau "7". Saya menambahkan cek cepat pada fungsi IsStrPrime untuk menolak angka yang diakhiri dengan "5".
Ini sangat menyenangkan. Mengingatkan saya pada sebuah teka-teki yang saya lakukan bertahun-tahun yang lalu untuk menghitung apa yang disebut prima digit dihapus . Ini adalah bilangan prima yang jika Anda menghapus angka apa pun, maka bilangan yang tersisa masih prima. Misalnya 1037 adalah digit prima yang dihapus karena 1037, 037, 137, 107, dan 103 adalah prima. Saya menemukan satu 84 angka, dan yang terlama saya ketahui adalah 332 digit. Saya yakin kita bisa menemukan yang lebih lama dengan teknik yang digunakan untuk teka-teki ini. (Tetapi memilih nomor uji coba sedikit lebih rumit - mungkin?)
sumber
Aksioma, 3019 digit {318} 5 {2700}
hasil dari nilai awal 3000 dalam 529 detik
sumber