Jestem wielkim fanem teorii liczb. Wielką rzeczą w teorii liczb jest arytmetyka modułowa; definicja jest wtedy i tylko wtedy, gdy m \ mid ab . Zabawne jest podnoszenie do potęg: szczególnie, gdy moduł jest liczbą pierwszą. W szczególności udowodniono, że jeśli a i m są względnie pierwsze (nie mają wspólnych czynników oprócz 1 ), to istnieje liczba e taka, że a ^ e \ equiv 1 \ mod m$a\equiv b\mod m$$m\mid a-b$$a$$m$$1$$e$$a^e\equiv 1\mod m$ .

Wyjaśnię, na czym polega ćwiczenie. Weźmy moduł $m=7$ . Możliwe wyjście programu lub funkcji to:

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

Każdy rząd jest listą potęg pierwszego numeru w tym rzędzie: pierwszy rząd to $3, 3^2, 3^3, \cdots, 3^6$ , co odpowiada $3,2,6,4,5,1$ moduł $7$ . Drugi rząd kwadratu powyżej to potęgi $2$ itd., Aż do ostatniego rzędu, które są tylko potęgami $1$ .

To magiczny kwadrat modulo, ponieważ:

• Kwadrat jest symetryczny; to znaczy, $i$ ta kolumna jest taka sama jak $i$ ty wiersz.
• Wszystkie wartości od $1$ do $m-1$ pojawiają się co najmniej raz.

Poniżej znajduje się jedyna ważna moc wyjściowa dla , zaczynając od mocy :$m=7$$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

Wyzwanie

Utwórz funkcję lub program, który podając liczbę pierwszą pgeneruje magiczny kwadrat modulo, to znaczy kwadrat o długości boków p-1, tak że każdy rząd jest listą kolejnych mocy pierwszego elementu w rzędzie i taki sam dla kolumn. Wszystkie liczby pomiędzy 0i pmuszą wystąpić, a kwadrat może zawierać tylko liczby z tego zakresu.

Dane wejściowe to liczba lub ciąg znaków, a dane wyjściowe mogą być ascii, macierzą, tablicą tablic (dowolny rozsądny format).

To jest golf golfowy, więc wygrywa najkrótszy kod.

Galaretka , 13 10 bajtów

-3 dzięki Nickowi Kennedy'emu

^{Odczuwana jak powtarzanego kodu powinno być to golf-stanie, ale już nie udało byłyby to ...}

*€Ṗ%µQƑƇḢị

Wypróbuj online! (stopka ładna-formaty jako siatka)

W jaki sposób?

*€Ṗ%µ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

Węgiel drzewny , 36 bajtów

≔Ｅ…¹θ﹪Ｘι…¹θＩθηＥ⊟Φη⁼¹№ι¹⪫Ｅ§η⊖ι◧ＩλＬ⊖θ 

Wypróbuj online! Link jest do pełnej wersji kodu. Uwaga: końcowe miejsce. Wyjaśnienie:

≔Ｅ…¹θ﹪Ｘι…¹θＩθη

Tworzenie p-1przez p-1tablicę uprawnień 1..p-1do indeksów 1..p-1(modulo p).

Ｅ⊟Φη⁼¹№ι¹

Mapuj jeden z wierszy, który ma dokładnie jeden 1.

⪫Ｅ§η⊖ι◧ＩλＬ⊖θ 

Zmień kolejność wierszy w kolejności podanej przez wybrany wiersz i sformatuj dane wyjściowe.

J , ^{35 32} 31 bajtów

