35
\$\begingroup\$

A number is a Mersenne Prime if it is both prime and can be written in the form 2n-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 , 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 :)

\$\endgroup\$
  • 2
    \$\begingroup\$ If I could I'd vote this as a dupe of the isprime challenge, as it doesn't really add anything new. \$\endgroup\$ – flawr Dec 25 '16 at 14:32
  • 9
    \$\begingroup\$ @flawr They are very similar - but for this challenge, there is less likely to be a builtin and there are lots of interesting approaches to determining whether a number is representable as 2^n-1 \$\endgroup\$ – FlipTack Dec 25 '16 at 14:39
  • 1
    \$\begingroup\$ I believe the definition of a Mersenne number also mandates that n be prime (a condition that has also been proven necessary, but not sufficient, for (2^n)-1 to be prime.) \$\endgroup\$ – SuperJedi224 Dec 25 '16 at 15:04
  • 4
    \$\begingroup\$ @SuperJedi224 n is always prime, but knowing that changes nothing, the definition is still correct. \$\endgroup\$ – FlipTack Dec 25 '16 at 15:13
  • 2
    \$\begingroup\$ @TheBitByte Yes - if you're implementing some probability-based algorithm which doesn't work 100% of the time, you can still post it, but it wouldn't be competing :) \$\endgroup\$ – FlipTack Dec 28 '16 at 16:06

34 Answers 34

0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

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 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.