Eine Zahl ist genau dann eine de Polignac-Zahl, wenn sie ungerade ist und nicht in der Form p + 2 n dargestellt werden kann, wobei n eine nicht negative ganze Zahl und p eine ganze Primzahl ist.
Aufgabe
Schreiben Sie einen Code, der eine positive ganze Zahl enthält und feststellt, ob es sich um eine de Polignac-Zahl handelt. Sie können zwei unterschiedliche Werte ausgeben, einen für wahr und einen für falsch. Sie sollten darauf abzielen, Ihre Byteanzahl zu minimieren.
Testfälle
Für positive Fälle ist hier der OEIS
1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, 1529, 1541, 1549, 1589, 1597, 1619, 1649, 1657, 1719, 1759, 1777, 1783, 1807, 1829, 1859, 1867, 1927, 1969, 1973, ...
Hier sind einige negative Fälle:
22, 57
code-golf
number
number-theory
decision-problem
Weizen-Assistent
quelle
quelle
Antworten:
Japt ,
91413 BytesOnline testen! oder Finden Sie alle de Polignac-Ganzzahlen unter 1000 .
Ausgänge
1
für falsche Eingaben und0
für Wahrheiten.Erläuterung
quelle
false
aber es sind keine Polignac-Zahlen.3
ist behoben, aber wir mussten zunächst nicht einmal Fälle behandeln. Festsetzung.3
keine Bytes gekostet hat, als ich den Fix für2
- Autsch!Jelly ,
11 bis10 Bytes1 Byte dank @Dennis gespeichert
Probieren Sie es online!
Wie es funktioniert
quelle
Ḷ2*⁸_ÆPS<Ḃ
Speichert ein Byte. tio.run/##ASQA2/9qZWxsef//4bi2Mirigbhfw4ZQUzzhuIL/…¬;ḂẠ
.S<Ḃ
ist weit außerhalb der Box, zumindest für mich :-)JavaScript (ES6),
56 5453 ByteGibt0 oder 1 .
Probieren Sie es online!
Wie?
Wir beginnen mitp = 1 . Wir testen, ob y= n - p ist und ergeben dementsprechend einen Booleschen Wert. Der nächste Test wird mit p × 2 .
Sobaldp größer als n , stoppen wir die Rekursion und geben n .
Die Ergebnisse aller Iterationen werden UND-verknüpft, wodurch die Booleschen Werte entweder auf0 oder 1 .
Vorausgesetzt, dass alle Zwischenergebnisse wahr sind, erhalten wir einen bitweisen Test wie:
1 & 1 & 1 & n
Dies ergibt1 genau dann, wenn n ungerade ist. Dies ist die letzte Bedingung, die erforderlich ist, um die Eingabe als De-Polignac-Zahl zu validieren.
quelle
n%2
oder ähnlichPython 2 ,
605756 BytesProbieren Sie es online!
quelle
&n&
. Die Zahl 5 wäre falsch negativ, wenn es sich um eine de Polignac-Zahl handeln würde, da 1 + 4 = 5, aber dies ist kein Problem, da 2 + 3 = 5.Gelee , 10 Bytes
Eine alternative 10-Byte-Jelly-Vorlage zu der bereits veröffentlichten.
Eine monadische Verbindung, die 1 für de Polignac-Zahlen und 0 für andere zurückgibt.
Probieren Sie es online! oder sieh die unter 1000 .
Wie?
quelle
05AB1E ,
98 Bytes-1 Byte danke an Emigna
Ausgänge
0
für wahrheitsgemäße Eingaben und1
für falsche Eingaben.Probieren Sie es online!
quelle
1å
könnte seinZ
.Python 2 , 99 Bytes
Probieren Sie es online!
-4 Bytes dank Leaky Nun
-2 Bytes dank Wondercricket
+8 Bytes, um einen Fehler zu beheben
-1 Byte danke an Herrn Xcoder
-3 Bytes dank Einkorn Enchanter
+12 Bytes, um einen Fehler zu beheben
quelle
Regex (ECMAScript), 97 Bytes
Dieses Problem war ein interessanter Fall, um das Problem des Fehlens eines nichtatomaren Vorausschauers zu umgehen. Und es ist das einzige Mal, dass ich einen guten Grund hatte, beide Versionen der Potenz von 2 zu testen,
((x+)(?=\2$))*x$
und es ist das einzige Mal, dass ich(?!(x(xx)+)\1*$)
den Primetest gegen Matching schützen musste 1, wie(?!(xx+)\1+$)xx
bei Verwendung in einem größeren Regex.^(?!(xx)*$|(x+)((?!(xx+)\4+$).*(?=\2$)((x+)(?=\6$))*x$|(?!(x(xx)+)\7*$).*(?=\2$)(?!(xx+)\9+$)xx))
Probieren Sie es online!
Regex (ECMAScript + Molecular Lookahead),
5352 Bytes^(?!(xx)*$|(?*xx+(((x+)(?=\4$))*x$))\2(?!(xx+)\5+$))
Diese Version ist nicht nur viel sauberer, sondern auch viel schneller, denn anstatt alle möglichen Wege durchlaufen zu müssen, in denen N die Summe von zwei Zahlen ist, kann man einfach jede Potenz von 2 von N subtrahieren und die Differenz auf Primzahl testen .
Der molekulare Lookahead kann einfach in einen Look mit variabler Länge umgewandelt werden:
Regex (.NET oder ECMAScript 2018),
5554 Byte^(?!(xx)*$|xx+(((x+)(?=\4$))*x$)(?<=(?<!^\5+(x+x))\2))
Probieren Sie es online! (.NET)
Probieren Sie es online! (ECMAScript 2018)
quelle
^(?!(x+)((?!(xx+)\3+$)x*(?!(x(xx)+)\4*$)|x(?!(x(xx)+)\6*$)x*(?!(xx+)\8+$)x)?\1$)
ohne allzu große Schwierigkeiten optimiert werden. Dann kann mit einigen sorgfältigen Überlegungen weiter nach Golf gespielt werden^(?!(x+)((x?)(?!(x(x\3)+)\4+$)x*(?!(x(xx)+|\3\3+)\6+$)\3)?\1$)
. Kürzere können noch möglich sein(x(xx)+|\3\3+)
->(x\3?(xx)+)
Mathematica, 41 Bytes
quelle
PrimeQ[#-2^Range[0,Log2@#]]
mitPrimeQ[#-2^Range[0,#]]
und dann durchPrimeQ[#-2^Range@#/2]
.PHP , 75 Bytes
gibt 1 für wahr und 0 für falsch aus
Probieren Sie es online!
Probieren Sie es online! Polignac Ganzzahlen unter 10000
quelle
Pari / GP , 34 Bytes
Probieren Sie es online!
quelle
Brachylog ,
15 bis13 BytesProbieren Sie es online!
Polignac-Zahlen bis 1000 ausgeben.
Rückgabe
false.
für de Polignac-Nummern undtrue.
andere.Basierend auf der gelöschten Antwort von @ LeakyNun mit einigen Bugfixes (mit deren Erlaubnis veröffentlicht).
(-2 Bytes mit der @ Jonathan Allan-Methode, um zu überprüfen, ob die Zahl eine Zweierpotenz ist.)
Die angegebene Nummer ist keine Polignac-Nummer, wenn:
quelle
=h2
wäre 1 Byte kürzer, aber es funktioniert auch nicht3
.Jelly , 13 Bytes
Probieren Sie es online!
Ausgaben
1
für false und0
für true.quelle
Ḷ2*ạfÆRṆ
dann auf Parität prüfenḶ2*ạfÆRṆo‘Ḃ
gibt1
für beide127
und zurück22
; das ist nicht richtig. Es sei denn, Sie haben das nicht vorgeschlagen.0
für 149.ạ
um_@
es zu beheben.Perl 6 , 55 Bytes
Probieren Sie es online!
(1, 2, 4 ... * > $_)
ist eine Folge der Zweierpotenzen bis zum Eingabeargument (Perl leitet die geometrische Reihe aus den bereitgestellten Elementen ab).grep &is-prime, ^$_
ist die Liste der Primzahlen bis zum Eingabeargument.[X+]
Wertet die Summe aller Elemente des Kreuzprodukts der beiden Reihen aus.Ich hätte auf die
so
zwei Bytes weniger verzichten können, aber dann werden zwei verschiedene falsche Werte (0
undFalse
) zurückgegeben.quelle
Axiom, 86 Bytes
Test und Ergebnisse
quelle
Haskell,
104102 BytesErläuterung
(+)
auf 2 ^ angewendeten Teilfunktionen, die auf eine Liste angewendet werden [0..Eingabe]UPDATE: Schreien Sie Einkorn Enchanter für das Golfen von zwei Bytes!
quelle
p x=[x]==[i|i<-[2..x],x`mod`i<1]
ist ein kürzerer Primalitätstest.filter p[1..k]
anstelle vonfilter(p)[1..k]
Common Lisp, 134 Bytes
Gibt zurück,
NIL
wenn das Argument eine Polignac-Zahl ist,T
andernfalls.Probieren Sie es online!
Ungolfed:
quelle
APL (Dyalog Extended) , 12 Byte
Probieren Sie es online!
Anonymes Präfix implizite Funktion. Gibt 1 für wahr, 0 für falsch zurück.
Hauptsächlich basierend auf der Japt-Antwort von ETHProductions .
Vielen Dank an @ Adám für die Unterstützung beim Golfen meiner ursprünglichen Antwort und für die Erstellung von Dyalog Extended.
Wie:
quelle
Python 2 , 98 Bytes
Probieren Sie es online!
quelle
Pyth , 14 Bytes
Versuch es!
quelle
Julia 0,4 , 31 Bytes
Probieren Sie es online!
quelle
APL (NARS) 80 Zeichen, 160 Byte
Die Funktion 0π ist die Funktion, die zurückgibt, ob ihr Argument prim ist oder nicht. Für mich ist diese Funktion nicht rekursiv, daher ist sie etwas länger ... Test:
für Eingabe <= 0 oder Eingabe> = 9E9 wird ¯1 zurückgegeben (Fehler)
quelle
C # (Visual C # Interactive Compiler) , 107 Byte
Probieren Sie es online!
Nicht der effizienteste Code, scheint aber zu funktionieren. Meine ursprüngliche Lösung hat nach Primzahlen gefiltert, bevor sie in der Formel getestet wurde, und es lief viel besser. Die aktuelle Version ist 11 Bytes kürzer.
quelle