Magische Modulo-Quadrate

11

Ich bin ein großer Fan der Zahlentheorie. Eine große Sache in der Zahlentheorie ist die modulare Arithmetik; Die Definition ist genau dann abmodm wenn mab . Eine lustige Sache ist es, die Potenzen zu erhöhen: besonders wenn der Modul eine Primzahl ist. Insbesondere wurde bewiesen, dass, wenn a und m relativ prim sind (außer 1 keine gemeinsamen Faktoren teilen ), eine Zahl e so dass ae1modm .

Ich werde anhand eines Beispiels erklären, was die Übung ist. Nehmen wir einen Modul m=7 . 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 3,32,33,,36 , was 3,2,6,4,5,1 Modulo 7 . Die zweite Reihe des Quadrats oben ist die Potenz von 2 usw. bis zur letzten Reihe, die nur Potenzen von 1 .

Dies ist ein magisches Modulo-Quadrat, weil:

  • Das Quadrat ist symmetrisch; Das heißt, die i te Spalte ist dieselbe wie die i te Zeile.
  • Alle Werte 1 bis m1 erscheinen mindestens einmal.

Unten ist die einzige andere gültige Ausgabe für m=7 , beginnend mit Potenzen von 5 :

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 pein 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 0und pmü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.

vrugtehagel
quelle
Verwandte OEIS-Sequenz: A001918 (der niedrigste gültige Wert für die obere linke Ecke).
Arnauld
2
Ich werde anhand eines Beispiels erklären, was die Übung ist. “ Nicht. Erklären Sie es in seinen eigenen Begriffen und geben Sie dann ein Beispiel zur Veranschaulichung. Ich denke, dass Sie nach einer Matrix fragen, so dass ein primitives Wurzelmodulo und , aber es ist ein großer Aufwand, diese Spezifikation aus der aktuellen Frage zu extrahieren. AA1,1pAi,j=A1,1ijmodp
Peter Taylor
2
@PeterTaylor stimmt, und das meine ich, aber erstens verdirbt das einen Teil des Erkundungsspaßes, und zweitens beruht es auf Wissen über primitive Wurzeln und modulare Arithmetik. Ich wollte, dass diese Frage von einem breiteren Publikum beantwortet werden kann, also versuchte ich einfacher zu erklären, was ich meine.
vrugtehagel

Antworten:

5

Gelee , 13 10 Bytes

-3 danke an Nick Kennedy

Fühlt sich an wie der wiederholten Code sollte sein ist Golf-Lage, aber ich habe es nicht geschafft d es ...

*€Ṗ%µQƑƇḢị

Probieren Sie es online aus! (Fußzeile hübsche Formate als Raster)

Wie?

*€Ṗ%µQƑƇḢị - Link: integer, p
 €         - for each n in [1..p]
*          -   exponentiate with:
  Ṗ        -     pop = [1..p-1]
           - ...i.e [[1^1,1^2,...,1^(p-1)],[2^1,2^2,...,2^(p-1)],...,[....,p^(p-1)]]
   %       - modulo p
    µ      - start a new monadic chain (call that list of lists X)
       Ƈ   - keep those which:
      Ƒ    -   are invariant under:
     Q     -     de-duplicate
        Ḣ  - head
         ị - index into the list of lists X
Jonathan Allan
quelle
Ahha, jetzt fühle ich mich langsam; p danke!
Jonathan Allan
3

Holzkohle , 36 Bytes

≔E…¹θ﹪Xι…¹θIθηE⊟Φη⁼¹№ι¹⪫E§η⊖ι◧IλL⊖θ 

Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Hinweis: Leerzeichen. Erläuterung:

≔E…¹θ﹪Xι…¹θIθη

Erstellen Sie eine p-1durch p-1Anordnung von Potenzen von 1..p-1Indizes 1..p-1(Modulo p).

E⊟Φη⁼¹№ι¹

Ordnen Sie eine der Zeilen zu, die genau eine hat 1.

