Eine Zahl ist eine Mersenne-Primzahl, wenn sie beide Primzahlen ist und in der Form 2 n -1 geschrieben werden kann , wobei n eine positive ganze Zahl ist.
Ihre Aufgabe ist es, bei einer positiven ganzen Zahl zu bestimmen, ob es sich um eine Mersenne-Primzahl handelt oder nicht. Sie können entweder eine Funktion übergeben, die einen Wahrheits- / Falschwert zurückgibt, oder ein vollständiges Programm, das E / A ausführt.
Regeln:
- Da dies Codegolf ist , sollten Sie versuchen, dies in möglichst kurzer Anzahl von Bytes zu tun . Builtins sind erlaubt.
- Es gelten Standard-Golflöcher - Sie können die Mersenne-Primzahlen nicht aus externen Dateien lesen oder in Ihr Programm einprogrammieren.
- Ihr Programm sollte für Werte innerhalb der Standard-Integer-Größe Ihrer Sprache funktionieren.
Testfälle
Als Referenz wird eine Liste von (bekannten) Mersenne - Primzahlen finden sich hier . Einige handliche Testfälle sind:
2 -> False
1 -> False
20 -> False
51 -> False
63 -> False
3 -> True
31 -> True
8191 -> True
Frohe Weihnachten an alle! Haben Sie einen schönen Urlaub, was auch immer Sie feiern :)
2^n-1
n
ist immer prim, aber da sich nichts ändert, ist die Definition immer noch korrekt.Antworten:
Gelee , 5 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
05AB1E , 5 Bytes
Eine positive Zahl in der Form 2 n - 1 in binärer Form besteht nur aus Einsen .
Code:
Erläuterung:
Verwendet die CP-1252- Codierung. Probieren Sie es online! oder Überprüfen Sie alle Testfälle .
quelle
Python , 45 Bytes
Probieren Sie es online!
Wie es funktioniert
Die drei Begriffe des verketteten Vergleichs
Mach Folgendes:
-~n&n
berechnet das bitweise UND von n + 1 und n . Da n nur aus 1 Bit besteht, wenn es eine Mersenne-Zahl ist, gibt das bitweise UND 0 zurück, wenn (und nur wenn) dies der Fall ist.all(n%i for i in range(2,n))
Gibt nur dann True zurück, wenn n mod i für alle Werte von i in [2,…, n - 1] ungleich Null ist , dh nur dann, wenn n außer 1 und n keine positiven Teiler hat .Mit anderen Worten, alle Erträge wahr , wenn und nur wenn n eine zusammengesetzte Zahl ist, dh n ist entweder 1 oder eine Primzahl.
n
ist selbsterklärend.Der verkettete Vergleich gibt nur dann True zurück, wenn die einzelnen Vergleiche dasselbe tun.
Da alle gibt entweder Wahr / 1 oder Falsch / 0 ,
-~n&n<all(n%i for i in range(2,n))
kann nur zurück Wahr , wenn-~n&n
Ausbeuten 0 ( das heißt, wenn n eine Mersenne Zahl) und alle Rücksendungen Wahr (dh wenn n entweder 1 oder eine Primzahl).Der Vergleich
all(n%i for i in range(2,n))<n
gilt immer dann, wenn n> 1 ist. Da jedoch bei n = 1 alle den Wert True zurückgeben , gilt dies in diesem Fall nicht.quelle
Brachylog , 7 Bytes
Probieren Sie es online!
Ein Brachylog Programm im Grunde eine Folge von Einschränkungen ist , die eine Kette bilden: der erste Eingrenzungs zwischen dem Eingang und einer anonymen unbekannt (nennen sie es ein für die Zwecke dieser Diskussion), ist die zweite Bedingung zwischen diesen anonymen unbekannten und einem zweiten anonymen unbekannt (was wir B nennen ) und so weiter. Als solches bricht das Programm folgendermaßen zusammen:
Alle diese Bedingungen können nur dann gleichzeitig erfüllt werden, wenn B eine Potenz von 2 ist, dh die Eingabe eine Potenz von 2 minus 1 ist und die Eingabe ebenfalls prim ist. (Brachylog verwendet intern einen Constraint-Solver, sodass das Programm nicht so ineffizient ist, wie es in der Auswertungsreihenfolge aussieht. Es ist jedoch klar, dass diese
C
Form vorliegt,[2, Y]
bevor versucht wird, sieB
als Potenzierung zweier Zahlen auszudrücken .)Interessanterweise
#p+~^
fast funktioniert, weil Mersenne-Primzahlen wie nur 2 als Base in nicht-degenerierten Fällen (können Nachweis ), aber a) es nicht für Nicht-Mersenne - Primzahlen B -1 , wie sie ausgedrückt werden kann als B ¹ und b ) Der vorhandene Brachylog-Interpreter scheint durch ein Programm, das so wenig eingeschränkt ist, verwirrt zu sein (er geht in eine unendliche oder zumindest lange Schleife). Es ist also unwahrscheinlich, dass 7 Bytes in Brachylog geschlagen werden.quelle
Mathematica 26 Bytes
Siehe diesen Beweis
Funktioniert, solange es keine ungeraden perfekten Zahlen gibt und keine bekannt ist.
quelle
n(n+1)/2
liefert (gerade) perfekte Zahlen, wennn
es sich um eine Mersenne-Primzahl (Euklid) handelt. Es scheint unbekannt zu sein, ob eine ungerade perfekte Zahl die Form haben kannn(n+1)/2
, dh eine dreieckige Zahl. Alle geraden perfekten Zahlen sind dreieckig, wenn diesn
eine Mersenne-Primzahl (Euler) ist.Mathematica,
2926 BytesBearbeiten: 3 Bytes dank Martin Ender gespeichert
PrimeQ@#&&IntegerQ@Log2[#+1]&
Ich vermute, dies wäre schneller, da die ersten 42 Exponenten fest codiert sind:
quelle
PrimeQ@#&&1>BitAnd[#,#+1]&
Perl 6 , 29 Bytes
Versuch es
Erweitert:
Da Perl 6 willkürlich große Ints hat, füllt es die Vorderseite nicht
.base(2)
mit0
s auf.quelle
Python,
8382797673 BytesPython 2, 71 Bytes
Diese Funktion implementiert den Lucas-Lehmer-Primalitätstest. Sie ist zwar nicht so kurz wie einige andere Python-Angebote, kann jedoch sehr viel schneller große Eingaben verarbeiten.
Hier ist ein Testcode, der auf Python 2 oder Python 3 ausgeführt wird.
Ausgabe
FWIW, hier ist eine etwas effizientere Version
f
, die nichtm
in jeder Schleife erneut getestet wird:quelle
R
4140 BytesSeltsamer in R die builtin
mersenne
nimmtn
als Argument nicht2^n-1
.Dieser entnimmt
x
STDIN, prüft anhand desmatlab
Pakets , ob es sich um eine Primzahl handelt und prüft, ob das 2-log vonx+1
eine ganze Zahl ist, indem mod 1 genommen und auf 'nicht Null' überprüft wird.Wenn Sie die
mersenne
eingebaute Funktion verwenden, ist sie zwar etwas kürzer, fühlt sich aber wie Schummeln an:1 Byte dank @Billywob gespeichert
quelle
matlab::isprime
, ein Byte zu speichern. Auch müssen Sie<-
für In-Function-Zuweisung verwenden.log2(x+1)
stattdessen auch verwendenlog(x+1,2)
.Pyke, 10 Bytes
Probieren Sie es hier aus!
quelle
Eigentlich 9 Bytes
Probieren Sie es online!
Erläuterung:
Da jede Zahl der Form 2 n -1 alle Einsen in ihrer binären Darstellung hat, kann eine Mersenne-Primzahl als Primzahl mit dieser Qualität identifiziert werden.
quelle
Gelee, 5 Bytes
Alternative Herangehensweise an @Dennis 'bestehende 5-Byte-Jelly-Antwort:
Probieren Sie es online!
Wie es funktioniert:
Da eine Mersenne-Primzahl eine 1 weniger als eine Potenz von 2 ist, ist ihre binäre Darstellung ausschließlich 1er. Die Ausgabe hierfür ist 1 für Mersenne-Primzahlen und 0 in allen anderen Fällen.
quelle
Ceylon, 66 Bytes
Formatiert (und kommentiert):
Durch Cheaten (Hardcodierung der Ergebnisse im Bereich von Ceylons Integer) können wir ein Byte kürzer machen (65):
(Es sieht so aus, als würde der Syntax-Textmarker Ceylons Hexadezimalzahlen als Kommentaranfang missverstehen.)
Wenn eine anonyme Funktion in Ordnung ist, sind dies 49 Bytes:
quelle
Wolfram Language (Mathematica) , 23 Byte
Probieren Sie es online!
1 wird richtig gehandhabt, weil
PrimeQ[BitAnd[1,1+2]*1] == PrimeQ@1 == False
. AnsonstenBitAnd[#,#+2]#
brauchen wir,#
um Primzahl zu sein, Primzahl undBitAnd[#,#+2] == 1
, was passiert, wenn#
es sich um eine Mersenne-Zahl handelt.quelle
ECMAScript-Regex,
4231 Bytes^(?!(xx+)\1+$)(x(x*)(?=\3$))+x$
Probieren Sie es online!
Edit: Bis zu 31 Bytes dank Neil.
Der Grundtest "ist eine Potenz von 2 minus 1" ist
^(x(x*)(?=\2$))*$
. Dies funktioniert, indem die Operation "subtrahiere 1, dividiere dann gleichmäßig durch 2" durchlaufen wird, bis dies nicht mehr möglich ist, und dann behauptet wird, dass das Ergebnis Null ist. Dies kann so geändert werden, dass es nur mit Zahlen ≥ 1 übereinstimmt, indem das letzte*
in ein a geändert wird+
, wodurch die Schleife gezwungen wird, mindestens einmal zu iterieren. Einfügen einesx
vor dem letzten$
modifiziert es so, dass es nur mit Zahlen ≥3 übereinstimmt, indem behauptet wird, dass das Endergebnis nach mindestens einer Schleife 1 ist.Der zugehörige "Ist eine Potenz von 2" -Test ist
^((x+)(?=\2$))*x$
. Es gibt auch eine Abkürzung für Matching-Potenzen von 2 minus 2, die von Grimy entdeckt wurde :^((x+)(?=\2$)x)*$
. Alle drei Regexes sind gleich lang.Alternative 31-Byte-Version von Grimy :
^(?!(xx+)\1+$|((xx)+)(\2x)*$)xx
Probieren Sie es online!
quelle
x(x+)(?=\3$)
es etwas effizienter darüber nachzudenken ?Regex (ECMAScript), 29 Bytes
Probieren Sie es online!
Inspiriert von Grimy im Chat
Der reguläre Ausdruck gibt an, dass die Eingabe größer als 3 ist und keine der folgenden Formen aufweist:
(xx+)\1+
oder((xx)+)(\1x)+
.Der erste stimmt mit zusammengesetzten Zahlen überein.
Die Sekunde stimmt mit einer Zahl überein, die um 1 kleiner als ein Vielfaches einer ungeraden Zahl größer als 2 ist.
Die erste stimmt nicht mit den Primzahlen oder2n- 1
0
oder überein1
.Die zweite stimmt nicht mit den Nummern des Formulars überein
Da 2 die einzige Primzahl ist, die 1 weniger als eine ungerade Primzahl ist, stimmt der negative Lookahead zusammen mit der Behauptung, dass die Eingabe größer als 3 ist, nur mit Mersenne-Primzahlen überein.
quelle
Ruby, 47 Bytes
quelle
Julia, 26 Bytes
quelle
Python, 65 Bytes
Ausgänge über Exit Code. Rekursionsfehler für False. Kein Fehler für True.
Wie es funktioniert
Da
2^n-1
in binär ganz aus Einsen gemacht wird, kommt die nächste2^n-1
Zahl durch generiert werdennumber|number+1
.Diese Funktion verwendet dies, indem sie jede
2^n-1
Zahl rekursiv überprüft, um festzustellen, ob es sich um eine Primzahl handelt, und um eine Gleichung für die Eingabe. Wenn die Zahl keine Mersenne-Primzahl ist, wird Python möglicherweise einen Fehler auslösen, da die maximale Rekursionstiefe überschritten worden wäre.quelle
<0
~>0>
.Aufdringlich , 7 Bytes
Probieren Sie es online!
Dies nutzt die Tatsache aus, dass Mersenne-Zahlen nur Einsen in ihrer Binärdarstellung haben:
Das Stack-Produkt wird nur sein,
1
wenn die Zahl in ihrer binären Darstellung keine Nullen hat und ihre Primalität istTrue
.quelle
Pyth , 8 Bytes
Überprüfen Sie alle Testfälle.
Pyth , 8 Bytes
Überprüfen Sie alle Testfälle.
Wie?
Code-Aufschlüsselung # 1
Wie funktioniert das?
Eine Zahl der Form 2 n - 1 enthält immer nur 1 , wenn sie binär geschrieben ist. Daher testen wir, ob alle seine Binärziffern 1 sind und ob es eine Primzahl ist.
Code-Aufschlüsselung # 2
Wie funktioniert das?
Dieser Test prüft, ob die Eingabe + 1 eine Zweierpotenz ist (dh ob es sich um eine Mersenne-Zahl handelt), und führt dann den Primalitätstest durch. Ist in Python
bool
eine Unterklasse vonint
, so wird die Wahrheit als 1 und die Falschheit als 0 behandelt . Um nicht explizit zu überprüfen, ob einer 0 und der andere 1 ist , vergleichen wir ihre Werte mit<
(da wir nur 1 solchen Fall haben).quelle
Java 8,
535249 BytesFehler behoben und dank @Nevay um 4 Bytes golfen .
Erläuterung:
Probieren Sie es hier aus.
quelle
true
für jede Primzahl> 2, nicht nur für Mersenne-Primzahlen, 56 Bytes zurück: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
Probieren Sie es hier aus
Python 2, 63 Bytes
Probieren Sie es hier aus
Danke für den Vorschlag Jonathan
Offen für Vorschläge zur Reduzierung des bytecount.
quelle
1 and
~>1and
.Japt, 6 Bytes
Führen Sie es aus oder führen Sie alle Testfälle aus
quelle
©
durch bitweise ersetzen,&
um eine konsistente Ausgabe zu erhalten, wenn Sie möchten.Python, 93 Bytes
Dieser Code würde sowohl in Python 2 als auch in Python 3 funktionieren, daher habe ich keine Version angegeben.
quelle
Schläger 76 Bytes
Ungolfed:
Testen:
Ausgabe:
quelle
PHP, 53 Bytes
Übernimmt das Kommandozeilenargument; druckt
1
für Mersenne prime, leere Zeichenfolge sonst. Laufen Sie mit-r
.Nervenzusammenbruch
quelle
C 94 Bytes
Gibt 1 zurück, wenn die Zahl eine Mersenne-Primzahl ist, andernfalls 0.
quelle
~x+g(2,n)
stattdessen vorx^g(2,n)-1
Scala, 59 Bytes
Für diese Funktion muss der Eingang a sein
BigInt
. Sie können einfach eine Zeichenfolge "162259276829213363391578010288127" (2 ** 107-1 ist eine Mersenne-Primzahl) in konvertieren,BigInt
indem Sie tunBigInt("162259276829213363391578010288127")
. Es könnte schief gehen, wie der Name derisProbablePrime()
Methode vermuten lässt. Aber die Wahrscheinlichkeit ist nicht mehr als0.5^(t.bigLength)*9
.Die eigenständige Skriptversion ist 72 Byte lang.
Angenommen, wir speichern es als "t.scala", dann kann das Programm ausgeführt werden als
quelle
Probable
von ,isProbablePrime
wenn Scala eine hatisPrime
Funktion.Perl 5 , 53 Bytes
52 Byte Code + 1 für
-p
Probieren Sie es online!
quelle
-p
Metakonsens wird die als eine andere Programmiersprache klassifiziert und zählt daher nicht zu Ihrem Bytecount.