Est-ce un Prime Mersenne?

35

Un nombre est un nombre premier de Mersenne s'il est à la fois premier et qu'il peut être écrit sous la forme 2 n -1 , où n est un entier positif.

Votre tâche consiste à déterminer, en fonction de tout nombre entier positif, s'il s'agit ou non d'un nombre premier de Mersenne. Vous pouvez soumettre soit une fonction qui retourne une valeur vérité / fausseté, soit un programme complet qui exécute des entrées / sorties.

Règles:

  • Comme il s'agit de , vous devriez viser le plus petit nombre d'octets possible. Les Builtins sont autorisés.
  • Des failles de golf standard s’appliquent - vous ne pouvez pas lire les nombres premiers Mersenne à partir de fichiers externes, ni les coder en dur dans votre programme.
  • Votre programme devrait fonctionner pour des valeurs comprises dans la taille entière standard de votre langue.

Cas de test

Pour référence, une liste des Primes de Mersenne (connues) peut être trouvée ici . Certains cas de test pratiques sont:

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

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

Joyeux Noël tout le monde! Passez de bonnes vacances, peu importe ce que vous célébrez :)

FlipTack
la source
2
Si je pouvais, je voterais cela comme une dupe du défi « isprime» , car cela n’apporte rien de nouveau.
mardi
9
@flawr Ils sont très similaires - mais pour ce défi, il y a moins de chance d'être intégré et il y a beaucoup d'approches intéressantes pour déterminer si un nombre est représentable2^n-1
FlipTack
1
Je crois que la définition d'un nombre de Mersenne exige également que n soit premier (une condition qui s'est également révélée nécessaire, mais pas suffisante, pour que (2 ^ n) -1 soit premier.)
SuperJedi224
4
@ SuperJedi224 nest toujours primordial, mais sachant que cela ne change rien, la définition est toujours correcte.
FlipTack
2
@TheBitByte Oui - si vous implémentez un algorithme basé sur les probabilités qui ne fonctionne pas 100% du temps, vous pouvez toujours le poster, mais ce ne sera pas concurrentiel :)
FlipTack

Réponses:

19

Gelée , 5 octets

&‘<ÆP

Essayez-le en ligne!

Comment ça marche

&‘<ÆP  Main link. Argument: x

 ‘     Yield x+1.
&      Take the bitwise AND of x and x+1.
       This yields 0 iff x is a Mersenne number, i.e., iff x+1 is a power of 2.
   ÆP  Yield 1 if x is a prime, 0 if not.
  <    Compare the results to both sides,
       This yields 1 iff x is both a Mersenne number and a prime.
Dennis
la source
Même problème que la réponse d'Adnan. Voir mothereff.in/byte-counter
Kelly Lowder le
8
@KellyLowder Ce compteur d'octets utilise UTF-8. Jelly et 05AB1E utilisent tous deux des jeux de caractères à un octet.
Dennis
24

05AB1E , 5 octets

Un nombre positif sous la forme 2 n - 1 en binaire est composé uniquement de 1 .

Code:

b`¹pP

Explication:

b`      # Push each digit of the binary representation of the number onto the stack
  ¹p    # Check if the input is prime
    P   # Take the product of all these digits

Utilise le codage CP-1252 . Essayez-le en ligne! ou Vérifiez tous les cas de test .

Adnan
la source
5
Je me demandais combien de temps avant que quelqu'un utilise ce truc :)
FlipTack
¹ prend 2 octets, donc c'est 6.
Kelly Lowder
5
@KellyLowder En UTF-8, oui. Cependant, 05AB1E utilise le codage CP-1252 plutôt que le codage UTF-8.
Adnan
10

Python , 45 octets

lambda n:-~n&n<all(n%i for i in range(2,n))<n

Essayez-le en ligne!

Comment ça marche

Les trois termes de la comparaison chaînée

-~n&n<all(n%i for i in range(2,n))<n