⪫E§η⊖ι◧IλL⊖θ 

Ordnen Sie die Zeilen in der Reihenfolge der ausgewählten Zeile neu an und formatieren Sie die Ausgabe.

Neil
quelle
2

JavaScript (ES7),  91  86 Byte

Diese 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.p11

f=(p,k)=>(g=k=>[...Array(i=p-1)].map(_=>k**++i%p))(k).sort()[1]>1?g(k).map(g):f(p,-~k)

Probieren Sie es online aus!


JavaScript (ES6),  92  87 Byte

Diese Version verwendet modulare Exponentiation, um (viel) höhere Eingabewerte zu unterstützen.

f=(p,k)=>(g=k=>[...Array(p-1)].map(_=>n=n*k%p,n=1))(k).sort()[1]>1?g(k).map(g):f(p,-~k)

Probieren Sie es online aus!

Wie?

Die erste Reihe finden

Bei wir die Hilfsfunktion , um für zu berechnen .1k<pgak(n)=knmodp1n<p

g = k =>              // k = input
  [...Array(p - 1)]   // generate an array of size p - 1
  .map(_ =>           // for each entry in there:
    n = n * k % p,    //   update n to (n * k) mod p
    n = 1             //   starting with n = 1
  )                   // end of map()

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 .knak(n)=111

g(k).sort()[1] > 1

Dies funktioniert sogar in lexikografischer Reihenfolge - was das Standardverhalten von ist sort()- weil:

  • wenn es mehrere ist, werden sie alle nach vorne bewegt werden , so wie sie es in numerischer Reihenfolge1
  • wenn es nur ein einziges , der 2 nd Wert ist größer als , ganz gleich , ob es wirklich die 2 nd Wert in numerischer Reihenfolge oder nicht111

Beispiel:

Für :p=17

  • für wir: k=1
    • a1=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
    • sortiert nach[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
  • für wir: k=2
    • a2=[2,4,8,16,15,13,9,1,2,4,8,16,15,13,9,1]
    • sortiert nach[1,1,13,13,15,15,16,16,2,2,4,4,8,8,9,9]
  • für wir: k=3
    • a3=[3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1]
    • sortiert nach[1,10,11,12,13,14,15,16,2,3,4,5,6,7,8,9]

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.kg(k)gg(k)

Dieser Teil kann einfach geschrieben werden als:

g(k).map(g)
Arnauld
quelle
.indexOf(1)>p-3spart 3 Bytes .every.
Neil
@ Neil Danke. Aber ich habe nach einer guten Nacht einen kürzeren Weg gefunden. :)
Arnauld
2

Zsh , 117 90 Bytes

b=$1
c=(eval set -- '$[x**'{1..$[b-1]}%b\])
for ((;${#${(u)@}}-b+1;++x))$c
for x;$c&&<<<$@

Probieren 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:

c=(eval set -- '$[x**'{1..$[b-1]}%b\])
                      {1..$[b-1]}        # brace expansion, expands immediately
               '$[x**'           %b\]    # string literals, expand during eval
   eval set --                           # sets the positional parameters
c=(                                   )  # defines c to the words contained

Beispiel für b=4:

c=(eval set -- '$[x**'{1..$[b-1]}%b\])
c=(eval set -- '$[x**'{1..3}%b\]     )                # $[b-1] => 3
c=(eval set -- '$[x**1%b]' '$[x**2%b]' '$[x**3%b]' )  # brace expansion

Schließlich werden, wo $cim Rest des Programms angezeigt, die Array-Elemente als ausgewertet eval set -- .....

