12
\$\begingroup\$

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

For example:

  • 7 is a Mersenne Prime because it is 23-1
  • 11 is not a Mersenne Prime because it cannot be written as 2m-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 nth 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 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 , all languages are accepted, and the shortest answer wins!

\$\endgroup\$
12
  • 1
    \$\begingroup\$ Please consider relaxing the output format. As it stands, the challenge consists of finding the prime (interesting part) and formatting the output (uninteresting) \$\endgroup\$
    – Luis Mendo
    Sep 3, 2022 at 9:59
  • \$\begingroup\$ @LuisMendo - done. Is that better? \$\endgroup\$
    – The Thonnu
    Sep 3, 2022 at 10:00
  • 1
    \$\begingroup\$ Closely related \$\endgroup\$
    – Arnauld
    Sep 3, 2022 at 10:03
  • 2
    \$\begingroup\$ @TheThonnu We often post "related" links in the comments of challenges; they're aren't accusations of being a duplicate, but are just there to help navigation between related questions. \$\endgroup\$
    – pxeger
    Sep 3, 2022 at 14:21
  • 7
    \$\begingroup\$ Hey, nice question! As this stands, it would be a perfect fit as a sequence challenge. This allows the output format to be a bit more flexible, allowing the answers to focus more on the challenge, rather than the output format. \$\endgroup\$
    – Seggan
    Sep 3, 2022 at 14:21

18 Answers 18

5
\$\begingroup\$

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
}              //
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 48 bytes. \$\endgroup\$
    – Steffan
    Sep 4, 2022 at 1:21
4
\$\begingroup\$

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

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

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Now that OP has added the sequence tag, you can output infinitely for 45: Try it online! \$\endgroup\$
    – pxeger
    Sep 4, 2022 at 13:58
3
\$\begingroup\$

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?
\$\endgroup\$
3
\$\begingroup\$

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

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

C (gcc), 63 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.

\$\endgroup\$
2
  • \$\begingroup\$ 53 bytes by doing the same thing as Arnauld's JS answer (sorry lol) \$\endgroup\$
    – Steffan
    Sep 4, 2022 at 1:18
  • \$\begingroup\$ @Steffan Arnauld's wizardry tops my feeble efforts yet again! lol Thanks! :D \$\endgroup\$
    – Noodle9
    Sep 4, 2022 at 12:50
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 28 bytes

2^MersennePrimeExponent@#-1&

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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

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

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)
\$\endgroup\$
2
\$\begingroup\$

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+, 78 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)
\$\endgroup\$
8
  • \$\begingroup\$ You can combine the i+=1 j+=all((2**i-1)%k for k in range(2,2**i-1)) lines into one, saving 3 bytes: Try it online! \$\endgroup\$
    – pxeger
    Sep 3, 2022 at 14:30
  • \$\begingroup\$ also, assigning 2**i-1 to a variable would save six bytes \$\endgroup\$
    – Jo King
    Sep 3, 2022 at 14:31
  • \$\begingroup\$ Thanks for the suggestions, updated \$\endgroup\$
    – The Thonnu
    Sep 3, 2022 at 15:06
  • \$\begingroup\$ the python+ code is 73 bytes in UTF-8. does it have a custom codepage? I can't find it \$\endgroup\$
    – Steffan
    Sep 3, 2022 at 18:00
  • 1
    \$\begingroup\$ It is forbidden to add features to a pre-existing language, after the challenge was posted: (commit from 1hr ago) \$\endgroup\$
    – Razetime
    Sep 5, 2022 at 8:46
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 26 bytes

Nθ≔¹ηWθ«≔⊕⊗ηη≧⁻﹪±Π…¹ηηθ»Iη

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

Nθ

Input n.

≔¹η

Start with 1.

Wθ«

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.)

»Iη

Output the final value.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 52 bytes

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

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ r+=r+1 can be r-=~r for -1 \$\endgroup\$
    – Steffan
    Sep 4, 2022 at 1:22
  • \$\begingroup\$ {|x|r%x>0} =>{r%_1>0} \$\endgroup\$
    – TKirishima
    Sep 29, 2022 at 21:28
1
\$\begingroup\$

Japt, 14 bytes

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

Try it

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

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
\$\endgroup\$
3
  • \$\begingroup\$ Thanks for your answer. Can you please explain how you got to that bytecount? I'm assuming this means there are 96 characters in Fig. Is there a page that lists the characters (like in other languages like 05AB1E)? \$\endgroup\$
    – The Thonnu
    Sep 28, 2022 at 17:37
  • \$\begingroup\$ @TheThonnu yes, Fig uses all the printable ASCII characters (barring the tab) for its codepage. If you were wondering how I got an irrational byte count, well, its allowed by site rules now. \$\endgroup\$
    – Seggan
    Sep 28, 2022 at 17:44
  • \$\begingroup\$ Yes, I know it's allowed. I was just wondering where the codepage was. Thanks for clarifying. \$\endgroup\$
    – The Thonnu
    Sep 28, 2022 at 18:01

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.