faire ce qui suit:

  • -~n&ncalcule le bit AND ET de n + 1 et n . Puisque n est constitué uniquement de 1 bits s’il s’agit d’un nombre de Mersenne, l’ET au niveau du bit ET retournera 0 si (et seulement si) c’est le cas.

  • all(n%i for i in range(2,n))renvoie True si et seulement si n mod i est non nul pour toutes les valeurs de i dans [2,…, n - 1] , c'est-à-dire si et seulement si n n'a pas de diviseurs positifs à l'exception de 1 et n .

    En d’autres termes, all renvoie True si et seulement si n est un nombre composé, c’est-à-dire que n est 1 ou un nombre premier.

  • n est explicite.

La comparaison chaînée renvoie True si et seulement si les comparaisons individuelles font la même chose.

  • Étant donné que tous les retours soit vrai / 1 ou Faux / 0 , -~n&n<all(n%i for i in range(2,n))ne peut retourner vrai si les -~n&nrendements 0 ( par exemple, si n est un nombre Mersenne) et tous les retours Vrai ( par exemple, si n soit 1 ou prime).

  • La comparaison all(n%i for i in range(2,n))<nest valable chaque fois que n> 1 , mais puisque tout retourne True si n = 1 , elle ne l’est pas dans ce cas.

Dennis
la source
1
Wow, c'est incroyable :)
ABcDexter
8

Brachylog , 7 octets

#p+~^h2

Essayez-le en ligne!

Un programme Brachylog est fondamentalement une suite de contraintes qui forment une chaîne: la première contrainte se situe entre l’entrée et un inconnu anonyme (appelons-le A pour les besoins de cette discussion), la seconde contrainte se situe entre cet inconnu anonyme et un deuxième anonyme. inconnu (que nous appellerons B ), et ainsi de suite. En tant que tel, le programme se décompose ainsi:

#p      Input = A, and is prime
+       B = A + 1
~^      B = X to the power Y, C = the list [X, Y]
h       D = the head of list C (= X)
2       D = 2

Le seul moyen de satisfaire simultanément toutes ces contraintes est si B est une puissance de 2, c'est-à-dire que l'entrée est une puissance de 2 moins 1 et que l'entrée est également première. (Brachylog utilise un résolveur de contraintes en interne, de sorte que le programme ne soit pas aussi inefficace que l'ordre d'évaluation; il sera conscient Cde sa forme [2, Y]avant d'essayer de l'exprimer Bsous la forme d'une exponentiation de deux nombres.)

Fait intéressant, #p+~^ presque fonctionne, parce que Mersenne comme les nombres premiers ne peut utiliser 2 comme base dans les cas non dégénéré ( preuve ), mais a) elle échoue pour les nombres premiers non-Mersenne B -1 car ils peuvent être exprimés en B ¹, et b ) L’interprète Brachylog existant semble être confondu (entrer dans une boucle infinie, ou du moins de longue durée) par un programme aussi peu contraint. Il est donc peu probable que 7 octets soient battus dans Brachylog.


la source
Je suis impressionné! Quant au problème de la boucle infinie, il est dû à la surcharge de prédicats. Avec le recul, je pense que je n’aurais pas dû implémenter de surcharge pour les prédicats. Cela provoque aussi des problèmes dans des choses comme findall.
Fataliser
7

Mathematica 26 octets

