Dengan bilangan bulat non-negatif N, hasilkan bilangan bulat positif terkecil terkecil yang merupakan pseudoprime kuat untuk semua Nbasis utama pertama .

Ini adalah urutan OEIS A014233 .

Kasus Uji (satu-diindeks)

1       2047
2       1373653
3       25326001
4       3215031751
5       2152302898747
6       3474749660383
7       341550071728321
8       341550071728321
9       3825123056546413051
10      3825123056546413051
11      3825123056546413051
12      318665857834031151167461
13      3317044064679887385961981

Kasus uji untuk N > 13tidak tersedia karena nilai-nilai tersebut belum ditemukan. Jika Anda berhasil menemukan istilah berikutnya dalam urutan, pastikan untuk mengirimkannya ke OEIS!

Aturan

• Anda dapat memilih untuk mengambil Nsebagai indeks-nol atau nilai satu-indeks.
• Ini dapat diterima untuk solusi Anda untuk hanya bekerja untuk nilai-nilai yang dapat diwakili dalam rentang bilangan bahasa Anda (hingga hingga N = 12bilangan bulat 64-bit yang tidak ditandatangani), tetapi solusi Anda harus secara teoritis bekerja untuk input apa pun dengan asumsi bahwa bahasa Anda mendukung bilangan bulat panjang sewenang-wenang.

Latar Belakang

Setiap bahkan bilangan bulat positif xdapat ditulis dalam bentuk x = d*2^sdi mana daneh. ddan sdapat dihitung dengan membagi berulang kali ndengan 2 sampai hasil bagi tidak lagi habis dibagi 2. dadalah hasil bagi akhir, dan smerupakan jumlah kali 2 membagi n.

Jika bilangan bulat positif nadalah bilangan prima, maka teorema kecil Fermat menyatakan:

Dalam bidang terbatas apa pun Z/pZ(di mana pbilangan prima), satu-satunya akar kuadrat 1adalah 1dan -1(atau, ekuivalen, 1dan p-1).

Kita dapat menggunakan tiga fakta ini untuk membuktikan bahwa salah satu dari dua pernyataan berikut harus benar untuk prime n(di mana d*2^s = n-1dan rmerupakan bilangan bulat [0, s)):

The Miller-Rabin tes primality beroperasi dengan menguji Contrapositive klaim atas: jika ada basis asehingga kedua kondisi di atas adalah palsu, maka ntidak prima. Pangkalan aitu disebut saksi .

Sekarang, menguji setiap pangkalan di [1, n)akan sangat mahal dalam waktu perhitungan untuk besar n. Ada varian probabilistik dari uji Miller-Rabin yang hanya menguji beberapa pangkalan yang dipilih secara acak di bidang terbatas. Namun, ditemukan bahwa pengujian hanya abasa prima yang cukup, dan dengan demikian pengujian dapat dilakukan secara efisien dan deterministik. Faktanya, tidak semua basis utama perlu diuji - hanya sejumlah tertentu yang diperlukan, dan angka tersebut tergantung pada ukuran nilai yang diuji untuk primality.

Jika jumlah basa prima yang diuji tidak mencukupi, pengujian ini dapat menghasilkan hasil positif palsu - bilangan bulat komposit ganjil di mana pengujian gagal membuktikan kesesuaiannya. Khususnya, jika suatu pangkalan agagal untuk membuktikan kekompakan dari suatu bilangan komposit ganjil, angka itu disebut pseudoprime kuat untuk basis a. Tantangan ini adalah tentang menemukan bilangan komposit ganjil yang memiliki psuedoprimes yang kuat untuk semua pangkalan kurang dari atau sama dengan Nbilangan prima th (yang setara dengan mengatakan bahwa mereka adalah pseudoprim yang kuat untuk semua basis prima kurang dari atau sama dengan Nbilangan prima th) .

C, 349 295 277 267 255 byte

N,i;__int128 n=2,b,o,l[999];P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}main(r){for(P(scanf("%d",&N));r|!b;)for(++n,b=i=N;i--&&b;){for(b=n-1,r=0;~b&1;b/=2)++r;for(o=1;b--;o=o*l[i]%n);for(b=o==1;r--;o=o*o%n)b|=o>n-2;for(o=r=1;++o<n;r&=n%o>0);}printf("%llu",n);}

