Soy un gran admirador de la teoría de números. Una gran cosa en la teoría de números es la aritmética modular; la definición es $a\equiv b\mod m$ si y solo si $m\mid a-b$ . Una cosa divertida es elevar a los poderes: especialmente cuando el módulo es un número primo. En particular, se ha demostrado que si $a$ y $m$ son relativamente primos (no comparten factores comunes además de $1$ ), entonces existe un número $e$ tal que $a^e\equiv 1\mod m$ .

Explicaré cuál es el ejercicio con un ejemplo. Tomemos un módulo $m=7$ . Una posible salida del programa o función sería:

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

Cada fila es una lista de las potencias del primer número en esa fila: la primera fila es $3, 3^2, 3^3, \cdots, 3^6$ , que es equivalente a $3,2,6,4,5,1$ módulo $7$ . La segunda fila del cuadrado de arriba son las potencias de $2$ , etcétera, hasta la última fila, que son solo potencias de $1$ .

Este es un módulo cuadrado mágico porque:

• El cuadrado es simétrico; que es, la $i$ ésima columna es el mismo que el $i$ -ésimo renglón.
• Todos los valores $1$ a $m-1$ aparecen al menos una vez.

A continuación se muestra la única otra salida válida para , comenzando con potencias 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

El reto

Cree una función o programa que, dado un primo, pgenere un cuadrado de módulo mágico, es decir, un cuadrado con longitudes laterales p-1, de modo que cada fila sea una lista de las potencias consecutivas del primer elemento de la fila, y lo mismo para las columnas. Todos los números entre 0y pdeben aparecer, y el cuadrado solo puede contener números en ese rango.

La entrada es un número o una cadena, y la salida puede ser ascii, una matriz, una matriz de matrices (cualquier formato razonable).

Este es el código de golf, por lo que gana el código más corto.

Jalea , 13 10 bytes

-3 gracias a Nick Kennedy

^{Se siente como el código repetido debe ser es capaz de golf, pero me han no logró d que ...}

*€Ṗ%µQƑƇḢị

Pruébalo en línea! (pie de página bonitos formatos como una cuadrícula)

¿Cómo?

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

Carbón , 36 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Nota: espacio final. Explicación:

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

Crear una p-1por p-1serie de potencias de 1..p-1los índices 1..p-1(módulo p).

Ｅ⊟Φη⁼¹№ι¹

Mapa sobre una de las filas que tiene exactamente una 1.

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

Reorganice las filas en el orden dado por la fila seleccionada y formatee la salida.

J , ^{35 32} 31 bytes

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

Pruébalo en línea!

Wolfram Language (Mathematica) , 46 43 bytes

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

Pruébalo en línea!

-3 gracias a alephalpha

JavaScript (ES7),  91  86 bytes

Esta versión intenta calcular los poderes antes de aplicar el módulo y fallará para debido a la pérdida de precisión. De lo contrario, utiliza la misma lógica que la versión comentada a continuación.$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)

Pruébalo en línea!

JavaScript (ES6),  92  87 bytes

Esta versión utiliza exponenciación modular para admitir (mucho) valores de entrada más altos.

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)

Pruébalo en línea!

¿Cómo?

Encontrar la primera fila

Dado , usamos la función auxiliar para calcular para .$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()

Buscamos tal que solo haya un valor tal que . Hacemos eso ordenando la matriz y probando si el ^2º elemento es mayor que .$k$$n$$a_k(n)=1$$1$

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

Esto funciona incluso en orden lexicográfico, que es el comportamiento predeterminado de sort(), porque:

• si hay varios , todos se moverán al frente como lo harían en orden numérico$1$
• Si sólo hay un único , la 2 ^nd valor será mayor que , no importa si es realmente el 2 ^nd valor en orden numérico o no$1$$1$

Ejemplo:

Para :$p=17$

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

Construyendo la matriz

Una vez que hemos encontrado , invocamos nuevamente (para recuperar la versión no ordenada de la matriz) e invocamos en cada elemento de para construir las filas de la matriz.$k$$g(k)$$g$$g(k)$

Esta parte se puede escribir simplemente como:

g(k).map(g)

Zsh , 117 90 bytes

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

Pruébalo en línea! Pruébalo en línea!

Que Dios tenga piedad de mi alma. Aquí hay muchas malas prácticas, déjenme explicar al menos al mayor infractor:

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

Ejemplo para 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

Finalmente, donde $caparece en el resto del programa, los elementos de la matriz se evalúan como eval set -- .....

Por último, ${#${(u)@}}cuenta los elementos únicos en los parámetros posicionales (es decir, ¿hay un ciclo / hay 1s?)

Comentarios relevantes a la respuesta de 117 bytes a continuación.

Retos que debemos superar:

• No hay matrices multidimensionales o anidadas. En su lugar, imprimimos las cadenas a medida que las hacemos en un bucle.
• Opciones para probar si una fila dada tiene varios 1:
  • ${#${(M)a:#1}: :#elimina la coincidencia e (M)invierte la coincidencia. Entonces, esto se expandirá al número ( ${# }) de 1s en la matriz. Desafortunadamente, esta expansión no funciona bien con la aritmética para el bucle que usamos aquí. Si lo hiciera, podría potencialmente salvar un byte.
  • ${${:-1}:*a}: Esta es la intersección del conjunto entre el singleton 1y el conjunto a. Esto se expandirá al single 1si se encuentra en la matriz. Usando esta opción, guardamos un personaje aquí, pero perdemos 1 en general teniendo que posponer la adición de la 1s en la última fila y columna hasta el final.

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 bytes

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

Pruébalo en línea!

Probablemente haya alguna forma de generar el cuadrado en sí, pero esto hace el mismo proceso descrito en la pregunta, ordenando las listas por sus posiciones en la primera lista que es solo una permutación de 1 a input-1. Devuelve como una lista de listas.

Por cierto, hay muchas maniobras, tratando de sortear algunas de las limitaciones molestas de Perl 6 que implican secuencias frente a matrices y variables anónimas.

Explicación:

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

Pruébalo en línea!

05AB1E , 19 16 bytes

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

-3 bytes gracias a @Emigna .

Pruébelo en línea (el pie de página es imprimir una bonita lista 2D).

Explicación:

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 bytes

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

Pruébalo en línea!

Pari / GP , 48 bytes

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

Pruébalo en línea!

APL (NARS), 29 caracteres, 58 bytes

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

prueba:

  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