Codegolf — Постройте Примитивный Корневой Диффузор

Введение

Если в комнате голые параллельные стены, это может создавать неприятные повторяющиеся акустические отражения (эхо). Диффузор — это устройство, установленное на стене, которое создает блочную поверхность разной высоты. Это приводит к разбиению отраженного звука на множество более мелких отражений (каждое с разной временной задержкой). Считается, что акустическое качество помещения значительно улучшается.

Примитивный корневой диффузор

В примитивном корневом диффузоре используется сетка из столбиков (обычно деревянных), каждая из которых имеет разную высоту (чтобы получить разное время задержки отражения). Высоты столбов выбираются в соответствии с последовательными степенями первородного корня G по модулю N (простое число).

Здесь Несколько фотографий примитивного корневого диффузора.

Задача

Вы должны написать программу или функцию, которая принимает простое число N > 2 в качестве единственного входного параметра. Затем он должен выбрать примитивный корень из N. G является примитивным корнем из N, если последовательные степени G по модулю N генерируют все целые числа от 1 до N-1. Более формальное определение примитивных корней можно найти в Статья в Википедии.

Затем ваш код должен поместить эти последовательные степени в массив (или матрицу) X на Y. Поскольку мы хотим повесить его на стену, диффузор должен быть удобной формы — как можно ближе к квадратной. Количество записей в массиве будет N-1, поэтому его размеры X и Y следует выбирать так, чтобы X*Y = N-1, а X был близок к Y, но не равен ему (в частности, X и Y взаимно просты). . Для удобства отображения горизонтальный размер должен быть больше вертикального.

Порядок размещения последовательных степеней G (по модулю N) должен начинаться с одного угла массива, затем проходить по диагонали через массив, повторяясь в обоих направлениях, пока все позиции массива не будут заполнены. Затем функция должна вернуть этот массив или вывести его на стандартный вывод, в зависимости от того, что вы предпочитаете.

Мы не будем интересоваться единицами измерения, используемыми для обрезки столбов по длине; мы предположим, что единицы измерения подходят для диапазона звуковых частот, которые мы хотим рассеивать, и будем придерживаться целых чисел.

Есть онлайн-калькулятор, на случай, если вы захотите проверить свою работу. Однако в настоящее время сайт, похоже, недоступен.

Пример

Предположим, мы выбрали N = 41. Наша программа должна выбрать один из примитивных корней числа N, а именно [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35]. Предположим, наша программа выбирает наименьший примитивный корень G = 6.

Затем наша программа выбирает квадратные размеры X,Y для массива так, что X*Y = N-1. Очевидный выбор — X=8 и Y=5.

Затем наша программа заполняет массив последовательными степенями G по модулю N (начиная с G^0), перемещаясь по диагонали. Затем программа возвращает/печатает массив:

 
 
 
 1   12  33  26  16  7   10  9   34
31  2   24  29  15  32  14  20  18
36  25  4   11  21  30  27  28  3
6   35  13  8   22  5   23  17  19
 
 
 
 

Обратите внимание, что оно начинается с 6^0 по модулю 41 = 1, затем 6^1 по модулю 41 = 6, затем 6^2 по модулю 41 = 36, затем 6^3 по модулю 41 = 11 и т. д.

Чтобы уточнить, последовательность степеней 6 по модулю 41 такова:

Другой пример

Н = 31

Предполагая, что программа выбирает G = 11, X = 6, Y = 5, результат будет следующим:

Третий пример

Н = 37

Предполагая, что программа выбирает G = 2, X = 9, Y = 4, результат будет следующим:

Подсчет очков

Стандартные правила гольфа с кодом: побеждает наименьшее количество байтов кода, дающих правильный результат!

#код-гольф #теория чисел #простые числа

Математика 158

Не нужны пробелы:

 
 
 
 
 
 
 
 
 
 b∘|¨ 
 
 
 
 
 
 
 
 
 

Последний выглядит так...

Хаскелл, 220 213 207 201 194 182 178

это функция, которая возвращает матрицу (список списков ⍳≢⍵ ).

он работает, вычисляя минимально возможное ⍵@(...)⊢ , the closet coprime (...)⍴0 и b← and defines a recursive function that given the indices of a slot in the grid returns the Integer in it, and maps this function over all slots.

