Vor ungefähr einem Jahr wurden Sie gebeten, die XOR-Primzahlen zu finden . Dies sind Zahlen, deren einzige Faktoren 1 und sich selbst sind, wenn eine XOR-Multiplikation in Basis 2 durchgeführt wird . Jetzt werden wir die Dinge ein bisschen aufpeppen.
Wir werden die XOR-Primzahlen in Basis -2 finden
Konvertieren in Basis -2
Basis -2 ist wie jede andere Basis. Die am weitesten links stehende Stelle ist die 1s-Stelle (1 = (-2) 0 ), daneben die -2s-Stelle (-2 = (-2) 1 ), daneben die 4s-Stelle (4 = (-2) ) 2 ) und so weiter und so fort. Der große Unterschied besteht darin, dass negative Zahlen in der Basis -2 ohne negatives Vorzeichen dargestellt werden können.
Hier einige Beispielkonvertierungen:
Decimal | Base -2
-----------------
6 | 11010
-7 | 1001
12 | 11100
-15 | 110001
XOR-Addition in Base -2
Die XOR-Addition in Base -2 entspricht weitgehend der XOR-Addition in Binärform. Sie konvertieren einfach die Zahl in Basis -2 und XOR für jede Stelle. (Dies ist dasselbe wie Addition ohne Carry)
Hier ist ein Beispiel, das Schritt für Schritt durchgearbeitet wird:
(Wir werden das Symbol verwenden +'
, um die Addition von Base -2 XOR anzuzeigen.)
Beginnen Sie in Basis 10:
6 +' -19
In Basis -2 konvertieren:
11010 +' 10111
Fügen Sie sie hinzu, ohne zu tragen:
11010
+' 10111
---------
01101
Konvertieren Sie Ihr Ergebnis wieder in Basis 10:
-3
XOR-Multiplikation in Basis -2
Wiederum ist die XOR-Multiplikation in Basis -2 fast dieselbe wie die XOR-Multiplikation in Binär. Wenn Sie nicht vertraut mit XOR - Multiplikation in der Basis sind 2 gibt es eine ausgezeichnete Erklärung hier empfehle ich Ihnen zu diesem zunächst einen Blick.
Die XOR-Multiplikation in Basis -2 entspricht der Durchführung einer langen Multiplikation in Basis -2, außer wenn es um den letzten Schritt geht, anstatt alle Zahlen mit einer traditionellen zu addieren, verwenden +
Sie die +'
oben definierte.
Hier ist ein Beispiel, das unten ausgearbeitet wurde:
Beginnen Sie in Dezimalzahl:
8 *' 7
In Basis -2 konvertieren:
11000 *' 11011
Lange Teilung einrichten:
11000
*' 11011
---------
Multiplizieren Sie die erste Zahl mit jeder Stelle in der zweiten
11000
*' 11011
------------
11000
11000
0
11000
11000
Addieren Sie alle Ergebnisse mit der Basis -2 XOR-Addition
11000
*' 11011
-------------
11000
11000
0
11000
+' 11000
-------------
101101000
Konvertieren Sie das Ergebnis zurück in eine Dezimalzahl:
280
Die Herausforderung
Ihre Herausforderung besteht darin, zu überprüfen, ob eine Zahl eine XOR-Primzahl in Basis -2 ist oder nicht. Eine Zahl ist eine XOR-Primzahl in der Basis -2, wenn das einzige Paar von ganzen Zahlen, die sich in der Basis mit ihr multiplizieren, 1 und sich selbst ist. (1 ist keine Primzahl)
Sie nehmen eine Zahl auf und geben einen Booleschen Wert aus, der wahr ist, wenn die Eingabe ansonsten eine XOR-Primzahl in der Basis -2-Falschheit ist.
Lösungen werden in Bytes bewertet, wobei die niedrigste Anzahl von Bytes als Ziel erreicht wird.
Testfälle
Das Folgende sind alle XOR-Primzahlen in Basis -2:
-395
-3
-2
3
15
83
Die folgenden sind keine XOR-Primzahlen in Basis -2:
-500
-4
0
1
258
280
quelle
258
scheint gleich zu sein-2 *' -129 = 10 *' 10000011
Antworten:
Mathematica,
156101 BytesWie hier angegeben , funktioniert dies, weil die XOR-Multiplikation im Wesentlichen eine Multiplikation im Polynomring F_2 ist.
Erläuterung
Beginnen Sie mit
{input}
. Ersetze wiederholt eine Zahla
(außer 0 und 1) durcha
Mod 2 und stelle -floor (a
/ 2) voran , bis sie sich nicht mehr ändert. Dies berechnet die Eingabe in Basis -2.Erstellen Sie ein Polynom mit den Ziffern der Basis -2-Zahl
x
als Variable. zB{1, 1, 0}
->x^2 + x
Überprüfen Sie mit Modul 2, ob das resultierende Polynom nicht reduzierbar ist.
Alte Version (156 Bytes)
Liste der Primzahlen
Hier ist eine Liste von Basis -2 XOR-Primzahlen zwischen -1000 und 1000 (Pastebin)
quelle