Mengambil input berbasis 1 pada stdin, misalnya:

echo "1" | ./millerRabin

Ini tentu saja tidak akan menemukan nilai-nilai baru dalam urutan dalam waktu dekat, tetapi itu menyelesaikan pekerjaan. UPDATE: sekarang lebih lambat!

• Sedikit lebih cepat dan lebih pendek, dengan inspirasi dari jawaban Neil A ( a^(d*2^r) == (a^d)^(2^r))
• Secara signifikan lebih lambat lagi setelah menyadari bahwa semua solusi untuk tantangan ini akan aneh, sehingga tidak perlu secara tegas menegakkan bahwa kami hanya memeriksa angka ganjil.
• Sekarang menggunakan GCC __int128, yang lebih pendek daripada unsigned long longsaat bekerja dengan angka yang lebih besar! Juga pada mesin little-endian, printf dengan %llumasih berfungsi dengan baik.

Kurang ditambang

N,i;
__int128 n=2,b,o,l[999];
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}
main(r){
    for(P(scanf("%d",&N));r|!b;)
        for(++n,b=i=N;i--&&b;){
            for(b=n-1,r=0;~b&1;b/=2)++r;
            for(o=1;b--;o=o*l[i]%n);
            for(b=o==1;r--;o=o*o%n)b|=o>n-2;
            for(o=r=1;++o<n;r&=n%o>0);
        }
    printf("%llu",n);
}

(Sudah kedaluwarsa) Kerusakan

unsigned long long                  // Use the longest type available
n=2,N,b,i,d,p,o,                    // Globals (mostly share names with question)
l[999];                             // Primes to check (limited to 999, but if you
                                    // want it to be "unlimited", change to -1u)
m(){for(o=1;p--;o=o*l[i]%n);}       // Inefficiently calculates (l[i]^p) mod n

// I cannot possibly take credit for this amazing prime finder;
// See /codegolf//a/5818/8927
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}

main(r){
    for(
        P(scanf("%llu",&N));        // Read & calculate desired number of primes
        r|!b;){                     // While we haven't got an answer:
        n=n+1|1;                    // Advance to next odd number
        for(b=1,i=N;i--&&b;){       // For each prime...
            for(d=n-1,r=0;~d&1;d/=2)++r; // Calculate d and r: d*2^r = n-1
            // Check if there exists any r such that a^(d*2^r) == -1 mod n
            // OR a^d == 1 mod n
            m(p=d);
            for(b=o==1;r--;b|=o==n-1)m(p=d<<r);
            // If neither of these exist, we have proven n is not prime,
            // and the outer loop will keep going (!b)
        }
        // Check if n is actually prime;
        // if it is, the outer loop will keep going (r)
        for(i=r=1;++i<n;r&=n%i!=0);
    }
    printf("%llu",n);               // We found a non-prime; print it & stop.
}

Seperti disebutkan, ini menggunakan input berbasis 1. Tetapi untuk n = 0 menghasilkan 9, yang mengikuti urutan terkait https://oeis.org/A006945 . Tidak lagi; sekarang tergantung pada 0.

Harus bekerja untuk semua n (setidaknya sampai output mencapai 2 ^ 64) tetapi sangat lambat. Saya telah memverifikasi ini pada n = 0, n = 1 dan (setelah banyak menunggu), n = 2.

Python 2, 633 465 435 292 282 275 256 247 byte

Diindeks 0

Pertanyakan implementasi Anda dan coba sesuatu yang baru

Mengubah dari fungsi ke program menghemat beberapa byte entah bagaimana ...

Jika Python 2 memberi saya cara yang lebih pendek untuk melakukan hal yang sama, saya akan menggunakan Python 2. Division secara default integer, jadi cara yang lebih mudah untuk membagi dengan 2, dan printtidak perlu tanda kurung.

n=input()
f=i=3
z={2}
a=lambda:min([i%k for k in range(2,i)])
while n:
 if a():z|={i};n-=1
 i+=2
while f:
 i+=2;d,s,f=~-i,0,a()
 while~d&1:d/=2;s+=1
 for y in z:
  x=y**d%i
  if x-1:
   for _ in[]*s:
    x*=x
    if~x%i<1:break
   else:f=1
print i

Cobalah online!