пример вывода:

MATLAB с символьным набором инструментов — 199 198 байт

Минимизировано:

Расширено:

Примеры результатов

Благородное усилие для MATLAB (даже если я сам так говорю), языка, который требует a← because it doesn't understand (≠/¨⌿⊢) . :П

Несколько примечаний:

• рутина использует тот факт, что ⍸⍵= for ∘.×⍨⍳⍵ строго положительный для положительного {a⊃⍨⊃⍋+/↑a←(≠/¨⌿⊢)⍸⍵=∘.×⍨⍳⍵}≢⍵ , and that {⍵@(b∘|¨2⌿¨⍳≢⍵)⊢(b←{a⊃⍨⊃⍋+/↑a←(≠/¨⌿⊢)⍸⍵=∘.×⍨⍳⍵}≢⍵)⍴0} является лишь примитивным корнем ⊃ if the number 1=≢⍵~⍨⍳⍺ появляется ровно два раза в последовательности
• процедура использует тот факт, что ряд (⍵∘{...}¨⌿⊢) can only equal ↓ для позитива ⍵ if ⍵| и ∘.*⍨⍳⍵-1 . Also, the fact that {{⍵@(b∘|¨2⌿¨⍳≢⍵)⊢(b←{a⊃⍨⊃⍋+/↑a←(≠/¨⌿⊢)⍸⍵=∘.×⍨⍳⍵}≢⍵)⍴0}⊃(⍵∘{1=≢⍵~⍨⍳⍺}¨⌿⊢)↓⍵|∘.*⍨⍳⍵-1} и ⍵ are coprime iff ⎕IO←0 .

Кроме этого, я не смог найти никаких оптимизаций для конкретных проблем.

MATLAB's {{⍵@(b∘|¨2⌿¨⍳≢⍵)⊢(b←{a⊃⍨⊃⍋+/↑a←(≠/¨⌿⊢)⍸⍵=∘.×⍨⍳⍵}≢⍵)⍴0}⊃(⍵∘{1=≢⍵~⍨⍳⍺}¨⌿⊢)↓⍵|∘.*⍨⍳⍵-1} function is particularly painful since I use it 3 times, and it takes a minimum of 8 characters per invocation, as opposed to 3 (i.e. 41 [[1, 27L, 32L, 3L, 40L, 14, 9L, 38L], [18L, 35, 2L, 13L, 23L, 6L, 39, 28L], [37L, 15L, 36, 29L, 4L, 26L, 5L, 12L], [10L, 24L, 33L, 30, 31L, 17L, 8L, 11L], [16L, 22L, 20L, 7L, 25, 19L, 21L, 34L]] ) практически для любого другого существующего языка программирования. N=input() w=n=G=N-1 Z=range(n) while sorted(G**x%N-1for x in Z)!=Z:G-=1 while w*w/n|n%w|1-all(w%i|n/w%i for i in Z[2:]):w-=1 n/=w a=[] for x in Z:a+=[n*[0]];a[x%w][x%n]=G**x%N print a[:w] (which in every other language is either C = @(N): M = N-1; y = 1:N; p = y-1; t = @(x) eval( sym(x).^p % N ); L = fix( l = M./y ); k = y( l == L.*gcd(y,L) & y > M^.5 )(1); C = ones( l = M/k, k ); C( p%k*l + p%l + 1 ) = t(y( x -> sum( t(x) < 2 ) < 3 )(1)); или -> is also painful.

В свете этих недостатков я также предлагаю следующее решение:

Фантазийный MATLAB – гораздо меньше байтов

Python 2: 232 217 212 208 201 198 194 192 187 байт.

Теперь он выбирает самый большой корень вместо самого маленького, поэтому выходные данные будут другими.

Пример:АПЛ (дзайма/APL)

, 84 байта

Попробуйте на repl.it! gcd(x,y) == 1 (0-indexing).

Использование y .

dfn, который принимает входные данные как длинное целое число и возвращает матрицу длинных целых чисел для первого примитивного корня

Размещено на repl.it, поскольку tio не обновляется до последней версии dzaima/APL. Кнопка запуска запускает все тестовые примеры.

x

gcd(floor(x),y) == 1 create a power table for 0..n-1

