Vor einiger Zeit habe ich mir die Primfaktorisierung von 27000 angesehen:
27000 = 2 3 × 3 3 × 5 3
Das hat zwei Besonderheiten:
- aufeinanderfolgende Primzahl : Die Primzahlen sind konsekutiv: 2 ist die 1. Primzahl, 3 ist die 2. Primzahl, 5 ist die 3. Primzahl.
- konstanter Exponent : Der Exponent ist für jede Primzahl gleich (immer 3)
Mathematisch ausgedrückt:
Eine Ganzzahl x ist eine fortlauf-prime / constant-Exponentenzahl , wenn es vorhanden ist streng positive ganze Zahlen n , k , m , so dass x = p n m × p n + 1 m × ... × P n + k m , wobei p j ist die j- te Primzahl
Ihre Aufgabe ist es zu testen, ob eine positive ganze Zahl diese Bedingungen erfüllt.
Eingang:
Eine positive ganze Zahl> 1 in jeder vernünftigen Form.
Ausgabe:
Einer von zwei Werten, von denen mindestens einer konstant sein muss, um anzuzeigen, ob die Eingabe eine fortlaufende Primzahl / Konstanten-Exponenten-Zahl ist.
Randfälle:
- Primzahlen sind truthy, da die Faktorisierung für Primzahl p ist , p 1
- andere Zahlen, die als p m geschrieben werden können, wobei p eine Primzahl ist, sind ebenfalls wahr.
Regeln:
- Es gelten Standardlücken.
- Keine Sorge um den Überlauf von Ganzzahlen, aber Zahlen bis zu 255 müssen funktionieren.
- Kürzester Code in Bytes gewinnt.
Testfälle:
Wahrheit:
2
3
4
5
6
7
8
9
11
13
15
27000
456533
Falsch:
10
12
14
72
10000000
Hier ist ein Python-Skript, das einige Testfälle generiert.
x = Pn^m
Teil zu tun . IchAntworten:
05AB1E , 4 Bytes
Probieren Sie es online!
Erläuterung
quelle
ÎÓKË
ist alles,ß
woran ich denken kann, außer diesem, netten ... Ich habe nachgedacht, aber es macht das Gegenteil von dem, was ich dachte.Regex (ECMAScript),
276205201193189 BytesDer Vergleich der Multiplizitäten (Exponenten) verschiedener Primfaktoren ist ein interessantes Problem für die Lösung mit ECMAScript Regex - das Fehlen von Rückreferenzen, die durch Iterationen einer Schleife bestehen, macht es zu einer Herausforderung, alles zu zählen. Selbst wenn das Zählen des fraglichen numerischen Merkmals möglich ist, führt ein indirekterer Ansatz oft zu einem besseren Golf.
Wie bei meinen anderen regulären ECMA-Posts gebe ich eine Spoiler-Warnung ausgeben: Ich empfehle dringend, zu lernen, wie man unäre mathematische Probleme in ECMAScript-Regex löst. Es war eine faszinierende Reise für mich, und ich möchte sie keinem verderben, der sie möglicherweise selbst ausprobieren möchte, insbesondere denen, die sich für Zahlentheorie interessieren. In diesem früheren Beitrag finden Sie eine Liste der nacheinander mit Spoiler-Tags gekennzeichneten empfohlenen Probleme, die nacheinander gelöst werden müssen.
So lesen keine weiteren , wenn Sie nicht einige erweiterte einstellige regex Magie für Sie verwöhnen wollen . Wenn Sie versuchen möchten, diese Magie selbst herauszufinden, empfehle ich dringend, zunächst einige Probleme in ECMAScript regex zu lösen, wie in dem oben verlinkten Beitrag beschrieben.
Die Hauptnutzlast eines Regex, den ich zuvor entwickelt habe, erwies sich als sehr zutreffend für diese Herausforderung. Das ist der reguläre Ausdruck, der die Primzahlen der höchsten Multiplizität findet . Meine erste Lösung dafür war sehr lang, und ich spielte sie später schrittweise ab, indem ich sie zuerst für die Verwendung von Molecular Lookahead umschrieb und dann mit einer fortschrittlichen Technik auf einfaches ECMAScript portierte , um das Fehlen von Molecular Lookahead zu umgehen , und anschließend Golf es viel kleiner als die ursprüngliche einfache ECMAScript-Lösung.
Der Teil dieses regulären Ausdrucks, der für dieses Problem gilt, ist der erste Schritt, bei dem Q ermittelt wird, der kleinste Faktor von N, der alle seine Primfaktoren teilt. Sobald wir diese Zahl haben, müssen wir nur noch N durch Q teilen, bis wir nicht mehr können. Wenn das Ergebnis 1 ist, sind alle Primzahlen gleich vielfach.
Nachdem ich eine Antwort unter Verwendung meines zuvor entwickelten Algorithmus zur Ermittlung von Q eingereicht hatte, stellte ich fest, dass diese auf eine völlig andere Weise berechnet werden kann: Ermitteln Sie den größten quadratfreien Faktor von N (unter Verwendung desselben Algorithmus wie bei meinem Carmichael-Zahlen-Regex) ). Wie sich herausstellt, ist dies überhaupt keine Schwierigkeit * im Hinblick auf das Fehlen eines molekularen Lookaheads und eines Lookbehinds mit variabler Länge (es ist nicht erforderlich, die zuvor verwendete fortschrittliche Technik einzuarbeiten), und es ist 64 Byte kürzer! Darüber hinaus entfällt die Komplexität, quadratfreies N und Prim N als unterschiedliche Sonderfälle zu behandeln, wodurch weitere 7 Byte aus dieser Lösung entfernt werden.
(Es verbleiben noch andere Probleme, die die fortgeschrittene Technik erfordern, die früher hier zum Herabsetzen der Berechnung von Q verwendet wurde, aber derzeit wird keine von ihnen durch meine PPCG-Posts dargestellt.)
Ich habe den Multiplizitätstest vor den Konsekutiv-Primzahlen-Test gestellt, weil letzterer viel langsamer ist; Wenn Sie Tests durchführen, die schneller fehlschlagen können, wird der reguläre Ausdruck für gleichmäßig verteilte Eingaben schneller. Es ist auch besser, Golf an erster Stelle zu setzen, weil es mehr Rückreferenzen verwendet (die mehr kosten würden, wenn sie zweistellig wären).
Ich konnte 4 Bytes aus dieser Regex (193 → 189) mit einem von Grimy gefundenen Trick löschen , der die Division weiter verkürzen kann, falls der Quotient garantiert größer oder gleich dem Divisor ist.
^(?=(|(x+)\2*(?=\2$))((?=(xx+?)\4*$)(?=(x+)(\5+$))\6(?!\4*$))*x$)(?=.*$\2|((?=((x*)(?=\2\9+$)x)(\8*$))\10)*x$)(?!(((x+)(?=\13+$)(x+))(?!\12+$)(x+))\11*(?=\11$)(?!(\15\14?)?((xx+)\18+|x?)$))
Probieren Sie es online!
* Mit molekularem Lookahead ist es immer noch sauberer, ohne dass N quadratfrei ist. Dies lässt 6 Bytes fallen und ergibt eine
195187183-Byte- Lösung:^(?=(?*(x+))\1*(?=\1$)((?=(xx+?)\3*$)(?=(x+)(\4+$))\5(?!\3*$))*x$)(?=((?=((x*)(?=\1\8+$)x)(\7*$))\9)*x$)(?!(((x+)(?=\12+$)(x+))(?!\11+$)(x+))\10*(?=\10$)(?!(\14\13?)?((xx+)\17+|x?)$))
Hier wird es auf Lookbehind mit variabler Länge portiert:
Regex (ECMAScript 2018),
198195194186182 Bytes^(?=(x+)(?=\1*$)(?<=^x((?<!^\5*)\3(?<=(^\4+)(x+))(?<=^\5*(x+?x)))*))((?=((x*)(?=\1\8+$)x)(\7*$))\9)*x$(?<!(?!(\14\16?)?((xx+)\12+|x?)$)(?<=^\13+)((x+)(?<!^\15+)((x+)(?<=^\17+)(x+))))
Probieren Sie es online!
quelle
.*$\2
mit\2^
^(?=(|(x+)\2*(?=\2$))(((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$))*x$))(?!(((xx+)(?=\10+$)(x+))(?!\9+$)(x+))\8*(?=\8$)(?!(\12\11?)?(xx+)\14+$))((?=((x*)(?=\2\17+$)x)(\16*$))\19)*\3$
Jelly ,
1365 BytesProbieren Sie es online!
Immer noch outgolfed ... (danke Erik für -1 Byte)
Erläuterung
quelle
œl
->t
. Es gibt keinen Grund, Nullen in der Ausgabe von ÆE nachzustellen.JavaScript (ES6), 87 Byte
Gibt 0 für wahr oder eine ganze Zahl ungleich Null für falsch zurück.
Probieren Sie es online!
Kommentiert
quelle
j||i
zu gebrocheni
. Es gibt jetzt viele falsch-positive Ergebnisse.CJam ,
3029 BytesProbieren Sie es online!
Meine erste Antwort nach fast 2 (!) - jähriger Pause, damit kann man wohl mehr golfen. Dies ist ein Block, der Eingaben als Ganzzahl akzeptiert (kann auch für Arrays von Ganzzahlen abgebildet werden).
Erläuterung
quelle
Stax ,
56 BytesFühren Sie es aus und debuggen Sie es
Entpackt, ungolfed und kommentiert sieht es so aus.
Bearbeiten:
Dies funktioniert nichtEs funktioniert jetzt.512
. Ich werde darüber nachdenken und hoffentlich später eine Lösung finden.quelle
Stax , 9 Bytes
1 ist wahr, 0 ist falsch
Führen Sie es aus und debuggen Sie es
Erläuterung
Kann wahrscheinlich mehr golfen werden, aber es deckt die Fälle ab, die ich in der letzten Lösung vermisst habe.
quelle
MATL ,
12 1110 BytesProbieren Sie es bei MATL Online!
Vielen Dank an Luis Mendo für das Entfernen der führenden Nullen. Er wies auch darauf hin, dass das Austauschen von Wahrheitswerten zulässig ist, sodass für Zahlen, die die Herausforderungsanforderungen erfüllen, und für jeden anderen positiven Wert 0 zurückgegeben wird .
Grosso Modo, dies generiert die Exponenten der sequentiellen Primfaktorisierung, entfernt führende Nullen und berechnet die Standardabweichung.
quelle
0iYFhdz
arbeitet für 7 Bytes: voranstellen einer 0 zu den Exponenten der sequentiellen Faktorisierung, aufeinanderfolgenden Differenzen, Anzahl der Nicht-Nullen. Das Ergebnis ist,1
wenn die Eingabe die Anforderung erfülltJava 10,
223191178176168 BytesReturns
1
als truthy und>=2
als Falsey.Probieren Sie es online aus.
Erläuterung:
Einige Beispieleingaben:
n=15
:1
für die erste Primzahl 2 (da 15 nicht durch 2 teilbar ist).1
bis0
, sobald wir bei Primzahl 3 sind. Da 15 durch 3 teilbar ist,n
wird 5 (15/3 1 ) und das Set wird[] → [1]
.n
wird 1 (5/5 1 ) und die Menge bleibt gleich ([1] → [1]
).n=1
stoppen wir also die äußere Schleife. Das Set ([1]
) enthält nur ein Element, das1
aus den beiden benachbarten Primzahlen 3 und 5 stammt. Wir geben also true zurück.n=14
:1
bis0
für die erste Primzahl 2 (da 14 durch 2 teilbar ist).n
wird zu 7 (14/2 1 ) und das Set wird[] → [1]
.n
bleibt sie gleich und die Menge wird[1] → [1,0]
.n
bleibt sie gleich, und die Menge bleibt auch gleich ([1,0] → [1,0]
).n
wird 1 (7/7 1 ) und die Menge bleibt gleich ([1,0] → [1,0]
).n=1
stoppen wir also die äußere Schleife. Das Set ([1,0]
) enthält zwei Elemente, das1
aus den nicht benachbarten Primzahlen 2 und 7 und das0
aus den Primzahlen 3 und 5, sodass wir false zurückgeben.n=72
:1
bis0
für die erste Primzahl 2, da 72 durch 2 teilbar ist (mehrfach). Son
wird 9 (72/2 3 ) und das Set wird[] → [3]
.n
wird 1 (9/3 2 ) und die Menge wird[3] → [3,2]
.n=1
stoppen wir also die äußere Schleife. Das Set ([3,2]
) enthält zwei Elemente, das3
von Prim 2 und das2
von Prim 3, also geben wir false zurück.quelle
<2
ein int entfernen und zurückgeben (geben Sie an, dass Sie 1 für truthy zurückgeben).1
ist wahr und2
oder höher ist falsch. Vielen Dank.J , 16 Bytes
Vielen Dank an FrownyFrog für -8 Bytes!
Probieren Sie es online!
Meine alte Lösung:
J , 24 Bytes
Probieren Sie es online!
Erläuterung:
_&q:
Hauptexponenten{.@I.}.]
Entfernt die führenden Nullen, indem das erste Nicht-Null-Element gefunden wird:1=[:#@~.
prüft, ob alle verbleibenden Zahlen gleich sind:quelle
Schale , 11 Bytes
Probieren Sie es online!
Gibt 0 aus, wenn keine fortlaufende Primzahl / konstante Exponentenzahl.
quelle
MATL , 7 Bytes
Das Ergebnis ist,
1
wenn die Eingabe die Anforderung erfüllt.Probieren Sie es online! Oder überprüfen Sie alle Testfälle
Erläuterung
quelle
Oktave , 67 Bytes
Probieren Sie es online!
Ich glaube, dies ist die einzige Lösung, die ein Histogramm verwendet.
Erläuterung:
Auf diese Weise wird ein Histogramm erstellt, in dem die zu zählende Variable die Faktoren der Eingabe darstellt und in die Bins platziert wird
primes(x)
, bei denen es sich um Primzahlen handelt, die kleiner als die Eingabe sind. Wir finden dann die Position der Primfaktoren, nehmen die Differenz zwischen den einzelnen Indizes und subtrahieren einen. Wenn es Elemente gibt, die nicht Null sind (dh die Differenz der Indizes von Primzahlen ist nicht 1), führt dies zu einem falschen Wert, andernfalls wird ein wahrer Wert zurückgegeben.Wir prüfen dann, dass alle Nicht-Null-Elemente im Histogramm gleich dem maximalen Element sind. Wenn es Werte gibt, die nicht gleich sind, führt dies zu einem falschen Wert, andernfalls wird ein wahrer Wert zurückgegeben.
Wenn beide Blöcke wahr sind, ist unsere Eingabe eine fortlaufende konstante Exponenten-Primzahl!
quelle
APL (Dyalog Extended) , 28 Byte
Probieren Sie es online!
Wie:
quelle
Wolfram Language (Mathematica) , 65 Byte
Probieren Sie es online!
quelle
Pari / GP , 63 Bytes
Probieren Sie es online!
quelle
J , 14 Bytes
1 in der Ausgabe gibt einen konsekutiven konstanten Exponenten an.
Probieren Sie es online!
quelle
Sauber , 127 Bytes
Probieren Sie es online!
Legt die Funktion
? :: Int -> Bool
mit$ :: Int -> [Int]
faktorisieren und@ :: Int -> Bool
primality zu überprüfen.quelle
APL (NARS) 41 Zeichen, 82 Byte
{π⍵} ist die Funktionsfaktorisierung des Arguments ⍵ in der Liste der Primfaktoren (Wiederholung, wenn ein Prim mehrmals auftritt);
{1π⍵} ist die nächste Primzahl der Funktion (in diesem Fall ist das Argument kein Skalar, sondern ein Array von Ganzzahlen). Prüfung:
quelle