Saya penggemar berat teori bilangan. Hal besar dalam teori bilangan adalah aritmatika modular; definisi menjadi jika dan hanya jika m \ mid ab . Hal yang menyenangkan untuk dilakukan adalah meningkatkan kekuatan: terutama ketika modulus adalah bilangan prima. Secara khusus, telah terbukti bahwa jika a dan m relatif prima (tidak berbagi faktor umum selain 1 ) maka ada bilangan e sehingga 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$

Saya akan menjelaskan apa latihan itu dengan sebuah contoh. Mari kita ambil modulus . Output yang mungkin dari program atau fungsi adalah:$m=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

Setiap baris adalah daftar kekuatan angka pertama di baris itu: baris pertama adalah , yang setara dengan modulo . Baris kedua dari persegi di atas adalah kekuatan , dan sebagainya, hingga baris terakhir, yang hanya kekuatan .$3, 3^2, 3^3, \cdots, 3^6$$3,2,6,4,5,1$$7$$2$$1$

Ini adalah kotak modulo ajaib karena:

• Kuadratnya simetris; yaitu, kolom ke- sama dengan baris ke- .$i$$i$
• Semua nilai hingga muncul setidaknya sekali.$1$$m-1$

Di bawah ini adalah satu-satunya output valid lainnya untuk , dimulai dengan pangkat :$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

Tantangan

Buat fungsi atau program yang memberikan poutput utama persegi modulo ajaib, yaitu, persegi dengan panjang sisi p-1, sehingga setiap baris adalah daftar kekuatan berurutan dari elemen pertama di baris, dan sama untuk kolom. Semua angka antara 0dan pharus terjadi, dan kuadrat hanya dapat berisi angka dalam rentang itu.

Input adalah angka atau string, dan output bisa ascii, sebuah matriks, array array (format apa pun yang masuk akal).

Ini kode-golf, jadi kode terpendek menang.

Jelly , 13 10 byte

Terima kasih kepada Nick Kennedy

^{Terasa seperti kode diulang harus adalah golf-bisa, tapi saya telah tidak mengelola d itu ...}

*€Ṗ%µQƑƇḢị

Cobalah online! (footer format cantik sebagai kisi)

Bagaimana?

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

Arang , 36 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Catatan: Ruang tambahan. Penjelasan:

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

Buat p-1dengan p-1array kekuatan 1..p-1untuk indeks 1..p-1(modulo p).

Ｅ⊟Φη⁼¹№ι¹

Memetakan lebih dari satu baris yang memiliki tepat satu 1.

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

Atur ulang baris ke dalam urutan yang diberikan oleh baris yang dipilih dan format output.

J , ^{35 32} 31 byte

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

Cobalah online!

Bahasa Wolfram (Mathematica) , 46 43 byte

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

Cobalah online!

-3 Terima kasih kepada alephalpha

JavaScript (ES7),  91  86 byte

Versi ini mencoba menghitung kekuatan sebelum menerapkan modulo dan akan gagal untuk $p\ge11$ karena kehilangan presisi. Atau menggunakan logika yang sama dengan versi komentar di bawah ini.

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

Cobalah online!

JavaScript (ES6),  92  87 byte

Versi ini menggunakan eksponensial modular untuk mendukung (banyak) nilai input yang lebih tinggi.

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)

Cobalah online!

Bagaimana?

Menemukan baris pertama

$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

Ini berfungsi bahkan dalam urutan leksikografis - yang merupakan perilaku default sort()- karena:

• $1$
• $1$$1$

Contoh:

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

Membangun matriks

$k$$g(k)$$g$$g(k)$

Bagian ini dapat ditulis sebagai:

g(k).map(g)

Zsh , 117 90 byte

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

Cobalah online! Cobalah online!

Semoga Tuhan mengampuni jiwaku. Ada banyak praktik buruk yang dibungkus di sini, izinkan saya menjelaskan pelaku terbesar setidaknya:

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

Contoh untuk 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

Akhirnya, di mana $cmuncul di sisa program, elemen array dievaluasi sebagai eval set -- .....

Terakhir, ${#${(u)@}}menghitung elemen unik dalam parameter posisi (yaitu: apakah ada siklus / ada 1?)

Komentar yang relevan dengan jawaban 117 byte di bawah ini.

Tantangan yang harus kita atasi:

• Tidak ada array multidimensi atau bersarang. Alih-alih, kami mencetak string saat kami membuatnya dalam satu lingkaran.
• Opsi untuk pengujian jika baris yang diberikan memiliki beberapa 1:
  • ${#${(M)a:#1}: :#menghapus pencocokan, dan (M)membalikkan kecocokan. Jadi, ini akan diperluas ke jumlah ( ${# }) dari 1dalam array. Sayangnya ekspansi ini tidak cocok dengan aritmatika untuk loop yang kami gunakan di sini. Jika ya, berpotensi menyimpan satu byte.
  • ${${:-1}:*a}: Ini adalah persimpangan himpunan antara singleton 1dan himpunan a. Ini akan diperluas ke single 1jika ditemukan dalam array. Menggunakan opsi ini, kami menyimpan satu karakter di sini, tetapi kehilangan 1 keseluruhan harus menunda menambahkan 1s di baris dan kolom terakhir sampai akhir.

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 byte

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

Cobalah online!

Mungkin ada beberapa cara untuk hanya mengeluarkan kuadrat itu sendiri, tetapi ini melakukan proses yang sama seperti yang dijelaskan dalam pertanyaan, mengurutkan daftar berdasarkan posisi mereka di daftar pertama yang hanya permutasi 1 ke input-1. Kembali sebagai daftar daftar.

BTW, ada banyak joki di sekitar, mencoba untuk mengatasi beberapa batasan menjengkelkan Perl 6 yang melibatkan urutan vs array, dan variabel anonim.

Penjelasan:

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

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]

Cobalah online!

05AB1E , 19 16 byte

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

-3 byte terima kasih kepada @Emigna .

Cobalah secara online (catatan kaki untuk mencetak daftar 2D dengan cantik).

Penjelasan:

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)

Bahasa Wolfram (Mathematica) , 67 byte

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

Cobalah online!

Pari / GP , 48 byte

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

Cobalah online!

APL (NARS), 29 karakter, 58 byte

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

uji:

  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