Je suis un grand fan de la théorie des nombres. Une grande chose dans la théorie des nombres est l'arithmétique modulaire; la définition étant si et seulement si . Une chose amusante à faire est d'augmenter les pouvoirs: surtout lorsque le module est un nombre premier. En particulier, il a été prouvé que si et sont relativement premiers (ne partagent aucun facteur commun à part ) alors il existe un nombre tel que .$a\equiv b\mod m$$m\mid a-b$$a$$m$$1$$e$$a^e\equiv 1\mod m$

Je vais expliquer ce qu'est l'exercice par un exemple. Prenons un module . Une sortie possible du programme ou de la fonction serait:$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

Chaque ligne est une liste des puissances du premier nombre de cette ligne: la première ligne est $3, 3^2, 3^3, \cdots, 3^6$ , ce qui équivaut à $3,2,6,4,5,1$ module $7$ . La deuxième rangée du carré ci-dessus correspond aux puissances de $2$ , etc., jusqu'à la dernière rangée, qui ne sont que des puissances de $1$ .

C'est un carré modulo magique car:

• Le carré est symétrique; c'est-à-dire que la $i$ ème colonne est la même que la $i$ ème ligne.
• Toutes les valeurs $1$ à $m-1$ apparaissent au moins une fois.

Voici la seule autre sortie valide pour , en commençant par des puissances de :$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

Le défi

Créez une fonction ou un programme qui donne un nombre premier pun carré modulo magique, c'est-à-dire un carré avec des longueurs latérales p-1, de sorte que chaque ligne est une liste des puissances consécutives du premier élément de la ligne, et la même chose pour les colonnes. Tous les nombres entre 0et pdoivent apparaître, et le carré ne peut contenir que des nombres dans cette plage.

L'entrée est un nombre ou une chaîne, et la sortie peut être ascii, une matrice, un tableau de tableaux (tout format raisonnable).

C'est le code-golf, donc le code le plus court l'emporte.

Gelée , 13 10 octets

-3 merci à Nick Kennedy

^{Feels comme le code répété devrait être est en mesure de golf, mais j'ont ne sont pas parvenus d elle ...}

*€Ṗ%µQƑƇḢị

Essayez-le en ligne! (joli pied de page sous forme de grille)

Comment?

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

Fusain , 36 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Remarque: Espace de fin. Explication:

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

Créez un p-1par p-1tableau de puissances d' 1..p-1indices 1..p-1(modulo p).

Ｅ⊟Φη⁼¹№ι¹

Mappez sur l'une des lignes qui en a exactement une 1.

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

Réorganisez les lignes dans l'ordre donné par la ligne sélectionnée et formatez la sortie.

J , ^{35 32} 31 octets

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

Essayez-le en ligne!

Wolfram Language (Mathematica) , 46 43 octets

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

Essayez-le en ligne!

-3 grâce à alephalpha

JavaScript (ES7),  91  86 octets

Cette version tente de calculer les puissances avant d'appliquer le modulo et échouera pour $p\ge11$ cause d'une perte de précision. Il utilise par ailleurs la même logique que la version commentée ci-dessous.

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

Essayez-le en ligne!

JavaScript (ES6),  92  87 octets

Cette version utilise l'exponentiation modulaire pour prendre en charge des valeurs d'entrée (beaucoup) plus élevées.

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)

Essayez-le en ligne!

Comment?

Trouver la première ligne

Étant donné $1\le k<p$ , nous utilisons la fonction d'aide $g$ pour calculer $a_k(n)=k^n\bmod p$ pour $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()

Nous cherchons $k$ tel qu'il n'y a qu'une seule valeur $n$ telle que $a_k(n)=1$ . Nous faisons cela en triant le tableau et en testant si le 2^eélément est supérieur à$1$ .

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

Cela fonctionne même dans l'ordre lexicographique - qui est le comportement par défaut de sort()- car:

• $1$
• s'il n'y a qu'un seul $1$$1$

Exemple:

Pour $p=17$

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

Construire la matrice

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

Cette partie peut simplement s'écrire:

g(k).map(g)

Zsh , 117 90 octets

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

Essayez-le en ligne! Essayez-le en ligne!

Que Dieu ait pitié de mon âme. Il y a beaucoup de mauvaises pratiques ici, permettez-moi d'expliquer au moins le plus gros délinquant:

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

Exemple pour 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

Enfin, là où $capparaît dans le reste du programme, les éléments du tableau sont évalués comme eval set -- .....

Enfin, ${#${(u)@}} compte les éléments uniques dans les paramètres positionnels (ie: y a-t-il un cycle / y en a-t-il 1?)

Commentaires relatifs à la réponse de 117 octets ci-dessous.

Les défis que nous devons surmonter:

• Pas de tableaux multidimensionnels ou imbriqués. Au lieu de cela, nous imprimons les chaînes au fur et à mesure que nous les mettons en boucle.
• Options pour tester si une ligne donnée a plusieurs 1:
  • ${#${(M)a:#1}: :#supprime la correspondance et (M)inverse la correspondance. Donc, cela va s'étendre au nombre ( ${# }) de 1s dans le tableau. Malheureusement, cette extension ne fonctionne pas bien avec l'arithmétique de boucle que nous utilisons ici. Si c'était le cas, cela pourrait potentiellement sauver un octet.
  • ${${:-1}:*a}: Il s'agit de l'intersection de l'ensemble entre le singleton 1et l'ensemble a. Cela s'étendra au single 1s'il est trouvé dans le tableau. En utilisant cette option, nous enregistrons un caractère ici, mais perdons 1 dans l'ensemble en retardant l'ajout des 1s dans la dernière ligne et colonne jusqu'à la fin.

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 octets

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

Essayez-le en ligne!

Il y a probablement un moyen de simplement sortir le carré lui-même, mais cela fait le même processus que celui décrit dans la question, en triant les listes par leurs positions dans la première liste qui n'est qu'une permutation de 1 à input-1. Renvoie sous forme de liste de listes.

BTW, il y a beaucoup de jockey autour, essayant de contourner certaines limitations ennuyeuses de Perl 6 impliquant des séquences vs des tableaux et des variables anonymes.

Explication:

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

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]

Essayez-le en ligne!

05AB1E , 19 16 octets

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

-3 octets grâce à @Emigna .

Essayez-le en ligne (le pied de page consiste à imprimer la liste 2D).

Explication:

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 octets

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

Essayez-le en ligne!

Pari / GP , 48 octets

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

Essayez-le en ligne!

APL (NARS), 29 caractères, 58 octets

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

tester:

  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