Find the nth Mersenne Prime

Question

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

For example:

• 7 is a Mersenne Prime because it is 2³-1
• 11 is not a Mersenne Prime because it cannot be written as 2^m-1
• 15 is not a Mersenne Prime because it is not prime

The first few Mersenne primes:

• 3
• 7
• 31
• 127
• 8191

Your task:

• Take a user input (it will be a positive integer) - let's call it n
• Find the n^th Mersenne prime and output it in the format shown below

Example output:

With an input of 4, the output should be 127. (But this is sequence so any form of output is allowed)

---

I'll add my attempt at this as an answer, but I'm sure that it can be golfed down a bit.

As this is code-golf, all languages are accepted, and the shortest answer wins!

Answer 1

JavaScript (ES6), 50 bytes

Returns the \$n\$-th Mersenne prime, 1-indexed.

n=>{for(k=1;n;n-=d<2)for(d=k-=~k;k%--d;);return k}

Try it online!

eval() version, 48 bytes

Suggested by @Steffan

n=>eval(`for(k=1;n;n-=d<2)for(d=k-=~k;k%--d;)k`)

Try it online!

How?

Numbers of the form \$2^n-1,\:n>1\$ can be computed recursively with:

$$\begin{cases} a(0)=3\\a(n)=2\times a(n-1)+1\end{cases}$$

Hence the golfed recurrence formula: k-=~k.

Commented

n => {         // n = input
  for(         // outer loop:
    k = 1;     //   start with k = 1
    n;         //   stop when n = 0
               //   after each inner loop,
    n -= d < 2 //   decrement n if d = 1 (i.e. k is prime)
  )            //
    for(       //   inner loop:
      d =      //     update k to the next number of the form 2**N - 1
      k -= ~k; //     and initialize the divisor d to the same value
      k % --d; //     decrement d until it divides k
    );         //
  return k     // k is the n-th Mersenne prime: return it
}              //

Answer 2

Vyxal G, 7 bytes

Þ∞E‹~æẎ

Try it Online!

7 bytes flagless (change Ẏ to i) if 0-indexing is allowed.

But how?

Þ∞E‹~æẎ
Þ∞      # all positive integers
  E‹    # as the power of 2 minus 1 (basically, all numbers that are of the form 2^m -  1)
    ~æ  # with only primes kept
      Ẏ # take the first (input) items
# The -G flag outputs the biggest of the final list

Answer 3

Factor + math.primes.lucas-lehmer, 48 bytes

[ 1 lfrom [ lucas-lehmer ] lfilter lnth 2^ 1 - ]

Try it online!

0-indexed.

• 1 lfrom A lazy list of the natural numbers
• [ ... ] lfilter Select the ones that...
• lucas-lehmer ...are Mersenne numbers
• lnth Take the nth one
• 2^ 1 - Turn a Mersenne number into a Mersenne prime

Answer 4

Python 2, 56 bytes

f=lambda k,n=1,p=1:k and f(k-(p%n>n&n+1),n+1,p*n*n)or~-n

Try it online!

Uses the Wilson's Theorem prime generator, which could be implemented like this to find the k'th prime:

f=lambda k,n=1,p=1:k and f(k-p%n,n+1,p*n*n)or~-n

Try it online!

But, modifies it to count only numbers of the form \$2^a-1\$ which are tested for as n&n+1==0. This is combined with the primality check as p%n>n&n+1.

Because this method recurses through all potential primes whether or not they have form \$2^a-1\$, it already exceeds the default maximum recursion depth for inputs of 5 and above.

Python 2, 65 bytes

f=lambda k,n=3:k and f(k-all(n%d for d in range(2,n)),n-~n)or n/2

Try it online!

Recurses through numbers of the \$2^a-1\$ by repeatedly applying n->2*n+1, using trial division to test for primality.

Answer 5

Jelly, 7 bytes

&‘<Ẓø#Ṫ

Try it online!

     #     Count up the first n matches
      Ṫ    then take the last
    ø      starting from 0:
&          Is the candidate bitwise AND
 ‘         itself + 1
  <        less than
   Ẓ       whether or not it's prime?

Answer 6

Prolog (SWI), 85 bytes

Y+X:-X mod Y<1->Y<X;Y+1+X.
Q-N-R:-2+Q,Q- \Q-N-R;N>1,Q- \Q-(N-1)-R;R is Q.
W-R:-3-W-R.

Try it online!

-4 bytes thanks to Jo King

Answer 7

C (gcc), ⁶³ 51 bytes

d;k;f(n){for(k=1;n;n-=d<2)for(d=k-=~k;k%--d;);n=k;}

Try it online!