Python terkenal lambat dibandingkan dengan bahasa lain.

Menentukan tes pembagian percobaan untuk kebenaran absolut, kemudian berulang kali menerapkan uji Miller-Rabin sampai pseudoprime ditemukan.

Cobalah online!

EDIT : Akhirnya pegolf jawabannya

EDIT : Digunakan minuntuk uji keutamaan divisi percobaan dan mengubahnya menjadi a lambda. Kurang efisien, tetapi lebih pendek. Juga tidak bisa menahan diri dan menggunakan beberapa operator bitwise (tidak ada perbedaan panjang). Secara teori seharusnya bekerja (sedikit) lebih cepat.

EDIT : Terima kasih @Dave. Editor saya mengendalikan saya. Saya pikir saya menggunakan tab tetapi itu dikonversi menjadi 4 spasi sebagai gantinya. Juga melewati hampir setiap tip Python tunggal dan menerapkannya.

EDIT : Beralih ke pengindeksan 0, memungkinkan saya untuk menyimpan beberapa byte dengan menghasilkan bilangan prima. Juga memikirkan kembali beberapa perbandingan

EDIT : Menggunakan variabel untuk menyimpan hasil tes, bukan for/elsepernyataan.

EDIT : Memindahkan bagian lambdadalam fungsi untuk menghilangkan kebutuhan akan suatu parameter.

EDIT : Dikonversi ke program untuk menyimpan byte

EDIT : Python 2 menyelamatkan saya byte! Saya juga tidak perlu mengkonversi inputint

Perl + Math :: Prime :: Util, 81 + 27 = 108 byte

1 until!is_provable_prime(++$\)&&is_strong_pseudoprime($\,2..nth_prime($_));$_=""

Jalankan dengan -lpMMath::Prime::Util=:all(penalti 27-byte, aduh).

Penjelasan

Bukan hanya Mathematica yang memiliki builtin untuk dasarnya apa saja. Perl memiliki CPAN, salah satu repositori perpustakaan besar pertama, dan yang memiliki banyak koleksi solusi siap pakai untuk tugas-tugas seperti ini. Sayangnya, mereka tidak diimpor (atau bahkan diinstal) secara default, artinya itu pada dasarnya tidak pernah merupakan pilihan yang baik untuk menggunakannya dalam kode-golf , tetapi ketika salah satu dari mereka kebetulan cocok dengan masalah dengan sempurna ...

Kami berjalan melalui bilangan bulat berturut-turut sampai kita menemukan satu yang tidak prima, dan belum semu yang kuat untuk semua basis bilangan bulat dari 2 ke n th prima. Opsi baris perintah mengimpor pustaka yang berisi builtin dalam pertanyaan, dan juga menetapkan input implisit (untuk baris-pada-waktu; Math::Prime::Utilmemiliki pustaka bignum builtin sendiri yang tidak suka baris baru dalam bilangan bulatnya). Ini menggunakan trik Perl standar untuk menggunakan $\(pemisah jalur keluaran) sebagai variabel untuk mengurangi parsing yang canggung dan memungkinkan keluaran dihasilkan secara implisit.

Perhatikan bahwa kita perlu menggunakan di is_provable_primesini untuk meminta ujian prima deterministik, bukan probabilistik. (Terutama mengingat bahwa tes prime probabilistik kemungkinan menggunakan Miller-Rabin di tempat pertama, yang kami tidak bisa berharap untuk memberikan hasil yang dapat diandalkan dalam kasus ini!)

Perl + Math :: Prime :: Util, 71 + 17 = 88 byte, bekerja sama dengan @Dada

1until!is_provable_prime(++$\)&is_strong_pseudoprime$\,2..n‌​th_prime$_}{

Jalankan dengan -lpMntheory=:all(penalti 17 byte).

Ini menggunakan beberapa trik golf Perl yang saya juga tidak tahu (ternyata Math :: Prime :: Util memiliki singkatan!), Tahu tentang tetapi tidak berpikir untuk menggunakan ( }{untuk output $\secara implisit sekali, daripada"$_$\" secara implisit setiap baris) , atau tahu tentang tetapi entah bagaimana berhasil menyalahgunakan (menghapus tanda kurung dari panggilan fungsi). Terima kasih kepada @Dada karena menunjukkan ini kepada saya. Selain itu, itu identik.