Я большой поклонник теории чисел. Большая вещь в теории чисел - модульная арифметика; определение является тогда и только тогда, когда . Забавная вещь, которую нужно сделать, это подняться до степеней, особенно когда модуль является простым числом. В частности, было доказано, что если и относительно простые (не имеют общих общих факторов, кроме ), то существует число такое, что .$a\equiv b\mod m$$m\mid a-b$$a$$m$$1$$e$$a^e\equiv 1\mod m$

Я объясню, что упражнение на примере. Давайте возьмем модуль . Возможный вывод программы или функции будет:$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

Каждая строка представляет собой список степеней первого числа в этой строке: первая строка , что эквивалентно по модулю . Второй ряд квадрата выше - это степени , и так далее, до последнего ряда, которые являются степенями .$3, 3^2, 3^3, \cdots, 3^6$$3,2,6,4,5,1$$7$$2$$1$

Это волшебный квадрат по модулю, потому что:

• Квадрат симметричный; то есть й столбец такой же, как и й ряд.$i$$i$
• Все значения от до появляются как минимум один раз.$1$$m-1$

Ниже приведен единственный другой действительный выход для , начиная с степеней :$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

Соревнование

Создайте функцию или программу, которая при заданном простом числе pвыводит магический квадрат по модулю, то есть квадрат с длинами сторон p-1, так что каждая строка является списком последовательных степеней первого элемента в строке и одинаковой для столбцов. Все числа между 0и pдолжны встречаться, и квадрат может содержать только числа в этом диапазоне.

Входные данные - это число или строка, а выходными данными могут быть ascii, матрица, массив массивов (любой приемлемый формат).

Это код-гольф, поэтому выигрывает самый короткий код.

Желе , 13 10 байт

-3 спасибо Нику Кеннеди

^{По ощущению как повторный код должен быть в гольф-состоянии, но я бы не удавались d это ...}

*€Ṗ%µQƑƇḢị

Попробуйте онлайн! (нижний колонтитул довольно форматирует как сетка)

Как?

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

Древесный уголь , 36 байт

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

Попробуйте онлайн! Ссылка на подробную версию кода. Примечание: конечный пробел. Объяснение:

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

Создание с p-1помощью p-1массива полномочий по 1..p-1индексам 1..p-1( по модулю p).

Ｅ⊟Φη⁼¹№ι¹

Карта над одной из строк, которая имеет ровно одну 1.

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

Расположите строки в порядке, заданном выбранной строкой, и отформатируйте вывод.

J , ^{35 32} 31 байт

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

Попробуйте онлайн!

Wolfram Language (Mathematica) , 46 43 байта

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

Попробуйте онлайн!

-3 благодаря алефале

JavaScript (ES7),  91  86 байт

Эта версия пытается вычислить степени перед применением по модулю и потерпит неудачу при $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)

Попробуйте онлайн!

JavaScript (ES6),  92  87 байт

Эта версия использует модульное возведение в степень для поддержки (намного) более высоких входных значений.

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)

Попробуйте онлайн!

Как?

Нахождение первого ряда

$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

Это работает даже в лексикографическом порядке - что является поведением по умолчанию sort()- потому что:

• $1$
• $1$$1$

Пример:

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

Построение матрицы

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

Эта часть может быть просто написана как:

g(k).map(g)

Zsh , 117 90 байт

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

Попробуйте онлайн! Попробуйте онлайн!

Пусть Бог помилует мою душу. Здесь есть много плохой практики, позвольте мне объяснить, по крайней мере, самого крупного преступника:

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

Пример для 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

Наконец, где $cпоявляется в остальной части программы, элементы массива оцениваются как eval set -- .....

Наконец, ${#${(u)@}}подсчитывает уникальные элементы в позиционных параметрах (т.е. есть ли цикл / есть 1s?)

Комментарии, относящиеся к 117-байтовому ответу ниже.

Проблемы, которые мы должны преодолеть:

• Нет многомерных или вложенных массивов. Вместо этого мы распечатываем строки, когда получаем их в цикле.
• Варианты тестирования, если заданная строка имеет несколько единиц:
  • ${#${(M)a:#1}: :#удаляет совпадение и (M)отменяет совпадение. Таким образом, это расширится до числа ( ${# }) 1s в массиве. К сожалению, это расширение плохо сочетается с арифметикой цикла for, которую мы здесь используем. Если это так, он потенциально может сохранить байт.
  • ${${:-1}:*a}Это пересечение набора между синглтоном 1и набором a. Это расширится до единственного, 1если это будет найдено в массиве. Используя эту опцию, мы сохраняем здесь один символ, но в целом теряем 1, откладывая добавление 1s в последнюю строку и столбец до конца.

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 байт

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

Попробуйте онлайн!

Возможно, есть какой-то способ просто вывести сам квадрат, но он выполняет тот же процесс, описанный в вопросе, сортируя списки по их позициям в первом списке, который представляет собой просто перестановку от 1 до input-1. Возвращает в виде списка списков.

Кстати, есть много шуток, пытающихся обойти некоторые раздражающие ограничения Perl 6, связанные с последовательностями против массивов и анонимными переменными.

Объяснение:

                               $++               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 байт

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]

Попробуйте онлайн!

05AB1E , 19 16 байт

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

-3 байта благодаря @Emigna .

Попробуйте онлайн (нижний колонтитул - просто распечатать 2D-список).

Объяснение:

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 байт

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

Попробуйте онлайн!

Пари / ГП , 48 байт

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

Попробуйте онлайн!

APL (NARS), 29 символов, 58 байтов

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

тест:

  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