PerfectNumberQ[# (#+1)/2]&

Voir cette preuve

Fonctionne tant qu'il n'y a pas de nombres impairs parfaits, et qu'aucun ne soit connu pour exister.

Kelly Lowder
la source
Donc, votre réponse n'est pas prouvée valide?
Jonathan Frech
Je ne pense pas que l'espace est nécessaire.
Jonathan Frech
@JonathanFrech La formule n(n+1)/2produit des nombres (pairs) parfaits dès qu'il ns'agit d'un nombre premier de Mersenne (Euclid). Il semble qu'on ignore si un nombre parfait impair peut avoir la forme n(n+1)/2, c'est-à-dire être un nombre triangulaire. Tous les nombres même parfaits sont triangulaires lorsqu'il ns'agit d'un nombre premier de Mersenne (Euler).
Jeppe Stig Nielsen
1
@JeppeStigNielsen La question est de savoir s'il est valide d'utiliser un fait inconnu pour baser sa solution.
Jonathan Frech
7

Mathematica, 29 à 26 octets

Edit: 3 octets sauvés grâce à Martin Ender

PrimeQ@#&&IntegerQ@Log2[#+1]&

PrimeQ@#&&1>BitAnd[#,#+1]&

Je pense que cela serait plus rapide puisque les 42 premiers exposants sont codés en dur:

MersennePrimeExponentQ@Log2[#+1]&
ngenisis
la source
6
PrimeQ@#&&1>BitAnd[#,#+1]&
Martin Ender
5

Perl 6 , 29 octets

{.base(2)~~/^1*$/&&.is-prime}

L'essayer

Étendu:

{             # bare block lambda with implicit parameter 「$_」

  .base(2)    # is its binary representation ( implicit method call on 「$_」 )
   ~~
  /^ 1* $/    # made entirely of 「1」s

  &&          # and

  .is-prime   # is it prime

}

Puisque Perl 6 a des tailles de fichier arbitrairement grandes, il ne couvre pas le début .base(2)avec 0s.

Brad Gilbert b2gills
la source
5

Python, 83 82 79 76 73 octets

def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

Python 2, 71 octets

def f(m):
 s,n=(m!=3)*4,m/4
 while-~m&m<n:s,n=(s*s-2)%m,n/2
 return s<1

Cette fonction implémente le test de primalité Lucas – Lehmer . Ainsi, bien que ce ne soit pas aussi court que certaines autres offres Python, il est beaucoup plus rapide à gérer des entrées énormes.


Voici un code de test qui s'exécute sur Python 2 ou Python 3.

from __future__ import print_function

def primes(n):
    """ Return a list of primes < n """
    # From http://stackoverflow.com/a/3035188/4014959
    sieve = [True] * (n//2)
    for i in range(3, int(n**0.5) + 1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    return [2] + [2*i + 1 for i in range(1, n//2) if sieve[i]]

def lucas_lehmer_old(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = (s * s - 2) % m
    return s == 0 and m or 0

# much faster
def lucas_lehmer(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = s * s - 2
        while s > m:
            s = (s & m) + (s >> p)
    return s == 0 or s == m and m or 0

def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

# Make a list of some Mersenne primes
a = [3]
for p in primes(608):
    m = lucas_lehmer(p)
    if m:
        print(p, m)
        a.append(m)
print()

# Test that `f` works on all the numbers in `a`
print(all(map(f, a))) 

# Test `f` on numbers that may not be Mersenne primes
for i in range(1, 525000):
    u = f(i)
    v = i in a
    if u or v:
        print(i, u, v)
    if u != v:
        print('Error:', i, u, v)

sortie

3 7
5 31
7 127
13 8191
17 131071
19 524287
31 2147483647
61 2305843009213693951
89 618970019642690137449562111
107 162259276829213363391578010288127
127 170141183460469231731687303715884105727
521 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
607 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

True
3 True True
7 True True
31 True True
127 True True
8191 True True
131071 True True
524287 True True

FWIW, voici une version légèrement plus efficace de fce test, qui ne re-teste pas mà chaque boucle:

def f(m):
 s,n=m!=3and 4,m>>2
 if-~m&m<1:
  while n:
   s=(s*s-2)%m
   n>>=1
 return s<1
PM 2Ring
la source
Vous pouvez écrire la boucle while sur une seule ligne (pas de nouvelle ligne ni de retrait)
indent
@ FlipTack D'oh! Je vous remercie! Je ne sais vraiment pas pourquoi j'ai manqué ça ... Et je viens de remarquer que je peux réduire encore quelques octets en revenant à Python 2.
PM 2Ring le
4

R, 41 40 octets

matlab::isprime(x<-scan())&!log2(x+1)%%1

Curieusement, le langage intégré dans R mersenneprend ncomme argument, pas 2^n-1.

Cela prend xSTDIN, vérifie s'il utilise correctement le matlabpaquet et vérifie si le 2-log de x+1est un nombre entier en prenant le mod 1 et en vérifiant que le résultat n'est pas nul.

De plus, si vous utilisez la commande mersenneintégrée, celle-ci finit par être légèrement plus courte, mais donne l'impression de tricher:

numbers::mersenne(log2(scan()+1))

Enregistré 1 octet grâce à @Billywob

JAD
la source
Posté une réponse similaire mais je l'ai supprimé maintenant. Puis-je suggérer matlab::isprimede sauver un octet. Aussi, vous devez utiliser <-pour l'affectation en fonction.
Billywob
@billywob Vient de remarquer que matlab :: isprime avait un octet de moins. (obtenu un pic de 1 seconde à votre solution).
JAD
Vous pouvez également utiliser à la log2(x+1)place log(x+1,2).
Billywob
2

Pyke, 10 octets

_PQb2+}\1q

Essayez-le ici!

_P         -    is_prime(input)
     +     -   ^ + V
  Qb2      -    base_2(input)
      }    -  uniquify(^)
       \1q - ^ == "1"
Bleu
la source
2

En fait , 9 octets

;├╔'1=@p*

Essayez-le en ligne!

Explication:

Comme chaque nombre de la forme 2 n -1 a tous les 1 dans sa représentation binaire, un nombre premier de Mersenne peut être identifié comme un nombre premier ayant cette qualité.

;├╔'1=@p*
 ├╔'1=     only unique binary digit is 1
        *  and
;     @p   is prime
Mego
la source
2

Gelée, 5 octets

Autre approche de la réponse Jelly à 5 octets existante de @Dennis:

B;ÆPP

Essayez-le en ligne!

Comment ça marche:

B      Returns the binary representation of the input as a list [1, 0, 1, 1, ...]
 ;     And attach to this list 
  ÆP   a 1 if the input is a prime, 0 otherwise
    P  Calculates the product of this list of 1's and 0's

Etant donné qu'un Mersenne Prime correspond à un moins qu'une puissance de 2, sa représentation binaire correspond à 1. La sortie correspondante est 1 pour les nombres premiers de Mersenne et 0 dans tous les autres cas.

Steenbergh
la source
2

Ceylan, 66 octets

Boolean m(Integer c)=>c>2&&c.and(c+1)<1&&!(2:c-2).any((d)=>c%d<1);

Formaté (et commenté):

// Check whether a (positive integer) number is a mersenne prime number.
//
// Question:  http://codegolf.stackexchange.com/q/104508/2338
// My Answer: http://codegolf.stackexchange.com/a/104805/2338

Boolean m(Integer c) =>
        // check whether c+1 is a power of two
        c.and(c+1)<1 &&
        // the standard primality check by trial division
         !(2 : c-2).any((d) => c%d < 1) &&
        // we need to exclude 1, which is unfortunately
        // matched by both criteria above, but is no prime.
        c>1;

Avec la triche (coder en dur les résultats dans la plage de Integer de Ceylan), nous pouvons obtenir un octet plus court (65):

Boolean h(Integer c) =>
        c.and(c+1)<1 && #20000000800a20ac.and(c+1)>0;

(Il semble que le surligneur de syntaxe comprenne mal les chiffres hexadécimaux de Ceylan en début de commentaire.)

Si une fonction anonyme est correcte, celle-ci a 49 octets:

[2,3,5,7,13,17,19,31,61].map((p)=>2^p-1).contains
Paŭlo Ebermann
la source
2

Wolfram Language (Mathematica) , 23 octets

PrimeQ[BitAnd[#,#+2]#]&

Essayez-le en ligne!

1 est traité correctement car PrimeQ[BitAnd[1,1+2]*1] == PrimeQ@1 == False. Sinon, pour BitAnd[#,#+2]#être premier, nous avons besoin de ce qui #est premier et BitAnd[#,#+2] == 1, ce qui arrive quand #est un nombre de Mersenne.

lirtosiast
la source
Bien fait! En tant que personne qui n’a jamais utilisé Mathematica, votre code TIO était confus au début. J'ai ensuite réalisé que vous compariez votre fonction au précédent détenteur du record ex æquo de ngenisis . Je pense qu'il serait préférable d' afficher le résultat de la fonction et peut-être un deuxième lien le comparant à l'autre solution.
Deadcode
2

Regex ECMAScript, 42 à 31 octets

^(?!(xx+)\1+$)(x(x*)(?=\3$))+x$

^
(?!(xx+)\1+$)      # Assert that N is prime or 0 or 1.
(x(x*)(?=\3$))+x$  # Assert that N is a power of 2 minus 1 and is >= 3.
                   # The >=3 part of this prevents the match of 0 and 1.

Essayez-le en ligne!

Edit: jusqu'à 31 octets grâce à Neil.

La base "est une puissance de 2 moins 1" test est ^(x(x*)(?=\2$))*$. Cela fonctionne en boucle avec l'opération "soustraire 1, puis diviser de manière égale par 2" jusqu'à ce que l'opération ne soit plus possible, puis en affirmant que le résultat est nul. Cela peut être modifié pour ne faire correspondre que les nombres ≥1 en remplaçant le dernier *par un +, forçant la boucle à itérer au moins une fois. Insertion d'un xavant le dernier$ le modifie pour qu'il ne corresponde qu'aux nombres ≥3 en affirmant que le résultat final après avoir bouclé au moins une fois est 1.

Le test connexe "est une puissance de 2" est ^((x+)(?=\2$))*x$. Il y a également un raccourci pour les pouvoirs correspondant de 2 moins 2, découverts par Grimy : ^((x+)(?=\2$)x)*$. Ces trois regex sont de la même longueur.

Version alternative 31 octets, par Grimy :

^(?!(xx+)\1+$|((xx)+)(\2x)*$)xx

Essayez-le en ligne!

# Match Mersenne primes in the domain ^x*$
^                   # N = input number
(?!                 # "(?!p|q)" is equivalent to "(?!p)(?!q)"; evaluate the
                    # logical AND of the following negative lookaheads:
    (xx+)\1+$       # Assert that N is prime or 0 or 1
|
    ((xx)+)(\2x)*$  # Assert that N is a power of 2 minus 1; this is based
                    # on "(?!(x(xx)+)\1*$)" which matches powers of 2.
)
xx                  # Assert that N >= 2, to prevent the unwanted match of
                    # 0 and 1 by both of the negative lookahead statements.
Deadcode
la source
1
Économisez 11 octets en recherchant directement un numéro 1 inférieur à une puissance de 2: essayez-le en ligne!
Neil
@Neil Merci beaucoup! J'aurais aimé y penser, mais ensuite, c'est exactement le genre de chose que je voulais arriver!
Deadcode
1
En fait, y penser serait x(x+)(?=\3$)légèrement plus efficace?
Neil
Oui, vous avez absolument raison.
Deadcode
2

Regex (ECMAScript), 29 octets

^(?!(xx+|(x(x))+)(\1\3)+$)xxx

Essayez-le en ligne!

Inspiré par Grimy in chat

La regex affirme que l'entrée est supérieure à 3 et qu'elle n'est ni de la forme, (xx+)\1+ni((xx)+)(\1x)+ .

Le premier correspond aux nombres composés.
La seconde correspond à un nombre égal à 1 de moins qu’un multiple d’un nombre impair supérieur à 2.

Le premier ne correspondra pas aux nombres premiers, ou 0ou 1.
La seconde ne correspondra pas aux numéros du formulaire2n-1, ou des nombres inférieurs de 1 à un nombre impair.

Étant donné que 2 est le seul nombre premier inférieur de 1 à un nombre impair, le signe d'anticipation négatif, ainsi que l'affirmation que l'entrée est supérieure à 3, correspondra uniquement aux nombres premiers de mersenne.

H.PWiz
la source
1

Ruby, 47 octets

->b{!("%b"%(b/2)=~/0/||(2...b).find{|a|b%a<1})}
GB
la source
1

Julia, 26 octets

n->isprime(n)&&ispow2(n+1)
Alephalpha
la source
1

Python, 65 octets

f=lambda n,i=3:(n^i)-all(n%i for i in range(2,n))<0 or f(n,-~i|i)

Sorties via le code de sortie. Erreur de récursion pour False. Aucune erreur pour True.

Comment ça marche

Comme 2^n-1en binaire est fait entièrement à partir de 1, le prochain2^n-1 nombre peut être généré parnumber|number+1 .

Cette fonction utilise ceci en 2^n-1vérifiant récursivement chaque nombre pour vérifier s'il s'agit d'un nombre premier et de son eqaul à l'entrée. Si le nombre n'est pas un nombre premier de mersenne, python émettra une erreur car la profondeur de récursivité maximale aurait été dépassée.

Cormac
la source
1
Si je ne me trompe pas, <0~> 0>.
Jonathan Frech
1

Pushy , 7 octets

oBoIpP#

Essayez-le en ligne!

Cela tire parti du fait que les nombres de mersenne n’en ont qu’un dans leur représentation binaire:

oB      \ Pop input, push its binary digits.
  oI    \ Re-push the input
    p   \ Test its primality (0/1)
     P# \ Print the product of the stack

Le produit de pile ne le sera que 1si le nombre n'a pas de zéros dans sa représentation binaire et que sa primalité est True.

FlipTack
la source
1

Pyth , 8 octets

&.AjQ2P_

Vérifiez tous les cas de test.

Pyth , 8 octets

<.&QhQP_

Vérifiez tous les cas de test.


Comment?

Code Breakdown # 1

&.AjQ2P_    Full program with implicit input.

      P_    Is Prime?
   jQ2      Convert the input to binary as a list of digits.
 .A         All the elements are truthy (i.e. all are 1).
&           Logical AND.
            Output implicitly.

Comment ça marche?

Un numéro de la forme 2 n - 1 contient toujours 1 uniquement lorsqu'il est écrit en binaire. Par conséquent, nous testons si tous ses chiffres binaires sont 1 et s'il est premier.

Code Breakdown # 2

<.&QhQP_    Full program with implicit input.

      P_    Is Prime?
    hQ      Input + 1.
 .&Q        Bitwise AND between the input and ^.
<           Is smaller than? I.e. The bitwise AND results in 0 and the primality test results in 1.
            Output implicitly.

Comment ça marche?

Ceci teste si l' entrée + 1 est une puissance de deux (c'est-à-dire s'il s'agit d'un nombre de Mersenne), puis effectue le test de primalité. En Python, boolest une sous-classe de int, de sorte que la vérité est traitée en tant que 1 et la fausseté est traitée en tant que 0 . Pour éviter de vérifier explicitement que l'un est 0 et l'autre 1 , nous comparons leurs valeurs en utilisant <(puisque nous n'avons qu'un seul cas de ce type).

M. Xcoder
la source
1

Java 8, 53 52 49 octets

n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}

Correction de bug et lecture de 4 octets grâce à @Nevay .

Explication:

Essayez ici.

n->{                // Method with integer parameter and boolean return-type
  int i=1;          //  Temp integer `i`, starting at 1
  for(;n%++i>0;);   //  Loop and increase `i` as long as `n` is divisible by `i`
  return(n&n+1|i^n) //  Then return if `n` bitwise-AND `n+1` bitwise-OR `i` bitwise-XOR `n`
          ==0;      //  is exactly 0
}                   // End of method
Kevin Cruijssen
la source
La solution actuelle revient truepour chaque nombre premier> 2, pas seulement pour les nombres premiers de Mersenne, 56 octets:n->{for(int i=2;i<n;n&=-n%i++>>-1);return(n&n+1)<1&n>2;}
Nevay
1
52 octets:n->{int i=1;for(;++i<n&n%i>0;);return(n&n+1|i^n)<1;}
Nevay
@Nevay Merci .. Et vous ne savez pas pourquoi les scénarios de test n'incluaient aucun nombre premier qui ne soit pas un nombre premier de mersenne .. Ajoutez-les moi-même et vous avez effectivement raison.
Kevin Cruijssen
1
49 octets:n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}
Nevay
1

Python 3, 68 octets

a=int(input());print(a&-~a<1and a>1and all(a%b for b in range(2,a)))

Essayez-le ici

Python 2, 63 octets

a=input();print(a&-~a<1)and a>1and all(a%b for b in range(2,a))

Essayez-le ici


Merci pour la suggestion Jonathan


Ouvert à toute suggestion pour réduire le nombre de tiers.

ABcDexter
la source
1
1 and~> 1and.
Jonathan Frech
1

Japt, 6 octets

¢¬×&Uj

Run it or Run all test cases

Oliver
la source
1
Very nice :) You could replace logical © with bitwise & for consistent output, if you want.
Shaggy
0

Python, 93 Bytes

def f(a):
 for b in range(a):
  if(a+1==2**b and not[i for i in range(2,a)if a%i<1]):return 1

This code would work in both Python 2 and Python 3 so I have not specified a version.

sonrad10
la source
0

Racket 76 bytes

(define(g m)(for/or((i m))(= m(-(expt 2 i)1))))(if(and(prime? n)(g n))#t #f)

Ungolfed:

(require math)
(define(f n)
  (define (ispowerminus1 m)
    (for/or ((i m))
      (= m (-(expt 2 i)1))))
  (if (and (prime? n)
           (ispowerminus1 n))
      #t #f))

Testing:

(f 1)
(f 2)
(f 20)
(f 51)
(f 63)
(f 3)
(f 31)
(f 8191)

Output:

#f
#f
#f
#f
#f
#t
#t
#t
rnso
la source
0

PHP, 53 bytes

for($i=$n=$argv[1];--$i&&$n%$i;);echo!($i-1|$n+1&$n);

takes command line argument; prints 1 for Mersenne prime, empty string else. Run with -r.

breakdown

for($i=$n=$argv[1];--$i&&$n%$i;);   // loop $i down from $n-1 until $i divides $n
                        // If $n is prime, loop ends with $i=1. ($n=1 -> $i=0)
echo!($i-1|$n+1&$n);    // If $i!=1, $n is not prime. If ($n+1&$n)>0, $n is not Mersenne.
                        // If either $i-1 or $n+1&$n is truthy, the negation will be false.
Titus
la source
0

C, 94 bytes

g(n,i){return--i?g(2*n,i):n;}n,r;f(x){for(n=r=1;++n<x;)r=x%n?x^g(2,n)-1?r:r|2:r&2;return r>2;}

Returns 1 if the number is a Mersenne Prime, 0 otherwise.

Steadybox
la source
Suggest ~x+g(2,n) instead of x^g(2,n)-1
ceilingcat
0

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
Aria Ax
la source
You can remove the Probable from isProbablePrime if Scala has an isPrime function.
MilkyWay90
0

Perl 5, 53 bytes

52 bytes of code + 1 for -p

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

Try it online!

Xcali
la source
According to meta consensus, the -p is classified as another programming language, and hence doesn't count in your bytecount.
MilkyWay90