[:(/:0/:@{]\:#@~."1)]|^/~@}.@i.

Wypróbuj online!

Wolfram Language (Mathematica) , 46 43 bajtów

Mod[PrimitiveRoot@#^Array[1##&,{#,#}-1],#]&

Wypróbuj online!

-3 dzięki alephalpha

JavaScript (ES7),  91  86 bajtów

$p\ge11$

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

Wypróbuj online!

JavaScript (ES6),  92  87 bajtów

Ta wersja wykorzystuje potęgowanie modułowe do obsługi (znacznie) wyższych wartości wejściowych.

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)

Wypróbuj online!

W jaki sposób?

Znajdowanie pierwszego rzędu

$1\le k<p$$g$$a_k(n)=k^n\bmod p$$1\le n<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()

$k$$n$$a_k(n)=1$$1$

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

Działa to nawet w kolejności leksykograficznej - co jest domyślnym zachowaniem sort()- ponieważ:

• $1$
• $1$$1$

Przykład:

$p=17$

• $k=1$
  • $a_1=[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]$
  • $[ 1, \color{red}1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]$
• $k=2$
  • $a_2=[ 2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 15, 13, 9, 1 ]$
  • $[ 1, \color{red}1, 13, 13, 15, 15, 16, 16, 2, 2, 4, 4, 8, 8, 9, 9 ]$
• $k=3$
  • $a_3=[ 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1 ]$
  • $[ 1, \color{red}{10}, 11, 12, 13, 14, 15, 16, 2, 3, 4, 5, 6, 7, 8, 9 ]$

Budowanie macierzy

$k$$g(k)$$g$$g(k)$ aby zbudować rzędy macierzy.

Tę część można po prostu napisać jako:

g(k).map(g)

Zsh , 117 90 bajtów

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

Wypróbuj online! Wypróbuj online!

Niech Bóg zlituje się nad moją duszą. Jest tu wiele złych praktyk, pozwól mi wyjaśnić przynajmniej największego przestępcę:

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

Przykład dla 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

Wreszcie, gdzie $cpojawia się w pozostałej części programu, elementy tablicy są oceniane jakoeval set -- .... .

Wreszcie, ${#${(u)@}}liczy unikalne elementy parametrów pozycyjnych (tj .: czy jest cykl / czy są 1?)

Komentarze dotyczące 117-bajtowej odpowiedzi poniżej.

Wyzwania, które musimy pokonać:

• Brak wielowymiarowych lub zagnieżdżonych tablic. Zamiast tego drukujemy ciągi, gdy otrzymujemy je w pętli.
• Opcje testowania, jeśli dany wiersz ma wiele 1:
  • ${#${(M)a:#1}: :#usuwa dopasowanie i (M)odwraca dopasowanie. To zwiększy liczbę ( ${# }) 1s do tablicy. Niestety, to rozszerzenie nie działa dobrze z arytmetyką pętli, której tutaj używamy. Jeśli tak, może potencjalnie zaoszczędzić bajt.
  • ${${:-1}:*a}: Jest to przecięcie zestawu między singletonem 1a zestawem a. Rozwinie się do singla, 1jeśli zostanie znaleziony w tablicy. Korzystając z tej opcji, zapisujemy tutaj jedną postać, ale tracimy 1 ogólną konieczność odłożenia dodawania 1s w ostatnim rzędzie i kolumnie do końca.

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)
}

Perl 6 , 65 57 bajtów

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

Wypróbuj online!

Prawdopodobnie jest jakiś sposób, aby wyprowadzić sam kwadrat, ale robi to ten sam proces opisany w pytaniu, sortując listy według ich pozycji na pierwszej liście, która jest tylko permutacją 1 na input-1. Zwraca jako listę list.

BTW, dużo się kręci, próbuje obejść niektóre irytujące ograniczenia Perla 6, obejmujące sekwencje kontra tablice i anonimowe zmienne.

Wyjaśnienie:

                               $++               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

Python 2 , 108 bajtów

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]

Wypróbuj online!

05AB1E , 19 16 bajtów

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

-3 bajty dzięki @Emigna .

Wypróbuj online (stopka służy do wydrukowania listy 2D).

Wyjaśnienie:

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)

Wolfram Language (Mathematica) , 67 bajtów

(s=Thread@Mod[x^#&/@(x=Range[#-1]),#])[[#&@@Select[s,Sort@#==x&]]]&

Wypróbuj online!

Pari / GP , 48 bajtów

n->lift(matrix(n-1,n-1,i,j,znprimroot(n)^(i*j)))

Wypróbuj online!

APL (NARS), 29 znaków, 58 bajtów

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

test:

  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