Ich bin ein großer Fan der Zahlentheorie. Eine große Sache in der Zahlentheorie ist die modulare Arithmetik; Die Definition ist genau dann wenn . Eine lustige Sache ist es, die Potenzen zu erhöhen: besonders wenn der Modul eine Primzahl ist. Insbesondere wurde bewiesen, dass, wenn und relativ prim sind (außer keine gemeinsamen Faktoren teilen ), eine Zahl so dass .
Ich werde anhand eines Beispiels erklären, was die Übung ist. Nehmen wir einen Modul . Eine mögliche Ausgabe des Programms oder der Funktion wäre:
3 2 6 4 5 1
2 4 1 2 4 1
6 1 6 1 6 1
4 2 1 4 2 1
5 4 6 2 3 1
1 1 1 1 1 1
Jede Zeile ist eine Liste der Potenzen der ersten Zahl in dieser Zeile: Die erste Zeile ist , was Modulo . Die zweite Reihe des Quadrats oben ist die Potenz von usw. bis zur letzten Reihe, die nur Potenzen von .
Dies ist ein magisches Modulo-Quadrat, weil:
- Das Quadrat ist symmetrisch; Das heißt, die te Spalte ist dieselbe wie die te Zeile.
- Alle Werte bis erscheinen mindestens einmal.
Unten ist die einzige andere gültige Ausgabe für , beginnend mit Potenzen von :
5 4 6 2 3 1
4 2 1 4 2 1
6 1 6 1 6 1
2 4 1 2 4 1
3 2 6 4 5 1
1 1 1 1 1 1
Die Herausforderung
Erstellen Sie eine Funktion oder ein Programm, bei dem eine Primzahl p
ein magisches Modulo-Quadrat ausgibt, dh ein Quadrat mit Seitenlängen p-1
, sodass jede Zeile eine Liste der aufeinanderfolgenden Potenzen des ersten Elements in der Zeile ist und dasselbe für die Spalten. Alle Zahlen zwischen 0
und p
müssen vorkommen, und das Quadrat kann nur Zahlen in diesem Bereich enthalten.
Die Eingabe ist eine Zahl oder eine Zeichenfolge, und die Ausgabe kann ASCII, eine Matrix, ein Array von Arrays (jedes vernünftige Format) sein.
Dies ist Code-Golf, also gewinnt der kürzeste Code.
quelle
Antworten:
Gelee ,
1310 Bytes-3 danke an Nick Kennedy
Fühlt sich an wieder wiederholten Codesollte seinist Golf-Lage, aber ichhabees nicht geschafftdes ...Probieren Sie es online aus! (Fußzeile hübsche Formate als Raster)
Wie?
quelle
Holzkohle , 36 Bytes
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Hinweis: Leerzeichen. Erläuterung:
Erstellen Sie eine
p-1
durchp-1
Anordnung von Potenzen von1..p-1
Indizes1..p-1
(Modulop
).Ordnen Sie eine der Zeilen zu, die genau eine hat
1
.Ordnen Sie die Zeilen in der Reihenfolge der ausgewählten Zeile neu an und formatieren Sie die Ausgabe.
quelle
J ,
353231 BytesProbieren Sie es online aus!
quelle
Wolfram Language (Mathematica) ,
4643 BytesProbieren Sie es online aus!
-3 dank alephalpha
quelle
JavaScript (ES7),
9186 ByteDiese Version versucht, die Potenzen vor dem Anwenden des zu berechnen und für aufgrund von Genauigkeitsverlust fehl . Ansonsten wird dieselbe Logik wie in der kommentierten Version unten verwendet.p≥11
Probieren Sie es online aus!
JavaScript (ES6),
9287 ByteDiese Version verwendet modulare Exponentiation, um (viel) höhere Eingabewerte zu unterstützen.
Probieren Sie es online aus!
Wie?
Die erste Reihe finden
Bei wir die Hilfsfunktion , um für zu berechnen .1≤k<p g ak(n)=knmodp 1≤n<p
Wir suchen nach so dass es nur einen Wert so dass . Wir tun , dass das Array durch Sortieren und Prüfen , ob das 2 nd Element größer ist .k n ak(n)=1 11
Dies funktioniert sogar in lexikografischer Reihenfolge - was das Standardverhalten von ist
sort()
- weil:Beispiel:
Für :p=17
Erstellen der Matrix
Sobald wir gefunden haben , rufen wir erneut auf (um die unsortierte Version des Arrays abzurufen) und rufen für jedes Element von auf, um die Zeilen der Matrix zu erstellen.k g(k) g g(k)
Dieser Teil kann einfach geschrieben werden als:
quelle
.indexOf(1)>p-3
spart 3 Bytes.every
.Zsh ,
11790 BytesProbieren Sie es online aus!Probieren Sie es online aus!Möge Gott meiner Seele gnädig sein. Es gibt hier eine Menge schlechter Praktiken, lassen Sie mich zumindest den größten Täter erklären:
Beispiel für
b=4
:Schließlich werden, wo
$c
im Rest des Programms angezeigt, die Array-Elemente als ausgewerteteval set -- ....
.Zuletzt werden
${#${(u)@}}
die eindeutigen Elemente in den Positionsparametern gezählt (dh: Gibt es einen Zyklus / gibt es1
s?)Kommentare, die für die 117-Byte-Antwort unten relevant sind.
Herausforderungen, die wir bewältigen müssen:
${#${(M)a:#1}
::#
Entfernt Übereinstimmungen und(M)
kehrt die Übereinstimmung um. Dies wird also auf die Anzahl (${# }
) von1
s im Array erweitert. Leider spielt diese Erweiterung nicht gut mit der Arithmetik für die Schleife, die wir hier verwenden. In diesem Fall könnte möglicherweise ein Byte gespeichert werden.${${:-1}:*a}
: Dies ist der Schnittpunkt zwischen dem Singleton1
und dem Satza
. Dies wird auf die Single erweitert,1
wenn es im Array gefunden wird. Mit dieser Option speichern wir hier ein Zeichen, verlieren aber insgesamt 1 Zeichen, da wir das Hinzufügen des1
s in der letzten Zeile und Spalte bis zum Ende verschieben müssen.quelle
Perl 6 ,
6557 BytesProbieren Sie es online aus!
Es gibt wahrscheinlich eine Möglichkeit, nur das Quadrat selbst auszugeben, aber dies geschieht auf die gleiche Weise wie in der Frage beschrieben, indem die Listen nach ihren Positionen in der ersten Liste sortiert werden, bei denen es sich lediglich um eine Permutation von 1 zu Eingabe-1 handelt. Gibt als Liste von Listen zurück.
Übrigens, es wird viel herumgeschleudert und versucht, einige der nervigen Einschränkungen von Perl 6 zu umgehen, die Sequenzen gegen Arrays und anonyme Variablen betreffen.
Erläuterung:
quelle
Python 2 , 108 Bytes
Probieren Sie es online aus!
quelle
print
anstatt zurückzukehren?05AB1E ,
1916 Bytes-3 Bytes dank @Emigna .
Probieren Sie es online aus (in der Fußzeile wird die 2D-Liste hübsch gedruckt).
Erläuterung:
quelle
LεI<LmI%}ÐΘOÏн<è
für 16 Bytes.<è
dass es genug gewesen wäre, anstatt das, wasUΣXyk
ich hatte.Wolfram Language (Mathematica) , 67 Bytes
Probieren Sie es online aus!
quelle
Pari / GP , 48 Bytes
Probieren Sie es online aus!
quelle
APL (NARS), 29 Zeichen, 58 Bytes
Prüfung:
quelle