Is it a Mersenne Prime?

Question

A number is a Mersenne Prime if it is both prime and can be written in the form 2ⁿ-1, where n is a positive integer.

Your task is to, given any positive integer, determine whether or not it is a Mersenne prime. You may submit either a function which returns a truthy/falsy value, or a full program which performs IO.

Rules:

• As this is code-golf, you should aim to do this in the shortest byte count possible. Builtins are allowed.
• Standard golfing loopholes apply - you cannot read the Mersenne primes from external files, or hardcode them into your program.
• Your program should work for values within your language's standard integer size.

---

Test Cases

For reference, a list of (known) Mersenne Primes can be found here. Some handy test cases are:

2  -> False
1  -> False 
20 -> False
51 -> False
63 -> False

3    -> True
31   -> True
8191 -> True

---

_{Merry Christmas, everybody! Have a great holiday, whatever you celebrate :)}

Answer 1

Scala, 59 Bytes

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

This function requires the input to be a BigInt. You can easily convert a string "162259276829213363391578010288127" (2**107-1 is a Mersenne prime) into BigInt by doing BigInt("162259276829213363391578010288127"). It might go wrong as the name of isProbablePrime() method suggests. But the probability is not more than 0.5^(t.bigLength)*9.

Standalone script version is 72 bytes long.

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

Assume we save it as "t.scala", then then program can be run as

>scala t.scala 162259276829213363391578010288127
>true

Answer 2

Perl 5, 53 bytes

52 bytes of code + 1 for -p

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

Try it online!

Answer 3

J, 16 bytes

*./(#:,1&=@#@q:)

This solution consists of a fork and then a reduce, returns a 1 if true and 0 if false.

The left side of the fork #: returns the binary expansion of the input; the right side 1&=@#@q: produces the prime factors, then tests whether the resulting array contains only a single item (so, whether or not the input is prime). Finally, the middle part of the fork , contains the two results. The result of the fork is reduced with the and operator (*.). Since the 1 less a power of two's binary expansion will only contain ones, we can pretend the binary expansion is actually an array of booleans.

Answer 4

JavaScript (Node.js), 57 bytes

n=>!(n&n+1||(g=(m,q)=>m>3?g(m>>1,(q*q-2)%n):n-3&&q)(n,4))

Try it online! Implements Lucas-Lehmer primality test. Works for n<2**26.5

(FINALLY NATIVE BIGINT SUPPORT IN JS IN 2018. HAIL V8)

For arbitrarily sized integers, try n=>!(n&n+1n||(g=(m,q)=>m>3n?g(m/2n,(q*q-2n)%n):n-3n&&q)(n,4n)) for 62 bytes. Only works in Chrome 67+ and Node.js 10.4.1+ because of BigInt support. Have a try on 2**4423-1!

Answer 5

APL (Dyalog Classic), 21 bytes

1∧.=1∘≠,2∘⊥⍣¯1,¯1↓⊢∨⍳

Verify test cases

Explanation:

Similar method to others here. Prime test + binary representation of Mersenne number being all 1s.

• ¯1↓⊢∨⍳ is a prime test. The length of the result depends on the size of the number but if the number is prime every element of the result list will be 1. (the exception is 1 which annoyingly returns empty list) Catenated with , to....
• 2∘⊥⍣¯1 is the easiest way to encode into binary in Dyalog, by inverting the decode-from-binary operation (yeah i know right), catenated to.....
• 1∘≠ which is there to catch the corner case that the above tests can't tell that 1 isn't a Mersenne prime. (Prime test returns empty list, binary encode results in 1, so result of concatenations contains only 1s)
• If the list resulting from the above operations contains only 1s, the result is a Mersenne prime. 1∧.= checks that all elements are 1.

Answer 6

APL(NARS), chars 20, bytes 40

{0π⍵×∧/⍵⊤⍨2⍴⍨1+⌊2⍟⍵}

0π return true [1] if its argument is prime else return false [0], test:

  f←{0π⍵×∧/⍵⊤⍨2⍴⍨1+⌊2⍟⍵}
  f¨2 1 20 51 63
0 0 0 0 0 
  f¨3 31 8191
1 1 1 

  

Answer 7

Husk, 8 bytes

§&o£İ2→ṗ

Try it online!