Angka adalah Perdana Mersenne jika keduanya prima dan dapat ditulis dalam bentuk 2 n -1 , di mana n adalah bilangan bulat positif.
Tugas Anda adalah, mengingat bilangan bulat positif, menentukan apakah itu prime Mersenne atau tidak. Anda dapat mengirimkan fungsi yang mengembalikan nilai kebenaran / kepalsuan, atau program lengkap yang menjalankan IO.
Aturan:
- Karena ini adalah kode-golf , Anda harus berusaha melakukan ini dalam hitungan byte sesingkat mungkin. Dibangun secara bawaan.
- Lubang golf standar berlaku - Anda tidak bisa membaca bilangan prima Mersenne dari file eksternal, atau meng-hardcode mereka ke dalam program Anda.
- Program Anda harus bekerja untuk nilai-nilai dalam ukuran integer standar bahasa Anda.
Uji Kasus
Untuk referensi, daftar (dikenal) Mersenne Primes dapat ditemukan di sini . Beberapa kasus uji yang berguna adalah:
2 -> False
1 -> False
20 -> False
51 -> False
63 -> False
3 -> True
31 -> True
8191 -> True
Selamat natal semuanya! Selamat menikmati liburan, apa pun yang Anda rayakan :)
2^n-1
n
selalu prima, tetapi mengetahui bahwa tidak mengubah apa pun, definisi tersebut masih benar.Jawaban:
Jelly , 5 byte
Cobalah online!
Bagaimana itu bekerja
sumber
05AB1E , 5 byte
Angka positif dalam bentuk 2 n - 1 dalam biner hanya terdiri dari 1 .
Kode:
Penjelasan:
Menggunakan pengkodean CP-1252 . Cobalah online! atau Verifikasi semua kasus uji .
sumber
Python , 45 byte
Cobalah online!
Bagaimana itu bekerja
Tiga istilah perbandingan dirantai
lakukan hal berikut:
-~n&n
menghitung bitwise AND dari n +1 dan n . Karena n hanya terdiri dari 1 bit jika merupakan angka Mersenne, maka bitwise AND akan mengembalikan 0 jika (dan hanya jika) hal ini terjadi.all(n%i for i in range(2,n))
mengembalikan True jika dan hanya jika n mod i adalah non-nol untuk semua nilai i di [2,…, n - 1] , yaitu, jika dan hanya jika n tidak memiliki pembagi positif selain 1 dan n .Dengan kata lain, semua mengembalikan True jika dan hanya jika n adalah bilangan komposit, yaitu, n adalah 1 atau prima.
n
cukup jelas.Perbandingan berantai mengembalikan Benar jika dan hanya jika perbandingan individu melakukan hal yang sama.
Karena semua mengembalikan Benar / 1 atau Salah / 0 ,
-~n&n<all(n%i for i in range(2,n))
hanya dapat mengembalikan Benar jika-~n&n
menghasilkan 0 (yaitu, jika n adalah angka Mersenne) dan semua mengembalikan Benar (yaitu, jika n salah 1 atau prima).Perbandingan
all(n%i for i in range(2,n))<n
berlaku setiap kali n> 1 , tetapi karena semua mengembalikan Benar jika n = 1 , itu tidak berlaku dalam kasus ini.sumber
Brachylog , 7 byte
Cobalah online!
Program Brachylog pada dasarnya adalah urutan kendala yang membentuk rantai: kendala pertama adalah antara input dan tidak dikenal anonim (sebut saja A untuk tujuan diskusi ini), kendala kedua adalah antara yang tidak diketahui anonim dan anonim kedua tidak diketahui (yang akan kita sebut B ), dan seterusnya. Dengan demikian, program rusak seperti ini:
Satu-satunya cara semua kendala ini dapat dipenuhi secara bersamaan adalah jika B adalah kekuatan 2, yaitu input adalah kekuatan 2 minus 1, dan input juga prima. (Brachylog menggunakan pemecah kendala secara internal, sehingga program tidak akan seefisien seperti yang terlihat pada urutan evaluasi; ia akan mengetahui bahwa itu
C
adalah bentuk[2, Y]
sebelum ia mencoba untuk menyatakanB
sebagai eksponensial dari dua angka.)Menariknya,
#p+~^
hampir berfungsi, karena bilangan prima seperti Mersenne hanya dapat menggunakan 2 sebagai dasar dalam kasus-kasus yang tidak merosot ( bukti ), tetapi a) gagal untuk bilangan prima non-Mersenne B -1 karena dapat dinyatakan sebagai B ¹, dan b ) penerjemah Brachylog yang ada tampaknya bingung (masuk ke loop tak terbatas, atau setidaknya lama,) oleh sebuah program yang dibatasi dengan buruk. Jadi 7 byte sepertinya tidak mungkin dikalahkan di Brachylog.sumber
Mathematica 26 Bytes
Lihat bukti ini
Berfungsi asalkan tidak ada angka sempurna ganjil, dan tidak ada yang diketahui ada.
sumber
n(n+1)/2
menghasilkan (bahkan) angka sempurna kapan punn
adalah prime Mersenne (Euclid). Tampaknya tidak diketahui apakah angka sempurna ganjil dapat memiliki bentukn(n+1)/2
, yaitu menjadi angka segitiga. Semua bahkan angka sempurna adalah segitiga di mana inin
adalah perdana Mersenne (Euler).Mathematica,
2926 byteSunting: Disimpan 3 byte berkat Martin Ender
PrimeQ@#&&IntegerQ@Log2[#+1]&
Saya menduga ini akan lebih cepat karena 42 eksponen pertama dikodekan:
sumber
PrimeQ@#&&1>BitAnd[#,#+1]&
Perl 6 , 29 byte
Cobalah
Diperluas:
karena Perl 6 memiliki Ints besar yang sewenang-wenang, ia tidak memenuhi bagian depan
.base(2)
dengan0
s.sumber
Python,
8382797673 bytePython 2, 71 byte
Fungsi ini mengimplementasikan uji primality Lucas-Lehmer , jadi meskipun tidak sesingkat beberapa penawaran Python lainnya, ini jauh lebih cepat dalam menangani input besar.
Berikut beberapa kode uji yang berjalan pada Python 2 atau Python 3.
keluaran
FWIW, ini versi yang sedikit lebih efisien
f
yang tidak diuji ulangm
pada setiap loop:sumber
R,
4140 byteAnehnya builtin di R
mersenne
mengambiln
sebagai argumen, bukan2^n-1
.Ini mengambil
x
dari STDIN, memeriksa apakah itu prima menggunakanmatlab
paket dan memeriksa apakah 2-log darix+1
bilangan bulat dengan mengambil mod 1 dan memeriksa 'bukan nol'.Juga, jika Anda menggunakan
mersenne
builtin, ujungnya menjadi sedikit lebih pendek, tetapi rasanya seperti curang:Disimpan 1 byte berkat @Billywob
sumber
matlab::isprime
untuk menyimpan satu byte. Anda juga harus menggunakan<-
untuk tugas in-function.log2(x+1)
sebagai gantinyalog(x+1,2)
.Pyke, 10 byte
Coba di sini!
sumber
Sebenarnya , 9 byte
Cobalah online!
Penjelasan:
Karena setiap angka dari bentuk 2 n -1 memiliki semua 1 dalam representasi binernya, sebuah prima Mersenne dapat diidentifikasi sebagai bilangan prima dengan kualitas itu.
sumber
Jelly, 5 byte
Pendekatan alternatif untuk jawaban Jelly 5-byte @Dennis yang ada:
Cobalah online!
Bagaimana itu bekerja:
Karena Perdana Mersenne adalah satu kurang dari kekuatan 2, representasi binernya adalah 1 secara eksklusif. Outputnya adalah 1 untuk bilangan prima Mersenne, dan 0 dalam semua kasus lainnya.
sumber
Ceylon, 66 byte
Diformat (dan dikomentari):
Dengan curang (hardcoding hasil dalam kisaran Ceylon's Integer), kita bisa mendapatkan byte yang lebih pendek (65):
(Sepertinya highlighter sintaksis salah paham angka hex Ceylon sebagai awal-komentar).
Jika fungsi anonim tidak apa-apa, yang ini 49 byte:
sumber
Bahasa Wolfram (Mathematica) , 23 byte
Cobalah online!
1 ditangani dengan benar karena
PrimeQ[BitAnd[1,1+2]*1] == PrimeQ@1 == False
. Kalau tidak, untukBitAnd[#,#+2]#
menjadi prima, kita perlu yang#
prima danBitAnd[#,#+2] == 1
, yang terjadi ketika#
adalah nomor Mersenne.sumber
ECMAScript regex,
4231 byte^(?!(xx+)\1+$)(x(x*)(?=\3$))+x$
Cobalah online!
Sunting: Down to 31 bytes berkat Neil.
Tes dasar "adalah kekuatan 2 minus 1"
^(x(x*)(?=\2$))*$
. Ini bekerja dengan mengulangi operasi "kurangi 1, lalu bagi secara merata dengan 2" hingga tidak dapat dilakukan lebih jauh, kemudian nyatakan bahwa hasilnya adalah nol. Ini dapat dimodifikasi untuk mencocokkan hanya angka ≥1 dengan mengubah yang terakhir*
ke a+
, memaksa loop untuk beralih setidaknya sekali. Memasukkanx
sebelum yang terakhir$
selanjutnya memodifikasinya untuk mencocokkan hanya angka ≥3 dengan menyatakan bahwa hasil akhir setelah pengulangan setidaknya sekali adalah 1.Tes terkait "adalah kekuatan 2"
^((x+)(?=\2$))*x$
. Ada juga istilah untuk kekuatan pencocokan dari 2 minus 2, ditemukan oleh Kotor :^((x+)(?=\2$)x)*$
. Ketiga regex ini memiliki panjang yang sama.Alternatif versi 31 byte, oleh Grimy :
^(?!(xx+)\1+$|((xx)+)(\2x)*$)xx
Cobalah online!
sumber
x(x+)(?=\3$)
sedikit lebih efisien?Regex (ECMAScript), 29 byte
Cobalah online!
Terinspirasi oleh Grimy dalam obrolan
Regex menegaskan bahwa input lebih besar dari 3, dan itu bukan bentuk:
(xx+)\1+
atau((xx)+)(\1x)+
.Yang pertama cocok dengan angka gabungan.
Yang kedua cocok dengan angka yang 1 kurang dari kelipatan dari beberapa angka ganjil lebih besar dari 2.
0
1
Karena 2 adalah satu-satunya prima yang 1 kurang dari prima ganjil, lookahead negatif, bersama dengan pernyataan bahwa input lebih besar dari 3, hanya akan cocok dengan mersenne primes.
sumber
Ruby, 47 byte
sumber
Julia, 26 byte
sumber
Python, 65 byte
Keluaran melalui Kode Keluar. Rekursi Kesalahan karena Salah. Tidak ada kesalahan untuk True.
Bagaimana itu bekerja
Karena
2^n-1
dalam biner dibuat seluruhnya dari 1, angka berikutnya2^n-1
dapat dihasilkan olehnumber|number+1
.Fungsi ini menggunakan ini dengan secara rekursif memeriksa setiap
2^n-1
nomor untuk melihat apakah itu adalah bilangan prima dan eqaul ke input. Jika angka tersebut bukan mersenne prime, python pada akhirnya akan melempar kesalahan karena kedalaman rekursi maksimum akan terlampaui.sumber
<0
~>0>
.Pushy , 7 byte
Cobalah online!
Ini mengambil keuntungan dari fakta bahwa angka mersenne hanya memiliki satu dalam representasi biner mereka:
Produk tumpukan hanya akan
1
jika nomor tidak memiliki nol dalam representasi binernya, dan keutamaannya adalahTrue
.sumber
Pyth , 8 byte
Verifikasi semua kasus uji.
Pyth , 8 byte
Verifikasi semua kasus uji.
Bagaimana?
Rincian Kode # 1
Bagaimana cara kerjanya?
Sejumlah formulir 2 n - 1 selalu berisi 1 hanya ketika ditulis dalam biner. Oleh karena itu, kami menguji apakah semua digit binernya adalah 1 dan jika itu prima.
Rincian Kode # 2
Bagaimana cara kerjanya?
Ini menguji apakah input + 1 adalah kekuatan dua (yaitu jika itu adalah angka Mersenne), dan kemudian melakukan tes primality. Dalam Python,
bool
adalah subkelas dariint
, jadi kebenaran diperlakukan sebagai 1 dan kepalsuan diperlakukan sebagai 0 . Untuk menghindari memeriksa secara eksplisit bahwa satu adalah 0 dan yang lainnya adalah 1 , kami membandingkan nilainya menggunakan<
(karena kami hanya memiliki 1 kasing seperti itu).sumber
Java 8,
535249 byteBug-diperbaiki dan golf dengan 4 byte berkat @Nevay .
Penjelasan:
Coba di sini.
sumber
true
untuk setiap prime> 2, tidak hanya untukn->{for(int i=2;i<n;n&=-n%i++>>-1);return(n&n+1)<1&n>2;}
n->{int i=1;for(;++i<n&n%i>0;);return(n&n+1|i^n)<1;}
n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}
Python 3, 68 byte
Coba di sini
Python 2, 63 byte
Coba di sini
Terima kasih atas sarannya Jonathan
Terbuka untuk semua saran untuk mengurangi bytecount.
sumber
1 and
~>1and
.Japt, 6 byte
Jalankan atau Jalankan semua test case
sumber
©
dengan bitwise&
untuk output yang konsisten, jika Anda mau.Python, 93 Bytes
Kode ini akan berfungsi baik di Python 2 dan Python 3 jadi saya belum menentukan versi.
sumber
Racket 76 byte
Tidak Disatukan:
Pengujian:
Keluaran:
sumber
PHP, 53 byte
mengambil argumen baris perintah; cetakan
1
untuk Mersenne prime, string kosong yang lain. Jalankan dengan-r
.kerusakan
sumber
C, 94 byte
Mengembalikan 1 jika nomornya adalah Mersenne Prime, 0 sebaliknya.
sumber
~x+g(2,n)
alih-alihx^g(2,n)-1
Scala, 59 Bytes
Fungsi ini membutuhkan input menjadi a
BigInt
. Anda dapat dengan mudah mengkonversi string "162259276829213363391578010288127" (2 ** 107-1 adalah prime Mersenne) menjadiBigInt
dengan melakukanBigInt("162259276829213363391578010288127")
. Mungkin salah seperti yangisProbablePrime()
disarankan oleh nama metode. Tetapi kemungkinannya tidak lebih dari0.5^(t.bigLength)*9
.Versi skrip mandiri adalah 72 byte.
Asumsikan kita menyimpannya sebagai "t.scala", lalu program dapat dijalankan sebagai
sumber
Probable
dariisProbablePrime
jika Scala memilikiisPrime
fungsi.Perl 5 , 53 byte
52 byte kode +1 untuk
-p
Cobalah online!
sumber
-p
ini diklasifikasikan sebagai bahasa pemrograman lain, dan karenanya tidak dihitung dalam bytecount Anda.