Apakah ini Perdana Mersenne?

35

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 , 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 :)

FlipTack
sumber
2
Jika saya bisa, saya akan memilih ini sebagai penipuan dari tantangan isprime , karena tidak benar-benar menambahkan sesuatu yang baru.
flawr
9
@ flawr Mereka sangat mirip - tetapi untuk tantangan ini, ada kemungkinan kecil menjadi builtin dan ada banyak pendekatan menarik untuk menentukan apakah suatu angka dapat direpresentasikan sebagai2^n-1
FlipTack
1
Saya percaya definisi nomor Mersenne juga mengamanatkan bahwa n menjadi prima (suatu kondisi yang juga telah terbukti perlu, tetapi tidak cukup, untuk (2 ^ n) -1 menjadi prima.)
SuperJedi224
4
@ SuperJedi224 nselalu prima, tetapi mengetahui bahwa tidak mengubah apa pun, definisi tersebut masih benar.
FlipTack
2
@TheBitByte Ya - jika Anda menerapkan beberapa algoritma berbasis probabilitas yang tidak berfungsi 100% setiap saat, Anda masih dapat mempostingnya, tetapi tidak akan bersaing :)
FlipTack

Jawaban:

19

Jelly , 5 byte

&‘<ÆP

Cobalah online!

Bagaimana itu bekerja

&‘<ÆP  Main link. Argument: x

 ‘     Yield x+1.
&      Take the bitwise AND of x and x+1.
       This yields 0 iff x is a Mersenne number, i.e., iff x+1 is a power of 2.
   ÆP  Yield 1 if x is a prime, 0 if not.
  <    Compare the results to both sides,
       This yields 1 iff x is both a Mersenne number and a prime.
Dennis
sumber
Masalah yang sama dengan jawaban Adnan. Lihat mothereff.in/byte-counter
Kelly Lowder
8
@KellyLowder Penghitung byte itu menggunakan UTF-8. Baik Jelly dan 05AB1E menggunakan set karakter byte tunggal.
Dennis
24

05AB1E , 5 byte

Angka positif dalam bentuk 2 n - 1 dalam biner hanya terdiri dari 1 .

Kode:

b`¹pP

Penjelasan:

b`      # Push each digit of the binary representation of the number onto the stack
  ¹p    # Check if the input is prime
    P   # Take the product of all these digits

Menggunakan pengkodean CP-1252 . Cobalah online! atau Verifikasi semua kasus uji .

Adnan
sumber
5
Saya bertanya-tanya berapa lama sampai seseorang menggunakan trik itu :)
FlipTack
¹ membutuhkan 2 byte, jadi ini 6.
Kelly Lowder
5
@KellyLowder Di UTF-8, ya. Namun, 05AB1E menggunakan pengkodean CP-1252 daripada pengkodean UTF-8.
Adnan
10

Python , 45 byte

lambda n:-~n&n<all(n%i for i in range(2,n))<n

Cobalah online!

Bagaimana itu bekerja

Tiga istilah perbandingan dirantai

-~n&n<all(n%i for i in range(2,n))<n

lakukan hal berikut:

  • -~n&nmenghitung 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&nmenghasilkan 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))<nberlaku setiap kali n> 1 , tetapi karena semua mengembalikan Benar jika n = 1 , itu tidak berlaku dalam kasus ini.

Dennis
sumber
1
Wow, itu luar biasa :)
ABcDexter
8

Brachylog , 7 byte

#p+~^h2

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:

#p      Input = A, and is prime
+       B = A + 1
~^      B = X to the power Y, C = the list [X, Y]
h       D = the head of list C (= X)
2       D = 2

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 Cadalah bentuk [2, Y]sebelum ia mencoba untuk menyatakan Bsebagai 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
Saya terkesan! Adapun masalah loop tak terbatas, ini disebabkan oleh kelebihan predikat. Melihat ke belakang, saya pikir saya seharusnya tidak menerapkan kelebihan beban untuk predikat. Ini juga menyebabkan masalah dalam hal-hal seperti findall.
Fatalkan
7

Mathematica 26 Bytes