Zuletzt werden ${#${(u)@}}die eindeutigen Elemente in den Positionsparametern gezählt (dh: Gibt es einen Zyklus / gibt es 1s?)

Kommentare, die für die 117-Byte-Antwort unten relevant sind.


Herausforderungen, die wir bewältigen müssen:

  • Keine mehrdimensionalen oder verschachtelten Arrays. Stattdessen drucken wir die Zeichenfolgen aus, sobald wir sie in einer Schleife erhalten.
  • Optionen zum Testen, ob eine bestimmte Zeile mehrere Einsen hat:
    • ${#${(M)a:#1}: :#Entfernt Übereinstimmungen und (M)kehrt die Übereinstimmung um. Dies wird also auf die Anzahl ( ${# }) von 1s 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 Singleton 1und dem Satz a. Dies wird auf die Single erweitert, 1wenn es im Array gefunden wird. Mit dieser Option speichern wir hier ein Zeichen, verlieren aber insgesamt 1 Zeichen, da wir das Hinzufügen des 1s in der letzten Zeile und Spalte bis zum Ende verschieben müssen.
f(){ # f [element] [modular base], puts powers up to n-2 into array $a
    a=()
    for i ({1..$[$2-2]})
        a+=($[$1**i%$2])
}
a=(1)                     # put 1 in a to force first loop iteration
for ((;${${:-1}:*a};))    # test for 1 in array $a
    f $[++x] $1           # increment x, iterate through all elements mod $1
for y ($a 1){             # for all elements in the [last array, 1]
    f $y $1               # put that row in $a
    <<<$a\ 1              # print out $a with 1 appended (space-delimited string)
}
GammaFunktion
quelle
1

Perl 6 , 65 57 Bytes

{.[|.first(*.Set+2>$_)]}o{.&{@=(($++X**1..^$_)X%$_)xx$_}}

Probieren 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:

                               $++               xx$_    # Map 0 to i-1 to
                              (   X**1..^$_)             # n, n^2, n^3... n^(i-1)
                             (              X%$_)        # All modulo i
{                      }o{.&{                        }}  # Pass to the next function
 .[                   ]    # Index into that list of lists
   |.first(          )     # The list of the first list that
           *.Set+2>$_        # Has all the elements in the range 1 to i-1
Scherzen
quelle
1

Python 2 , 108 Bytes

def f(p):R=range(1,p);return[m for m in[[[j**(k*i)%p for i in R]for k in R]for j in R]if sorted(m[0])==R][0]

Probieren Sie es online aus!

Chas Brown
quelle
1
Kannst du nicht tun, printanstatt zurückzukehren?
Verkörperung der Unwissenheit
1

05AB1E , 19 16 Bytes

LεI<LmI%}ÐΘOÏн<è

-3 Bytes dank @Emigna .

Probieren Sie es online aus (in der Fußzeile wird die 2D-Liste hübsch gedruckt).

Erläuterung:

L          # Create a list in the range [1, (implicit) input]
 ε         # Map each number `y` in the list to:
  I<L      #  Create a list in the range [1, input-1]
     m     #  Get number `y` to the power of each number in this list
      I%   #  Take modulo-input on each number
         # After the map: triplicate this modified matrix
   ΘO      # Get the amount of 1s in each row
     Ï     # And only leave the rows with exactly one 1
      н    # Then only leave the first row which contains a single 1
       <   # Decrease each value by 1 to make it 0-indexed
        è  # And index each into the rows of the modified matrix to create a new matrix
           # (which is output implicitly as result)
Kevin Cruijssen
quelle
1
LεI<LmI%}ÐΘOÏн<èfür 16 Bytes.
Emigna
@ Emigna Danke! Ich wusste nicht, dass es genug gewesen wäre, anstatt das, was UΣXykich hatte.
Kevin Cruijssen
0

APL (NARS), 29 Zeichen, 58 Bytes

{k←⍵∣⍺*⍳⍵-1⋄⊃{m∣k*⍵}¨⍳¯1+m←⍵}

Prüfung:

  f←{k←⍵∣⍺*⍳⍵-1⋄⊃{m∣k*⍵}¨⍳¯1+m←⍵}
  3 f 7
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
  5 f 7
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 
RosLuP
quelle