Tantangan
Temukan penutup pangkalan terkecil (misalnya, moduli) yang rangkaian residu kuadratnya dapat diuji melalui pencarian tabel untuk menentukan secara pasti apakah bilangan bulat non-negatif yang diberikan n adalah kuadrat sempurna. Basis semua harus kurang dari atau sama dengan akar kuadrat dari nilai maksimum n .
Jawaban dengan set pangkalan terkecil untuk kategori tertentu dan memenangkan tantangan. (Ini berarti kemungkinan ada lebih dari satu pemenang.) Kategori n adalah:
Category Maximum allowed n Maximum allowed modulus/base
------------- -------------------- ----------------------------
8-bit values 255 15
16-bit values 65535 255
32-bit values 4294967295 65535
64-bit values 18446744073709551615 4294967295
Jika dasi dengan dua set memiliki kardinalitas yang sama, dasi akan pergi ke set memiliki kemampuan yang lebih besar untuk mendeteksi non-kotak di awal urutan.
Dalam hal tidak ada sampul lengkap yang ditemukan (yang kemungkinan besar untuk kategori 32-bit dan 64-bit), pemenang akan menjadi himpunan pangkalan yang secara statistik atau mungkin mengesampingkan persentase non-kuadrat tertinggi (tanpa salah kotak pelaporan sebagai non-kotak). Lihat di bawah untuk diskusi tentang sampul yang tidak lengkap.
Latar Belakang
Dalam banyak aplikasi teori bilangan, muncul pertanyaan apakah bilangan n adalah kuadrat sempurna (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, dll.). Salah satu cara untuk menguji apakah n adalah kuadrat adalah dengan menguji apakah lantai (√n) ² = n, yaitu, apakah akar kuadrat bulat-bawah dari n , ketika kuadrat, memberikan kembali n . Misalnya, lantai (√123) ² = 11² = 121, yang bukan 123, jadi 123 tidak persegi; tetapi lantai (√121) ² = 11² = 121, jadi 121 berbentuk bujur sangkar. Metode ini berfungsi dengan baik untuk angka-angka kecil, terutama ketika operasi akar kuadrat perangkat keras tersedia. Tetapi untuk jumlah besar (ratusan atau ribuan bit) bisa sangat lambat.
Cara lain untuk menguji kuadrat adalah untuk menyingkirkan non-kuadrat menggunakan tabel residu kuadratik. Sebagai contoh, semua kuadrat dalam basis 10 harus memiliki digit akhir (satu-tempat) yaitu 0, 1, 4, 5, 6, atau 9. Nilai-nilai ini membentuk himpunan residu kuadratik untuk basis 10. Jadi jika basis -10 Nomor berakhir pada 0, 1, 4, 5, 6, atau 9, Anda tahu bahwa itu mungkin persegi, dan pemeriksaan lebih lanjut akan diperlukan. Tetapi jika nomor basis-10 berakhir pada 2, 3, 7, atau 8, maka Anda dapat yakin bahwa itu bukan kotak.
Jadi mari kita lihat basis lain. Semua kotak di basis 8 harus diakhiri dengan 0, 1, atau 4, yang dengan mudah hanya 3 dari 8 kemungkinan, yang berarti peluang 37,5% dari angka acak menjadi kuadrat, atau 62,5% kemungkinan nomor acak jelas tidak berbentuk kuadrat. Itu adalah peluang yang jauh lebih baik daripada yang diberikan base 10. (Dan perhatikan bahwa operasi modulus basis-8 hanyalah operasi logis-dan, sebagai lawan dari modulus basis-10, yang merupakan pembagian dengan 10 dengan sisanya.)
Apakah ada basis yang lebih baik? Ya, sebenarnya. Basis 120 memiliki 18 kemungkinan (0, 1, 4, 9, 16, 24, 25, 36, 40, 49, 60, 64, 76, 81, 84, 96, 100, dan 105), yang hanya mewakili 15% kemungkinan menjadi persegi. Dan base 240 lebih baik lagi, dengan hanya 24 kemungkinan, yang hanya mewakili 10% kemungkinan menjadi persegi.
Tetapi tidak ada satu basis pun yang dapat menentukan kuadrat secara definitif (kecuali jika lebih besar dari jumlah maksimum yang diuji, yang sangat tidak praktis). Satu basis saja dapat mengesampingkan kuadrat; itu tidak dapat secara meyakinkan memverifikasi kuadrat. Hanya satu set pangkalan yang dipilih dengan hati-hati, yang bekerja bersama, yang dapat memverifikasi secara meyakinkan kuadrat atas serangkaian bilangan bulat.
Jadi, pertanyaannya menjadi: Kumpulan basis apa yang membentuk perlindungan minimal yang secara bersama-sama mengizinkan pengurangan definitif kuadrat atau non-kuadrat?
Contoh penutup yang benar tetapi tidak minimal
Penutup 16 penutup bawah {3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37} cukup untuk menentukan secara definitif kuadrat atau non-kuadrat dari semua nilai 16-bit 0 hingga 65535. Tetapi ini bukan penutup minimal , karena setidaknya ada 15 penutup dasar yang juga mudah ditemukan. Faktanya, ada kemungkinan bahwa cakupan yang jauh lebih kecil ada - mungkin dengan sedikitnya 6 atau 7 pangkalan.
Tapi untuk ilustrasi, mari kita lihat menguji nilai sampel n menggunakan set penutup 16-dasar ini. Berikut adalah set residu kuadrat untuk set pangkalan di atas:
Base m Quadratic residue table specific to base m
------ ----------------------------------------------------
3 {0,1}
4 {0,1}
5 {0,1,4}
7 {0,1,2,4}
8 {0,1,4}
9 {0,1,4,7}
11 {0,1,3,4,5,9}
13 {0,1,3,4,9,10,12}
16 {0,1,4,9}
17 {0,1,2,4,8,9,13,15,16}
19 {0,1,4,5,6,7,9,11,16,17}
23 {0,1,2,3,4,6,8,9,12,13,16,18}
25 {0,1,4,6,9,11,14,16,19,21,24}
29 {0,1,4,5,6,7,9,13,16,20,22,23,24,25,28}
31 {0,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28}
37 {0,1,3,4,7,9,10,11,12,16,21,25,26,27,28,30,33,34,36}
Sekarang mari kita coba angka n = 50401 menggunakan set pangkalan ini, dengan mengubahnya menjadi setiap pangkalan. (Ini bukan cara yang paling efisien untuk memeriksa residu, tetapi cukup untuk tujuan penjelasan.) Ini adalah tempat 1 yang kami minati di sini (ditandai di bawah dalam tanda kurung):
Base "Digits" in base m
m m^9 m^8 m^7 m^6 m^5 m^4 m^3 m^2 m^1 ( m^0 )
---- -----------------------------------------------------------------
3 2 1 2 0 0 1 0 2 0 ( 1 ) ✓
4 3 0 1 0 3 2 0 ( 1 ) ✓
5 3 1 0 3 1 0 ( 1 ) ✓
7 2 6 6 6 4 ( 1 ) ✓
8 1 4 2 3 4 ( 1 ) ✓
9 7 6 1 2 ( 1 ) ✓
11 3 4 9 5 ( 10 )
13 1 9 12 3 ( 0 ) ✓
16 12 4 14 ( 1 ) ✓
17 10 4 6 ( 13 ) ✓
19 7 6 11 ( 13 )
23 4 3 6 ( 8 ) ✓
25 3 5 16 ( 1 ) ✓
29 2 1 26 ( 28 ) ✓
31 1 21 13 ( 26 )
37 36 30 ( 7 ) ✓
Jadi kita dapat melihat bahwa di 13 basis ini, residu cocok dengan residu kuadratik yang dikenal (sebut ini "hit" dalam tabel), dan pada 3 basis ini, residu tidak cocok dengan residu kuadratik yang dikenal (sebut ini sebagai "Rindu"). Yang diperlukan hanyalah 1 ketinggalan untuk mengetahui bahwa angka itu adalah non-kuadrat, sehingga kita bisa berhenti di 11, tetapi untuk tujuan ilustrasi, kami telah memeriksa semua 16 pangkalan di sini.
Contoh sampul yang tidak lengkap
Secara teknis, penutup yang tidak lengkap bukanlah penutup, tapi itu intinya. Himpunan basis {7, 8, 11, 15} hampir mencakup semua nilai 8-bit n dari 0 hingga 255 dengan benar, tetapi tidak cukup. Secara khusus, ini secara keliru mengidentifikasi 60 dan 240 sebagai bujur sangkar (ini adalah false positive) - tetapi ia mengidentifikasi dengan benar semua kotak yang sebenarnya (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, dan 225) dan tidak membuat kesalahan positif lainnya. Jadi ini adalah 4-set yang hampir berhasil sebagai solusi, tetapi akhirnya gagal, karena tutup yang tidak lengkap bukanlah solusi yang valid.
Untuk 8-bit n , himpunan basis {7, 8, 11, 15} adalah salah satu dari dua himpunan 4 pangkalan yang menghasilkan dua kesalahan, dan ada tujuh himpunan 4 pangkalan yang hanya menghasilkan satu kesalahan. Tidak ada set 4 pangkalan yang benar-benar ada yang membentuk penutup nilai 8-bit yang lengkap dan akurat. Bisakah Anda menemukan satu set 5 pangkalan yang tidak menghasilkan kesalahan, mencakup semua nilai 8-bit dengan benar? Atau apakah Anda membutuhkan 6 atau lebih? (Saya tahu jawabannya untuk 8-bit n , tapi saya tidak akan memberikannya. Saya tidak tahu jawabannya untuk 16-bit, 32-bit, atau 64-bit, dan saya percaya bahkan pada 16- kasus bit tidak mungkin untuk diselesaikan melalui pencarian brute-force. Memecahkan kasus 32-bit dan 64-bit tentu akan membutuhkan teknik pencarian genetik, heuristik, atau lainnya.)
Sebuah komentar tentang angka yang besar secara kriptografis
Melampaui angka 64-bit - naik dalam ratusan atau ribuan digit biner - ini adalah tempat pemeriksaan kuadrat cepat benar-benar berguna, bahkan jika penutupnya tidak lengkap (yang pastinya akan menjadi angka yang sangat besar). Bagaimana tes seperti ini masih bermanfaat bahkan jika itu tidak cukup menentukan? Nah, bayangkan Anda memiliki tes yang sangat cepat untuk kuadrat yang bekerja dengan benar 99,9% dari waktu dan memberikan negatif palsu sisa 0,1% dari waktu dan tidak pernah memberikan positif palsu. Dengan tes semacam itu, Anda akan dapat menentukan non-kuadrat dari angka hampir secara instan, dan kemudian dalam kasus keraguan yang luar biasa, Anda kemudian dapat menggunakan metode yang lebih lambat untuk menyelesaikan yang tidak dikenal dengan cara yang berbeda. Ini akan menghemat sedikit waktu.
Misalnya, himpunan {8, 11, 13, 15} benar 99,61% dari waktu untuk nilai 8-bit dari n hingga 0, 255, benar 95,98% dari waktu untuk nilai 16-bit dari n dari 0 hingga 65535, dan benar 95.62% dari waktu untuk nilai 24-bit n dari 0 hingga 16777215. Ketika n berlanjut hingga tak terhingga, persentase kebenaran untuk set pangkalan ini turun, tetapi secara asimptotik mendekati dan tidak pernah turun di bawah 95,5944% ketepatan.
Jadi, bahkan kumpulan yang sangat kecil dari 4 pangkalan kecil ini berguna untuk segera mengidentifikasi sekitar 22 dari 23 jumlah besar yang sewenang-wenang sebagai non-kuadrat - meniadakan kebutuhan untuk pemeriksaan lebih lanjut dari angka-angka itu dengan metode yang lebih lambat. Metode yang lebih lambat hanya perlu diterapkan dalam persentase kecil kasus yang tidak dapat dikesampingkan dengan tes cepat ini.
Sangat menarik untuk dicatat bahwa beberapa pangkalan 16-bit mencapai lebih baik dari 95% sendiri. Bahkan, masing-masing pangkalan di bawah ini mampu menyingkirkan lebih dari 97% dari semua bilangan hingga tak terbatas karena tidak berbentuk bujur sangkar. Set residu kuadrat untuk masing-masing pangkalan ini dapat direpresentasikan sebagai array paket-bit yang hanya menggunakan 8192 byte.
Berikut adalah 10 pangkalan tunggal terkuat yang kurang dari 2 ^ 16:
Rank Base Prime factorization Weeds out
---- ------------------------------ ---------
1. 65520 = 2^4 x 3^2 x 5 x 7 x 13 97.95%
2. 55440 = 2^4 x 3^2 x 5 x 7 x 11 97.92%
3. 50400 = 2^5 x 3^2 x 5^2 x 7 97.56%
4. 52416 = 2^6 x 3^2 x 7 x 13 97.44%
5. 61200 = 2^4 x 3^2 x 5^2 x 17 97.41%
6. 44352 = 2^6 x 3^2 x 7 x 11 97.40%
7. 63360 = 2^7 x 3^2 x 5 x 11 97.39%
8. 60480 = 2^6 x 3^3 x 5 x 7 97.38%
9. 63840 = 2^5 x 3 x 5 x 7 x 19 97.37%
10. 54720 = 2^6 x 3^2 x 5 x 19 97.37%
Lihat sesuatu yang menarik yang dimiliki oleh semua pangkalan ini? Tidak ada alasan untuk berpikir bahwa mereka mungkin berguna dalam kombinasi bersama (mungkin memang benar, mungkin tidak), tetapi ada beberapa petunjuk bagus di sini mengenai pangkalan apa yang paling berpengaruh bagi kategori angka yang lebih besar.
Tantangan sampingan: Salah satu pangkalan yang paling berpengaruh (jika bukan yang paling) hingga 2 ^ 28 adalah 245044800, yang sendirian dapat dengan benar menyingkirkan 99,67% dari non-kuadrat, atau sekitar 306 dari 307 angka acak yang dilemparkan padanya. Dapatkah Anda menemukan yang basa tunggal paling berpengaruh kurang dari 2 ^ 32?
Terkait
Ada beberapa ide yang sangat bagus dalam pertanyaan-pertanyaan berikut yang terkait erat, serta beberapa trik optimasi mikro untuk membuat operasi tertentu lebih cepat. Meskipun pertanyaan terkait tidak secara khusus ditetapkan untuk menemukan set pangkalan terkuat, gagasan basis kuat secara implisit pusat beberapa teknik optimasi yang digunakan di sana.
sumber
Jawaban:
Mathematica
Saya tidak benar-benar tahu banyak tentang teori bilangan (sayangnya), jadi ini adalah pendekatan yang agak naif. Saya menggunakan algoritma serakah yang selalu menambahkan basis yang memiliki paling banyak ketinggalan untuk angka yang tersisa.
Ini memecahkan 8 bit dalam waktu singkat dengan 6 basis berikut:
16 bit mengambil 6s dan menghasilkan penutup 6-basis berikut:
Untuk kasus yang lebih besar, pendekatan ini jelas kehabisan memori.
Untuk melampaui 16 bit, saya harus mencari cara untuk memeriksa penutup menjadi lengkap tanpa benar-benar membuat daftar semua angka hingga N maks (atau pergi dan belajar tentang teori nomor).
Sunting: Mengurangi runtime untuk 16 bit dari 66s ke 8s dengan mempopulasikan daftar nomor dengan hanya mereka yang tidak dikesampingkan oleh basis paling efektif. Ini juga harus secara signifikan meningkatkan jejak memori.
Sunting: Saya menambahkan dua optimisasi kecil untuk mengurangi ruang pencarian. Ini bukan salah satu kategori resmi, tetapi dengan itu saya menemukan sampul 8-base untuk 24 bit dalam 9,3 jam:
Adapun optimasi, saya sekarang melewatkan semua basis yang membagi LCM dari basis sudah di sampul, dan ketika saya menguji efisiensi basis saya hanya mengujinya terhadap angka hingga LCM dari basis baru dan semua basis yang sudah saya miliki memiliki.
sumber