floor(x) == x modulo that by the input y

floor(x)*gcd(floor(x),y) convert to list of lists

x >= 2 tacit function, filter lists where:

1 numbers from 1 to n-1 are present

N take the first one

j and do the following:

Объяснение

j do the following with the length of the first list:

k = 0..N-1 multiplication table of 1..length

mod( j^k, N ) coordinates at which product = length

a = b(c)(d) remove the ones which create squares

a1 = b(c); a = a1(d); assign the final coordinates to primroot(37) ans = 1 12 33 26 16 7 10 9 34 31 2 24 29 15 32 14 20 18 36 25 4 11 21 30 27 28 3 6 35 13 8 22 5 23 17 19 primroot(41) ans = 1 14 32 38 40 27 9 3 18 6 2 28 23 35 39 13 37 26 36 12 4 15 5 29 10 17 33 11 31 24 8 30 16 19 20 34 25 22 21 7 primroot(31) ans = 1 6 5 30 25 26 16 3 18 15 28 13 8 17 9 23 14 22 4 24 20 27 7 11 2 12 10 29 19 21 primroot(113) ans = 1 48 44 78 15 42 95 40 112 65 69 35 98 71 18 73 106 3 31 19 8 45 13 59 7 110 82 94 105 68 100 54 49 92 9 93 57 24 22 39 64 21 104 20 56 89 91 74 109 34 50 27 53 58 72 66 4 79 63 86 60 55 41 47 28 101 102 37 81 46 61 103 85 12 11 76 32 67 52 10 30 84 77 80 111 17 25 70 83 29 36 33 2 96 88 43 16 90 26 5 14 107 51 75 97 23 87 108 99 6 62 38

function C = primroot( N ) M = N-1; y = 1:N; p = y-1; t = @(x) eval( mod( sym(x).^p, N ) ); l = M./y; L = fix( l ); k = y( l == L.*gcd(y,L) & y > M^.5 ); k = k(1); l = M/k; C = eye( l, k ); g = y(arrayfun( @(x) sum( t(x) < 2 ) < 3, y )); C(mod(p,k)*l+mod(p,l)+1) = t(g(1)); index of coordinate with highest sum

function C=F(N),M=N-1;y=1:N;p=y-1;t=@(x)eval(mod(sym(x).^p,N));l=M./y;L=fix(l);k=y(l==L.*gcd(y,L)&y>M^.5);k=k(1);l=M/k;C=eye(l,k);g=y(arrayfun(@(x)sum(t(x)<2)<3,y));C(mod(p,k)*l+mod(p,l)+1)=t(g(1)); take that coordinate from *Main> mapM_ print $ f 13 -- used for printing the matrix line-by-lie [1,5,12,8] [3,2,10,11] [9,6,4,7] *Main> mapM_ print $ f 43 [1,21,11,16,35,4,41] [37,3,20,33,5,19,12] [36,25,9,17,13,15,14] [42,22,32,27,8,39,2] [6,40,23,10,38,24,31] [7,18,34,26,30,28,29] *Main> mapM_ print $ f 37 [1,12,33,26,16,7,10,9,34] [31,2,24,29,15,32,14,20,18] [36,25,4,11,21,30,27,28,3] [6,35,13,8,22,5,23,17,19]

k assign that to b

j create a grid of zeroes of that size

g assign the first list at the following indices:

Int 1..length

f n=[map(x%)[0..j-1]|x<-[0..i-1]]where j=[x|x<-l,x^2>n,(n-1)&x<1,gcd(n`div`x)x<2]!!0;i=n`div`j;0%0=1;a%b=([x|x<-l,all((>1).(&n).(x^))l]!!0*(a-1)&i%((b-1)&j))&n;l=[1..n-2] (&)=mod each replicated twice

f@n_ := (m = Mod; {p, q} = Sort[{y-x, x, y} /. Solve[x*y==n - 1 && x~GCD~y == 1 < x < y, Integers]][[1, 2 ;;]]; (g[#~m~p + 1, #~m~q + 1] = m[PrimitiveRoot@n^#, n]) & /@ (Range@n - 1); g~ Array~{p, q}) mod b(vectorizes)

Функция поиска размеров (любезно предоставлено ngn):