A port of Arnauld's JavaScript answer.
Saved a whopping 13 bytes thanks to Steffan!!!

Inputs positive integer \$n\$.
Returns the 1-based \$n^{\text{th}}\$ Mersenne prime.

Answer 8

Python, 57 bytes

a=1
while 1:a-=~a;0in(a%d for d in range(2,a))or print(a)

Attempt This Online!

a-=~a taken from Arnauld's JS answer

Answer 9

Wolfram Language (Mathematica), 28 bytes

2^MersennePrimeExponent@#-1&

Try it online!

Answer 10

Husk, 7 bytes

!fṗm←İ2

Try it online!

!fṗm←İ2
   m    # map over
     İ2 # powers of 2
    ←   # decrementing each one
 f      # then filter to keep only
  ṗ     # primes
!       # and get the input-th one.

Answer 11

Brachylog, 14 bytes

;2{;X≜^-₁ṗ}ᶠ⁽t

Try it online!

Worth noting it started with ∧{≜;2↔^-₁ṗ}ᶠ↖?t.

;2{       }ᶠ⁽     Find the first n possible outputs given 2 from:
   ;X             pair the 2 with an unbound variable,
     ≜            label the variable to an integer,
      ^           raise the 2 to that power,
       -₁         subtract 1,
         ṗ        and fail if not prime.
             t    Yield only the last of the results.

Answer 12

05AB1E, 5 bytes

∞o<ʒp

Outputs the infinite sequence.

Try it online.

Outputting the 1-based \$n^{th}\$ value like the example in the challenge description, would be 8 bytes in the legacy version of 05AB1E instead:

µNbSPNp*

Try it online.

Explanation:

∞      # Push an infinite list of positive integers: [1,2,3,...]
 o     # Take 2 to the power each: [2,4,8,...
  <    # Decrease each by 1: [1,3,7,...]
   ʒ   # Filter this list by:
    p  #  Only keep the prime numbers
       # (after which the result is output implicitly)

µ      # Continue looping while `¾` is not equal to the (implicit) input-integer:
       # (counter variable `¾` is 0 by default)
 N     #  Push the loop-index
  b    #  Convert it to a binary string
   S   #  Convert it to a list of digits
    P  #  Check if all bits are 1 by taking the product
 N     #  Push the loop-index again
  p    #  Check whether it's a prime number
     * #  Check if both are truthy
       #  (if they are: implicitly increase `¾` by 1)
       # (after which the last index `N` is output implicitly as result)

Answer 13

Python 3, ^{116 99 88} 85 bytes

def f(n,i=1,j=0):
 while j!=n:i+=1;m=2**i-1;j+=all(m%k for k in range(2,m))
 print(m)

Try it online!

• (-24 thanks to Jo King)
• (-4 thanks to pxeger)

Python+, ⁷⁸ 73 bytes

n=int(§())
i=1
j=0
€j!=n
 i+=1;m=2**i-1;j+=all(m%k£k:range(2,m))
$(m)

• (-1 thanks to pxeger)
• (-4 thanks to Jo King)

Answer 14

Retina, 38 bytes

\d+
_
$
_$`
"$+"}/^(__+)\1+$/+`$
_$`
_

Try it online! No test suite due to the program's use of history. Explanation:

\d+
_

On the first pass through the loop, replace the input with 1 in unary.

$
_$`

Double and increment the value.

/^(__+)\1+$/+`

While the value is composite...

$
_$`

... double and increment the value.

"$+"}

Repeat the above n times.

_

Convert to decimal.

Answer 15

Charcoal, 26 bytes

Ｎθ≔¹ηＷθ«≔⊕⊗ηη≧⁻﹪±Π…¹ηηθ»Ｉη

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input n.

≔¹η

Start with 1.

Ｗθ«

Repeat until n=0.

≔⊕⊗ηη

Double and increment the value.

≧⁻﹪±Π…¹ηηθ

If the value is prime then decrement n. For decremented powers of 2, (n-1)!%-n is either 0 for composite or -1 for prime. (In fact, (n-1)!²%n is 0 for any positive non-prime and 1 for any prime.)

»Ｉη

Output the final value.

Answer 16

Ruby, 52 bytes

->n{r=1;1until(2...r+=r+1).all?{|x|r%x>0}&&1>n-=1;r}

Try it online!

Answer 17

Japt, 14 bytes

Èõ!²mÉ øX*j}iU

Try it

Answer 18

Fig, \$8\log_{256}(96)\approx\$ 6.585 bytes

F@p{^2mC

Try it online!

Outputs an infinite list of Mersenne primes.

F@p{^2mC
      mC # Infinite list of counting numbers
    ^2   # 2^x
   {     # Decrement
F@       # Filter for...
  p      # Primality