Pendahuluan / Latar Belakang
Dalam sebuah diskusi baru - baru ini di chat crypto saya ditantang untuk berdiskusi / membantu dengan tes primality Fermat dan angka-angka Carmichael. Tes ini didasarkan pada premis yang a^(p-1) mod p==1
akan selalu berlaku untuk bilangan prima p
, tetapi tidak selalu untuk komposit. Sekarang nomor carmichael pada dasarnya adalah tes musuh terburuk Fermat: Nomor yang harus Anda pilih a
untuk tidak ikut-ikutan p
mendapatkannya a^(p-1) mod p!=1
. Sekarang jika a
bukan co-prime, Anda pada dasarnya menemukan faktor non-sepelep
dan seperti kita ketahui anjak piutang bisa sangat sulit. Apalagi jika semua faktor cukup besar. Anda sekarang mungkin menyadari mengapa tes Fermat tidak sering digunakan dalam praktik (well, ada algoritma yang lebih baik), itu karena ada angka yang Anda sebagai pembela (dalam hal keamanan) harus melakukan jumlah pekerjaan yang sama seperti seorang penyerang (yaitu faktor nomor).
Jadi sekarang kita tahu mengapa angka-angka ini agak menarik, kita akan menghasilkan mereka dengan cara sesingkat mungkin, jadi kita bisa mengingat kode pembuatan jika kita membutuhkannya!
Nomor Carmichael juga dikenal sebagai A002997 di OEIS .
Sudah ada tantangan terkait , tetapi entri dari sana tidak kompetitif di sini karena mereka dioptimalkan untuk kecepatan dibandingkan dengan ukuran. Argumen yang sama berlaku untuk arah terbalik, entri di sini cenderung membuat trade-off terhadap kecepatan demi ukuran.
Spesifikasi
Memasukkan
Ini adalah tantangan urutan standar , sehingga Anda mengambil bilangan bulat positif atau non-negatif n
sebagai input. n
mungkin 0 atau 1 diindeks sesuai keinginan Anda (sebutkan).
Keluaran
Output Anda akan menjadi n
nomor carmichael -th atau n
nomor carmichael pertama , seperti yang Anda inginkan (sebutkan).
Spesifikasi
Integer x
adalah nomor Carmichael jika dan hanya jika x
komposit dan untuk semua bilangan bulat y
dengan gcd(x,y)=1
, itu menyatakan bahwa y^(x-1) mod x==1
.
Yang menang?
Ini adalah kode-golf , jadi kode terpendek dalam byte menang!
IO standar dan aturan celah berlaku.
Uji Kasus
Beberapa angka carmichael pertama adalah:
561,1105,1729,2465,2821,6601,8911,10585,15841,
29341,41041,46657,52633,62745,63973,75361,101101,
115921,126217,162401,172081,188461,252601,278545,
294409,314821,334153,340561,399001,410041,449065,
488881,512461
sumber
Python 2 , 92 byte
Cobalah online!
1-diindeks dan lambat sebagai molase.
Dalam pemahaman daftar, saya menggunakan metode Dennis untuk menghasilkan semua bilangan bulat coprime ke
n
( total n ), dan kemudian saya menghitungx**~-n%n
untuk semuanya. Mari kita sebut daftar iniL
.Untuk mendeteksi nomor Carmichael, saya membandingkan daftar ini secara leksikografis dengan daftar yang terdiri dari
n-1
satu. Mengapa ini bekerja?Setiap elemen
L
adalah bilangan bulat positif:(k/n)
adalah coprime ton
, begitu(k/n)**~-n
juga adalah, begitu(k/n)**~-n%n > 0
. Dengan demikian, satu-satunya nilai yang mungkin dariL
yang secara leksikografis kurang dari[1]*(n-1)
yang seluruhnya terdiri dari kurang darin-1
yang. (L
tidak dapat berisi lebih darin-1
nilai, karenan
tidak dapat memiliki lebih darin-1
total! Jadi, perbandingan seperti tidak[1,1,1,1,3] < [1,1,1,1]
ada.)Memeriksa bahwa ada kurang dari
n-1
entri dalamL
memastikan yangn
komposit. (Memilikin-1
jumlah adalah kondisi yang setara dengan primality.) Dan kemudian, kondisi untuk menjadi nomor Carmichael adalah persis bahwa setiap elemenL
sama1
. Jadi perbandingan leksikografis ini mendeteksi dengan tepat apa yangL
kami minati.Tn. Xcoder menyimpan byte dengan beralih ke formulir lambda rekursif:
j
menghitung mundur setiap kali kami menekan nomor Carmichael, dann
menghitung setiap kali kami melakukan rekursi. Jadi sekalij
mencapai nol,n-1
sama denganoriginal_value_of_j
angka Carmichael ke-10.sumber
Jelly ,
1211 byte-1 byte terima kasih kepada miles & Mr. Xcoder (penggunaan atom fungsi Carmichael & golfnya)
Tautan monadik yang mengambil
n
dan mengembalikan daftarn
nomor Carmichael pertama .Cobalah online!
Bagaimana?
Sama seperti sebelumnya (di bawah) kecuali bahwa ada built-in untuk fungsi Carmichael - yang menghasilkan daya terkecil sehingga input dinaikkan ke kekuatan itu kongruen dengan satu modulo bahwa daya untuk semua bilangan bulat co-prime ke bilangan bulat itu. Dengan demikian kita dapat mengecualikan false-positif (bilangan prima) dalam lebih sedikit byte dan memiliki kode lebih cepat!
Sebelumnya 12 bytes :
Cobalah online! (Ya, waktunya habis
n=3
).Bagaimana?
Angka,,
c
adalah angka Carmichael jika itu komposit dan memang benar bahwa bilangan bulat mana punx
, dinaikkan kec
kongruen denganx
moduloc
.Kita hanya perlu memeriksa ini positif
x
untukx=c
dirinya sendiri.Perhatikan juga bahwa pada
x=c
cek adalah apakahx
dinaikkan ke kekuatanx
kongruen untukx
modulox
, yang benar - jadi kita tidak perlu memeriksa ini (ini membuat kode lebih pendek).sumber
ECMAScript Regex,
8689 bytePeringatan: Jangan baca ini jika Anda tidak ingin beberapa sihir regex unary dimanjakan untuk Anda. Jika Anda ingin mencoba mencari tahu sendiri keajaiban ini, saya sangat menyarankan memulai dengan menyelesaikan beberapa masalah di ECMAScript regex: lihat posting ini sebelumnya untuk daftar masalah yang direkomendasikan secara spoiler-taged yang direkomendasikan untuk diselesaikan satu per satu.
^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$))((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$)){2,}x$
Cobalah online!
Keajaiban utama regex ini adalah pada bagian yang menyatakan bahwa semua faktor utama N adalah multiplisitas tunggal. Ini adalah trik yang sama seperti yang digunakan oleh string Match saya yang panjangnya adalah kekuatan keempat dan Find the Smoothest Number regexes: pembagian implisit berulang dengan faktor prima terkecil.
Mungkin juga untuk secara langsung menguji bahwa N tidak memiliki faktor kuadrat sempurna (yaitu, bahwa N bebas kuadrat). Ini menggunakan varian dari algoritma multiplikasi yang dijelaskan secara singkat dalam paragraf dari angka saya yang banyak, posting regex untuk menguji apakah suatu angka adalah kuadrat sempurna. Ini adalah spoiler . Jadi jangan membaca lebih jauh jika Anda tidak ingin beberapa sihir regex unary canggih dimanjakan untuk Anda . Jika Anda ingin mencoba mencari tahu sendiri keajaiban ini, saya sangat menyarankan memulai dengan memecahkan beberapa masalah dalam daftar masalah yang direkomendasikan secara spoiler-tag pada posting sebelumnya , dan mencoba untuk menemukan wawasan matematika secara mandiri.
Namun, menggunakan algoritme itu untuk masalah ini tidak memberikan manfaat apa pun. Ini menghasilkan regex lebih lambat, dengan ukuran lebih besar dari 97 byte. Tanpa uji multiplisitas prima (yang dalam satu loop menegaskan baik bahwa setidaknya ada 2 faktor prima dan bahwa mereka masing-masing multiplisitas tunggal), kita harus secara terpisah menyatakan bahwa N adalah komposit.
Cobalah online!
sumber
decision-problem
jawaban, tapi tantangannya adalahsequence
tantangan.) Mungkin dalam varian regex yang lebih kuat akan ada tes yang lebih langsung untuk pembagi kotak yang tersedia?^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$
, atau mungkin bahkan kurang dari 72 byte.J ,
725951 byteCobalah online!
sumber
Retina , 94 byte
Cobalah online! 1-diindeks. Tidak cepat, begitu juga waktu untuk
n>5
TIO. Penjelasan:Tambahkan nilai saat ini. Pada pass pertama, ini juga menghapus
n
dari buffer output (tetapi$+
masih dapat mengaksesnya).Uji apakah nilai saat ini adalah angka Carmichael. Ini menggunakan algoritma alternatif @ Deadcode, karena pendeteksian persegi lebih pendek ketika ditulis menggunakan .NET / Perl / PCRE regex.
Ulangi sampai nilai saat ini adalah angka Carmichael.
Tambahkan nilai saat ini.
Ulangi kenaikan awal dan di atas
n
waktu loop .Ubah hasilnya menjadi desimal.
sumber
Haskell , 95 byte
Cobalah online!
Degolfed:
sumber