Un número es un Mersenne Prime si es primo y puede escribirse en la forma 2 n -1 , donde n es un número entero positivo.
Su tarea es, dado cualquier número entero positivo, determinar si es o no un primo de Mersenne. Puede enviar una función que devuelve un valor verdadero / falso o un programa completo que realiza IO.
Reglas:
- Como se trata de código de golf , debe intentar hacerlo en el menor recuento de bytes posible. Las construcciones están permitidas.
- Se aplican las lagunas de golf estándar: no puede leer los primos de Mersenne de archivos externos ni codificarlos en su programa.
- Su programa debería funcionar para valores dentro del tamaño entero estándar de su idioma.
Casos de prueba
Como referencia, puede encontrar una lista de los Mimesenne Primes (conocidos) aquí . Algunos casos de prueba útiles son:
2 -> False
1 -> False
20 -> False
51 -> False
63 -> False
3 -> True
31 -> True
8191 -> True
¡Feliz Navidad a todos! Que tengas unas buenas vacaciones, lo que celebres :)
2^n-1
n
siempre es primo, pero sabiendo que no cambia nada, la definición sigue siendo correcta.Respuestas:
Jalea , 5 bytes
Pruébalo en línea!
Cómo funciona
fuente
05AB1E , 5 bytes
Un número positivo en la forma 2 n - 1 en binario solo consta de 1 .
Código:
Explicación:
Utiliza la codificación CP-1252 . Pruébalo en línea! o Verificar todos los casos de prueba .
fuente
Python , 45 bytes
Pruébalo en línea!
Cómo funciona
Los tres términos de la comparación encadenada
Haz lo siguiente:
-~n&n
calcula el AND bit a bit de n + 1 y n . Dado que n consiste únicamente en 1 bits si es un número de Mersenne, el AND bit a bit devolverá 0 si (y solo si) este es el caso.all(n%i for i in range(2,n))
devuelve True si y solo si n mod i no es cero para todos los valores de i en [2,…, n - 1] , es decir, si y solo si n no tiene divisores positivos aparte de 1 y n .En otras palabras, todo devuelve True si y solo si n es un número compuesto, es decir, n es 1 o un primo.
n
Se explica por sí mismo.La comparación encadenada devuelve True si y solo si las comparaciones individuales hacen lo mismo.
Desde todos los retornos ya sea Verdadero / 1 o Falso / 0 ,
-~n&n<all(n%i for i in range(2,n))
sólo se pueden volver Verdadero si-~n&n
los rendimientos de 0 (es decir, si n es un número Mersenne) y todos los retornos verdadera (es decir, si n sea 1 o un primo).La comparación se
all(n%i for i in range(2,n))<n
mantiene siempre que n> 1 , pero dado que todo devuelve True si n = 1 , no se cumple en este caso.fuente
Brachylog , 7 bytes
Pruébalo en línea!
Un programa Brachylog es básicamente una secuencia de restricciones que forman una cadena: la primera restricción está entre la entrada y un desconocido anónimo (llamémosla A para el propósito de esta discusión), la segunda restricción está entre ese desconocido anónimo y un segundo anónimo desconocido (que llamaremos B ), y así sucesivamente. Como tal, el programa se descompone así:
La única forma en que todas estas restricciones pueden satisfacerse simultáneamente es si B es una potencia de 2, es decir, la entrada es una potencia de 2 menos 1, y la entrada también es primo. (Brachylog usa un solucionador de restricciones internamente, por lo que el programa no será tan ineficiente como parece el orden de evaluación; se dará cuenta de que
C
es de la forma[2, Y]
antes de intentar expresarB
como la exponenciación de dos números).Curiosamente,
#p+~^
casi funciona, porque los primos tipo Mersenne solo pueden usar 2 como base en casos no degenerados ( prueba ), pero a) falla para los primos no Mersenne B -1, ya que pueden expresarse como B ¹, y b ) el intérprete de Brachylog existente parece estar confundido (entrando en un bucle infinito, o al menos de larga duración) por un programa que está tan limitado. Por lo tanto, parece poco probable que 7 bytes sean superados en Brachylog.fuente
Mathematica 26 Bytes
See this proof
Works so long as there are no odd perfect numbers, and none are known to exist.
fuente
n(n+1)/2
produces (even) perfect numbers whenevern
is a Mersenne prime (Euclid). It appears to be unknown whether an odd perfect number can have the formn(n+1)/2
, i.e. be a triangular number. All even perfect numbers are triangular where thisn
is a Mersenne prime (Euler).Mathematica,
2926 bytesEdit: Saved 3 bytes thanks to Martin Ender
PrimeQ@#&&IntegerQ@Log2[#+1]&
I suspect this would be faster since the first 42 exponents are hard-coded:
fuente
PrimeQ@#&&1>BitAnd[#,#+1]&
Perl 6, 29 bytes
Try it
Expanded:
since Perl 6 has arbitrarily large Ints, it doesn't pad the front of
.base(2)
with0
s.fuente
Python,
8382797673 bytesPython 2, 71 bytes
This function implements the Lucas–Lehmer primality test, so while it isn't as short as some of the other Python offerings it's much faster at handling huge inputs.
Here's some test code that runs on Python 2 or Python 3.
output
FWIW, here's a slightly more efficient version of
f
that doesn't re-testm
on every loop:fuente
R,
4140 bytesOddly enough the builtin in R
mersenne
takesn
as argument, not2^n-1
.This takes
x
from STDIN, checks if it is prime using thematlab
package and checks if the 2-log ofx+1
is a whole number by taking mod 1 and checking for 'not zero-ness'.Also, if you use the
mersenne
builtin, it ends up being slightly shorter, but feels like cheating:Saved 1 byte thanks to @Billywob
fuente
matlab::isprime
to save one byte. Also you have to use<-
for in-function assignment.log2(x+1)
insteadlog(x+1,2)
.Pyke, 10 bytes
Try it here!
fuente
Actually, 9 bytes
Try it online!
Explanation:
Since every number of the form 2n-1 has all 1's in its binary representation, a Mersenne prime can be identified as a prime number with that quality.
fuente
Jelly, 5 bytes
Alternate approach to @Dennis' existing 5-byte Jelly answer:
Try it online!
How it works:
Since a Mersenne Prime is one less than a power of 2, its binary representation is excusively 1's. The output therefor is 1 for Mersenne primes, and 0 in all other cases .
fuente
Ceylon, 66 bytes
Formatted (and commented):
With cheating (hardcoding the results in the range of Ceylon's Integer), we can get a byte shorter (65):
(It looks like the syntax highlighter misunderstands Ceylon's hex numerals as start-of-comment.)
If an anonymous function is okay, this one is 49 bytes:
fuente
Wolfram Language (Mathematica), 23 bytes
Try it online!
1 is handled correctly because
PrimeQ[BitAnd[1,1+2]*1] == PrimeQ@1 == False
. Otherwise, forBitAnd[#,#+2]#
to be prime, we need that#
is prime andBitAnd[#,#+2] == 1
, which happens when#
is a Mersenne number.fuente
ECMAScript regex,
4231 bytes^(?!(xx+)\1+$)(x(x*)(?=\3$))+x$
Try it online!
Edit: Down to 31 bytes thanks to Neil.
The basic "is a power of 2 minus 1" test is
^(x(x*)(?=\2$))*$
. This works by looping the operation "subtract 1, then divide evenly by 2" until it can be done no further, then asserting that the result is zero. This can be modified to match only numbers ≥1 by changing the last*
to a+
, forcing the loop to iterate at least once. Inserting anx
before the last$
further modifies it to match only numbers ≥3 by asserting that the final result after looping at least once is 1.The related "is a power of 2" test is
^((x+)(?=\2$))*x$
. There is also a shorthand for matching powers of 2 minus 2, discovered by Grimy:^((x+)(?=\2$)x)*$
. All three of these regexes are of the same length.Alternative 31 byte version, by Grimy:
^(?!(xx+)\1+$|((xx)+)(\2x)*$)xx
Try it online!
fuente
x(x+)(?=\3$)
be slightly more efficient?Regex (ECMAScript), 29 bytes
Try it online!
Inspired by Grimy in chat
The regex asserts that the input is greater than 3, and that it is neither of the form:
(xx+)\1+
or((xx)+)(\1x)+
.The first matches composite numbers.
The second matches a number that is 1 less than a multiple of some odd number greater than 2.
The first will not match prime numbers, or2n−1 , or numbers that are 1 less than an odd prime.
0
or1
.The second will not match numbers of the form
Since 2 is the only prime that is 1 less than an odd prime, the negative lookahead, together with the assertion that the input is greater than 3, will match only mersenne primes.
fuente
Ruby, 47 bytes
fuente
Julia, 26 bytes
fuente
Python, 65 bytes
Outputs via Exit Code. Recursion Error for False. No error for True.
How it works
Since
2^n-1
in binary is made entirely from 1's, the next2^n-1
number can be generated bynumber|number+1
.This function uses this by recursively going through each
2^n-1
number checking to see if it's a prime number and eqaul to the input. If the number is not a mersenne prime, python will eventually throw an error as the maximum recursion depth would have been exceeded.fuente
<0
~>0>
.Pushy, 7 bytes
Try it online!
This takes advantage of the fact that mersenne numbers have only ones in their binary representation:
The stack product will only be
1
if the number has no zeroes in its binary representation, and its primality isTrue
.fuente
Pyth, 8 bytes
Verify all the test cases.
Pyth, 8 bytes
Verify all the test cases.
How?
Code Breakdown #1
How does that work?
A number of the form 2n - 1 always contains 1 only when written in binary. Hence, we test if all its binary digits are 1 and if it is prime.
Code Breakdown #2
How does that work?
This tests if the input + 1 is a power of two (i.e. if it is a Mersenne number), and then performs the primality test. In Python,
bool
is a subclass ofint
, so truthy is treated as 1 and falsy is treated as 0. To avoid checking explicitly that one is 0 and the other is 1, we compare their values using<
(since we only have 1 such case).fuente
Java 8,
535249 bytesBug-fixed and golfed by 4 bytes thanks to @Nevay.
Explanation:
Try it here.
fuente
true
for every prime >2, not only for Mersenne primes, 56 bytes:n->{for(int i=2;i<n;n&=-n%i++>>-1);return(n&n+1)<1&n>2;}
n->{int i=1;for(;++i<n&n%i>0;);return(n&n+1|i^n)<1;}
n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}
Python 3, 68 bytes
Try it here
Python 2, 63 bytes
Try it here
Thanks for suggestion Jonathan
Open to any suggestions for reducing the bytecount.
fuente
1 and
~>1and
.Japt, 6 bytes
Run it or Run all test cases
fuente
©
with bitwise&
for consistent output, if you want.Python, 93 Bytes
This code would work in both Python 2 and Python 3 so I have not specified a version.
fuente
Racket 76 bytes
Ungolfed:
Testing:
Output:
fuente
PHP, 53 bytes
takes command line argument; prints
1
for Mersenne prime, empty string else. Run with-r
.breakdown
fuente
C, 94 bytes
Returns 1 if the number is a Mersenne Prime, 0 otherwise.
fuente
~x+g(2,n)
instead ofx^g(2,n)-1
Scala, 59 Bytes
This function requires the input to be a
BigInt
. You can easily convert a string "162259276829213363391578010288127" (2**107-1 is a Mersenne prime) intoBigInt
by doingBigInt("162259276829213363391578010288127")
. It might go wrong as the name ofisProbablePrime()
method suggests. But the probability is not more than0.5^(t.bigLength)*9
.Standalone script version is 72 bytes long.
Assume we save it as "t.scala", then then program can be run as
fuente
Probable
fromisProbablePrime
if Scala has anisPrime
function.Perl 5, 53 bytes
52 bytes of code + 1 for
-p
Try it online!
fuente
-p
is classified as another programming language, and hence doesn't count in your bytecount.