PerfectNumberQ[# (#+1)/2]&

Lihat bukti ini

Berfungsi asalkan tidak ada angka sempurna ganjil, dan tidak ada yang diketahui ada.

Kelly Lowder
sumber
Jadi jawaban Anda tidak terbukti valid?
Jonathan Frech
Saya tidak berpikir bahwa ruang itu perlu.
Jonathan Frech
@JonathanFrech Formula ini n(n+1)/2menghasilkan (bahkan) angka sempurna kapan pun nadalah prime Mersenne (Euclid). Tampaknya tidak diketahui apakah angka sempurna ganjil dapat memiliki bentuk n(n+1)/2, yaitu menjadi angka segitiga. Semua bahkan angka sempurna adalah segitiga di mana ini nadalah perdana Mersenne (Euler).
Jeppe Stig Nielsen
1
@JeppeStigNielsen Pertanyaannya adalah apakah valid menggunakan fakta yang tidak diketahui sebagai dasar solusinya.
Jonathan Frech
7

Mathematica, 29 26 byte

Sunting: Disimpan 3 byte berkat Martin Ender

PrimeQ@#&&IntegerQ@Log2[#+1]&

PrimeQ@#&&1>BitAnd[#,#+1]&

Saya menduga ini akan lebih cepat karena 42 eksponen pertama dikodekan:

MersennePrimeExponentQ@Log2[#+1]&
ngenisis
sumber
6
PrimeQ@#&&1>BitAnd[#,#+1]&
Martin Ender
5

Perl 6 , 29 byte

{.base(2)~~/^1*$/&&.is-prime}

Cobalah

Diperluas:

{             # bare block lambda with implicit parameter 「$_」

  .base(2)    # is its binary representation ( implicit method call on 「$_」 )
   ~~
  /^ 1* $/    # made entirely of 「1」s

  &&          # and

  .is-prime   # is it prime

}

karena Perl 6 memiliki Ints besar yang sewenang-wenang, ia tidak memenuhi bagian depan .base(2)dengan 0s.

Brad Gilbert b2gills
sumber
5

Python, 83 82 79 76 73 byte

def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

Python 2, 71 byte

def f(m):
 s,n=(m!=3)*4,m/4
 while-~m&m<n:s,n=(s*s-2)%m,n/2
 return s<1

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.

from __future__ import print_function

def primes(n):
    """ Return a list of primes < n """
    # From http://stackoverflow.com/a/3035188/4014959
    sieve = [True] * (n//2)
    for i in range(3, int(n**0.5) + 1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    return [2] + [2*i + 1 for i in range(1, n//2) if sieve[i]]

def lucas_lehmer_old(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = (s * s - 2) % m
    return s == 0 and m or 0

# much faster
def lucas_lehmer(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = s * s - 2
        while s > m:
            s = (s & m) + (s >> p)
    return s == 0 or s == m and m or 0

def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

# Make a list of some Mersenne primes
a = [3]
for p in primes(608):
    m = lucas_lehmer(p)
    if m:
        print(p, m)
        a.append(m)
print()

# Test that `f` works on all the numbers in `a`
print(all(map(f, a))) 

# Test `f` on numbers that may not be Mersenne primes
for i in range(1, 525000):
    u = f(i)
    v = i in a
    if u or v:
        print(i, u, v)
    if u != v:
        print('Error:', i, u, v)

keluaran

3 7
5 31
7 127
13 8191
17 131071
19 524287
31 2147483647
61 2305843009213693951
89 618970019642690137449562111
107 162259276829213363391578010288127
127 170141183460469231731687303715884105727
521 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
607 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

True
3 True True
7 True True
31 True True
127 True True
8191 True True
131071 True True
524287 True True

FWIW, ini versi yang sedikit lebih efisien fyang tidak diuji ulang mpada setiap loop:

def f(m):
 s,n=m!=3and 4,m>>2
 if-~m&m<1:
  while n:
   s=(s*s-2)%m
   n>>=1
 return s<1
PM 2Ring
sumber
Anda dapat menulis loop sementara semua dalam satu baris (tidak perlu baris baru dan
lekukan
@FlipTack D'oh! Terima kasih! Saya benar-benar tidak tahu mengapa saya melewatkan itu ... Dan saya baru sadar saya bisa mencukur beberapa byte lagi dengan kembali ke Python 2.
PM 2Ring
4

R, 41 40 byte

matlab::isprime(x<-scan())&!log2(x+1)%%1

Anehnya builtin di R mersennemengambil nsebagai argumen, bukan 2^n-1.

Ini mengambil xdari STDIN, memeriksa apakah itu prima menggunakan matlabpaket dan memeriksa apakah 2-log dari x+1bilangan bulat dengan mengambil mod 1 dan memeriksa 'bukan nol'.

Juga, jika Anda menggunakan mersennebuiltin, ujungnya menjadi sedikit lebih pendek, tetapi rasanya seperti curang:

numbers::mersenne(log2(scan()+1))

Disimpan 1 byte berkat @Billywob

JAD
sumber
Diposting jawaban yang sama tetapi saya menghapusnya sekarang. Bolehkah saya menyarankan matlab::isprimeuntuk menyimpan satu byte. Anda juga harus menggunakan <-untuk tugas in-function.
Billywob
@ billywob Hanya memperhatikan bahwa matlab :: isprime 1 byte lebih pendek. (dapatkan 1 detik puncak di solusi Anda).
JAD
Anda juga dapat menggunakan log2(x+1)sebagai gantinya log(x+1,2).
Billywob
2

Pyke, 10 byte

_PQb2+}\1q

Coba di sini!

_P         -    is_prime(input)
     +     -   ^ + V
  Qb2      -    base_2(input)
      }    -  uniquify(^)
       \1q - ^ == "1"
Biru
sumber
2

Sebenarnya , 9 byte

;├╔'1=@p*

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.

;├╔'1=@p*
 ├╔'1=     only unique binary digit is 1
        *  and
;     @p   is prime
Mego
sumber
2

Jelly, 5 byte

Pendekatan alternatif untuk jawaban Jelly 5-byte @Dennis yang ada:

B;ÆPP

Cobalah online!

Bagaimana itu bekerja:

B      Returns the binary representation of the input as a list [1, 0, 1, 1, ...]
 ;     And attach to this list 
  ÆP   a 1 if the input is a prime, 0 otherwise
    P  Calculates the product of this list of 1's and 0's

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.

steenbergh
sumber
2

Ceylon, 66 byte

Boolean m(Integer c)=>c>2&&c.and(c+1)<1&&!(2:c-2).any((d)=>c%d<1);

Diformat (dan dikomentari):

// Check whether a (positive integer) number is a mersenne prime number.
//
// Question:  http://codegolf.stackexchange.com/q/104508/2338
// My Answer: http://codegolf.stackexchange.com/a/104805/2338

Boolean m(Integer c) =>
        // check whether c+1 is a power of two
        c.and(c+1)<1 &&
        // the standard primality check by trial division
         !(2 : c-2).any((d) => c%d < 1) &&
        // we need to exclude 1, which is unfortunately
        // matched by both criteria above, but is no prime.
        c>1;

Dengan curang (hardcoding hasil dalam kisaran Ceylon's Integer), kita bisa mendapatkan byte yang lebih pendek (65):

Boolean h(Integer c) =>
        c.and(c+1)<1 && #20000000800a20ac.and(c+1)>0;

(Sepertinya highlighter sintaksis salah paham angka hex Ceylon sebagai awal-komentar).

Jika fungsi anonim tidak apa-apa, yang ini 49 byte:

[2,3,5,7,13,17,19,31,61].map((p)=>2^p-1).contains
Paŭlo Ebermann
sumber
2

Bahasa Wolfram (Mathematica) , 23 byte

PrimeQ[BitAnd[#,#+2]#]&

Cobalah online!

1 ditangani dengan benar karena PrimeQ[BitAnd[1,1+2]*1] == PrimeQ@1 == False. Kalau tidak, untuk BitAnd[#,#+2]#menjadi prima, kita perlu yang #prima dan BitAnd[#,#+2] == 1, yang terjadi ketika #adalah nomor Mersenne.

lirtosiast
sumber
Bagus sekali! Namun, sebagai seseorang yang tidak pernah menggunakan Mathematica, kode TIO Anda membingungkan pada awalnya. Kemudian saya menyadari bahwa Anda membandingkan fungsi Anda dengan pemegang rekaman terikat ngenisis sebelumnya. Saya pikir akan lebih baik hanya untuk menunjukkan output fungsi dan mungkin memiliki tautan kedua yang membandingkannya dengan solusi lain.
Deadcode
2

ECMAScript regex, 42 31 byte

^(?!(xx+)\1+$)(x(x*)(?=\3$))+x$

^
(?!(xx+)\1+$)      # Assert that N is prime or 0 or 1.
(x(x*)(?=\3$))+x$  # Assert that N is a power of 2 minus 1 and is >= 3.
                   # The >=3 part of this prevents the match of 0 and 1.

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. Memasukkan xsebelum 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!

# Match Mersenne primes in the domain ^x*$
^                   # N = input number
(?!                 # "(?!p|q)" is equivalent to "(?!p)(?!q)"; evaluate the
                    # logical AND of the following negative lookaheads:
    (xx+)\1+$       # Assert that N is prime or 0 or 1
|
    ((xx)+)(\2x)*$  # Assert that N is a power of 2 minus 1; this is based
                    # on "(?!(x(xx)+)\1*$)" which matches powers of 2.
)
xx                  # Assert that N >= 2, to prevent the unwanted match of
                    # 0 and 1 by both of the negative lookahead statements.
Kode mati
sumber
1
Hemat 11 byte dengan memeriksa langsung untuk angka 1 kurang dari kekuatan 2: Coba online!
Neil
@Neil Terima kasih banyak! Seandainya saya memikirkan hal itu, tetapi kemudian, ini adalah hal yang saya inginkan terjadi!
Deadcode
1
Sebenarnya memikirkannya akan x(x+)(?=\3$)sedikit lebih efisien?
Neil
Ya, Anda benar sekali.
Deadcode
2

Regex (ECMAScript), 29 byte

^(?!(xx+|(x(x))+)(\1\3)+$)xxx

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.

01
2n-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.

H.Piz
sumber
1

Ruby, 47 byte

->b{!("%b"%(b/2)=~/0/||(2...b).find{|a|b%a<1})}
GB
sumber
1

Julia, 26 byte

n->isprime(n)&&ispow2(n+1)
alephalpha
sumber
1

Python, 65 byte

f=lambda n,i=3:(n^i)-all(n%i for i in range(2,n))<0 or f(n,-~i|i)

Keluaran melalui Kode Keluar. Rekursi Kesalahan karena Salah. Tidak ada kesalahan untuk True.

Bagaimana itu bekerja

Karena 2^n-1dalam biner dibuat seluruhnya dari 1, angka berikutnya 2^n-1dapat dihasilkan oleh number|number+1.

Fungsi ini menggunakan ini dengan secara rekursif memeriksa setiap 2^n-1nomor 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.

Cormac
sumber
1
Jika saya tidak salah, <0~> 0>.
Jonathan Frech
1

Pushy , 7 byte

oBoIpP#

Cobalah online!

Ini mengambil keuntungan dari fakta bahwa angka mersenne hanya memiliki satu dalam representasi biner mereka:

oB      \ Pop input, push its binary digits.
  oI    \ Re-push the input
    p   \ Test its primality (0/1)
     P# \ Print the product of the stack

Produk tumpukan hanya akan 1jika nomor tidak memiliki nol dalam representasi binernya, dan keutamaannya adalah True.

FlipTack
sumber
1

Pyth , 8 byte

&.AjQ2P_

Verifikasi semua kasus uji.

Pyth , 8 byte

<.&QhQP_

Verifikasi semua kasus uji.


Bagaimana?

Rincian Kode # 1

&.AjQ2P_    Full program with implicit input.

      P_    Is Prime?
   jQ2      Convert the input to binary as a list of digits.
 .A         All the elements are truthy (i.e. all are 1).
&           Logical AND.
            Output implicitly.

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

<.&QhQP_    Full program with implicit input.

      P_    Is Prime?
    hQ      Input + 1.
 .&Q        Bitwise AND between the input and ^.
<           Is smaller than? I.e. The bitwise AND results in 0 and the primality test results in 1.
            Output implicitly.

Bagaimana cara kerjanya?

Ini menguji apakah input + 1 adalah kekuatan dua (yaitu jika itu adalah angka Mersenne), dan kemudian melakukan tes primality. Dalam Python, booladalah subkelas dari int, 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).

Tuan Xcoder
sumber
1

Java 8, 53 52 49 byte

n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}

Bug-diperbaiki dan golf dengan 4 byte berkat @Nevay .

Penjelasan:

Coba di sini.

n->{                // Method with integer parameter and boolean return-type
  int i=1;          //  Temp integer `i`, starting at 1
  for(;n%++i>0;);   //  Loop and increase `i` as long as `n` is divisible by `i`
  return(n&n+1|i^n) //  Then return if `n` bitwise-AND `n+1` bitwise-OR `i` bitwise-XOR `n`
          ==0;      //  is exactly 0
}                   // End of method
Kevin Cruijssen
sumber
Solusi saat ini kembali trueuntuk setiap prime> 2, tidak hanya untuk n->{for(int i=2;i<n;n&=-n%i++>>-1);return(n&n+1)<1&n>2;}
prienne
1
52 byte:n->{int i=1;for(;++i<n&n%i>0;);return(n&n+1|i^n)<1;}
Nevay
@Nevay Terima kasih .. Dan tidak yakin mengapa kasus uji tidak menyertakan bilangan prima yang bukan bilangan prima mersenne .. Menambahkannya sendiri, dan Anda memang benar.
Kevin Cruijssen
1
49 byte:n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}
Nevay
1

Python 3, 68 byte

a=int(input());print(a&-~a<1and a>1and all(a%b for b in range(2,a)))

Coba di sini

Python 2, 63 byte

a=input();print(a&-~a<1)and a>1and all(a%b for b in range(2,a))

Coba di sini


Terima kasih atas sarannya Jonathan


Terbuka untuk semua saran untuk mengurangi bytecount.

ABcDexter
sumber
1
1 and~> 1and.
Jonathan Frech
1

Japt, 6 byte

¢¬×&Uj

Jalankan atau Jalankan semua test case

Oliver
sumber
1
Sangat bagus :) Anda bisa mengganti yang logis ©dengan bitwise &untuk output yang konsisten, jika Anda mau.
Shaggy
0

Python, 93 Bytes

def f(a):
 for b in range(a):
  if(a+1==2**b and not[i for i in range(2,a)if a%i<1]):return 1

Kode ini akan berfungsi baik di Python 2 dan Python 3 jadi saya belum menentukan versi.

sonrad10
sumber
0

Racket 76 byte

(define(g m)(for/or((i m))(= m(-(expt 2 i)1))))(if(and(prime? n)(g n))#t #f)

Tidak Disatukan:

(require math)
(define(f n)
  (define (ispowerminus1 m)
    (for/or ((i m))
      (= m (-(expt 2 i)1))))
  (if (and (prime? n)
           (ispowerminus1 n))
      #t #f))

Pengujian:

(f 1)
(f 2)
(f 20)
(f 51)
(f 63)
(f 3)
(f 31)
(f 8191)

Keluaran:

#f
#f
#f
#f
#f
#t
#t
#t
juga
sumber
0

PHP, 53 byte

for($i=$n=$argv[1];--$i&&$n%$i;);echo!($i-1|$n+1&$n);

mengambil argumen baris perintah; cetakan 1untuk Mersenne prime, string kosong yang lain. Jalankan dengan -r.

kerusakan

for($i=$n=$argv[1];--$i&&$n%$i;);   // loop $i down from $n-1 until $i divides $n
                        // If $n is prime, loop ends with $i=1. ($n=1 -> $i=0)
echo!($i-1|$n+1&$n);    // If $i!=1, $n is not prime. If ($n+1&$n)>0, $n is not Mersenne.
                        // If either $i-1 or $n+1&$n is truthy, the negation will be false.
Titus
sumber
0

C, 94 byte

g(n,i){return--i?g(2*n,i):n;}n,r;f(x){for(n=r=1;++n<x;)r=x%n?x^g(2,n)-1?r:r|2:r&2;return r>2;}

Mengembalikan 1 jika nomornya adalah Mersenne Prime, 0 sebaliknya.

Steadybox
sumber
Sarankan ~x+g(2,n)alih-alihx^g(2,n)-1
ceilingcat
0

Scala, 59 Bytes

def f(t:BigInt)=t.isProbablePrime(t.bitLength*9)&(1+t)%2==0

Fungsi ini membutuhkan input menjadi a BigInt. Anda dapat dengan mudah mengkonversi string "162259276829213363391578010288127" (2 ** 107-1 adalah prime Mersenne) menjadi BigIntdengan melakukan BigInt("162259276829213363391578010288127"). Mungkin salah seperti yang isProbablePrime()disarankan oleh nama metode. Tetapi kemungkinannya tidak lebih dari 0.5^(t.bigLength)*9.

Versi skrip mandiri adalah 72 byte.

val t=BigInt(args(0));print(t.isProbablePrime(t.bitLength*9)&(1+t)%2==0)

Asumsikan kita menyimpannya sebagai "t.scala", lalu program dapat dijalankan sebagai

>scala t.scala 162259276829213363391578010288127
>true
Aria Ax
sumber
Anda dapat menghapus Probabledari isProbablePrimejika Scala memiliki isPrimefungsi.
MilkyWay90
0

Perl 5 , 53 byte

52 byte kode +1 untuk -p

$f=0|sqrt;1while$_%$f--;$_=!$f*(sprintf'%b',$_)!~/0/

Cobalah online!

Xcali
sumber
Menurut konsensus meta, the -p ini diklasifikasikan sebagai bahasa pemrograman lain, dan karenanya tidak dihitung dalam bytecount Anda.
MilkyWay90