# Magical Modulo Squares

I'm a big fan of number theory. A big thing in number theory is modular arithmetic; the definition being $$\a\equiv b\mod m$/extract_tex] if and only if $$\m\mid a-b$$/extract_tex]. A fun thing to do is raising to powers: especially when the modulus is a prime number. In particular, it has been proven that if $$\a\$$ and $$\m\$$ are relatively prime (share no common factors besides $$\1\$$) then there exists a number $$\e\$$ such that $$\a^e\equiv 1\mod m\$$. I will explain what the exercise is by an example. Let's take a modulus $$\m=7\$$. A possible output of the program or function would be: 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 Each row is a list of the powers of the first number in that row: the first row is $$\3, 3^2, 3^3, \cdots, 3^6\$$, which is equivalent to $$\3,2,6,4,5,1\$$ modulo $$\7\$$. The second row of the square above is the powers of $$\2\$$, etcetera, up to the last row, which are just powers of $$\1\$$. This is a magical modulo square because: • The square is symmetric; that is, the $$\i\$$th column is the same as the $$\i\$$th row. • All values $$\1\$$ to $$\m-1\$$ appear at least once. Below is the only other valid output for $$\m=7\$$, starting with powers of $$\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 ## The challenge Create a function or program that given a prime p outputs a magical modulo square, that is, a square with side lengths p-1, such that each row is a list of the consecutive powers of the first element in the row, and the same for the columns. All numbers between 0 and p must occur, and the square can only contain numbers in that range. Input is a number or a string, and output can be ascii, a matrix, an array of arrays (any reasonable format). This is code-golf, so the shortest code wins. • Related OEIS sequence: A001918 (the lowest valid value for the top-left corner). May 7, 2019 at 11:44 • "I will explain what the exercise is by an example." Don't. Explain it in its own terms and then give an example to illustrate. I think that what you're asking for is a matrix \A\ such that \A_{1,1}\ is a primitive root modulo \p\ and \A_{i,j} = A_{1,1}{}^{ij} \bmod p\, but it's a lot of effort to extract that specification from the question as it stands. May 7, 2019 at 13:59 • @PeterTaylor true, and that is what I mean, but firstly, that spoils part of the exploration fun, and second, it relies on knowledge about primitive roots and modular arithmetic. I wanted this question to be answerable by a wider audience than that, so I tried to explain what I mean in easier terms. – user83717 May 7, 2019 at 14:01 ## 12 Answers # Jelly, 13 10 bytes -3 thanks to Nick Kennedy Feels like the repeated code should be is golf-able, but I have did not managed it... *€Ṗ%µQƑƇḢị Try it online! (footer pretty-formats as a grid) ### How? *€Ṗ%µ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 • May 7, 2019 at 7:49 • Ahha, now I feel slow ;p thanks! May 7, 2019 at 7:51 # Charcoal, 36 bytes ≔Ｅ…¹θ﹪Ｘι…¹θＩθηＥ⊟Φη⁼¹№ι¹⪫Ｅ§η⊖ι◧ＩλＬ⊖θ Try it online! Link is to verbose version of code. Note: Trailing space. Explanation: ≔Ｅ…¹θ﹪Ｘι…¹θＩθη Create a p-1 by p-1 array of powers of 1..p-1 to indices 1..p-1 (modulo p). Ｅ⊟Φη⁼¹№ι¹ Map over one of the rows which has exactly one 1. ⪫Ｅ§η⊖ι◧ＩλＬ⊖θ Rearrange the rows into the order given by the selected row and format the output. # J, 35 32 31 bytes [:(/:0/:@{]\:#@~."1)]|^/~@}.@i. Try it online! # Wolfram Language (Mathematica), 46 43 bytes Mod[PrimitiveRoot@#^Array[1##&,{#,#}-1],#]& Try it online! -3 thanks to alephalpha # Zsh, 117 90 bytes b=1 c=(eval set -- '[x**'{1..[b-1]}%b$) for ((;{#{(u)@}}-b+1;++x))c for x;c&&<<<@ May God have mercy on my soul. There's a lot of bad practice all wrapped up here, let me explain the biggest offender at least: 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

Example for 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 Finally, where$c appears in the rest of the program, the array elements are evaluated as eval set -- .....

Lastly, ${#${(u)@}} counts the unique elements int the positional parameters (i.e.: is there a cycle / are there 1s?)

Challenges we have to overcome:

• No multidimensional or nested arrays. Instead we print out the strings as we get them in a loop.
• Options for testing if a given row has multiple 1s:
• ${#${(M)a:#1}: :# removes matching, and (M) reverses the match. So, this will expand to the number (${# }) of 1s in the array. Unfortunately this expansion doesn't play nicely with the arithmetic for loop we use here. If it did, it could potentially save a byte. •${${:-1}:*a}: This is the set intersection between the singleton 1 and the set a. This will expand to the single 1 if it is found in the array. Using this option, we save one character here, but lose 1 overall having to put off adding the 1s in the last row and column until the end. 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$_}}

Try it online!

There's probably some way to just output the square itself, but this does the same process outlined in the question, sorting the lists by their positions in the first list that is just a permutation of 1 to input-1. Returns as a list of lists.

BTW, there's a lot of jockeying around, trying to get around some of Perl 6's annoying limitations involving sequences vs arrays, and anonymous variables.

### Explanation:

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

# JavaScript (ES7),  91  86 bytes

This version attempts to compute the powers before applying the modulo and will fail for $$\p\ge11\$$ because of loss of precision. It is otherwise using the same logic as the commented version below.

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

Try it online!

# JavaScript (ES6),  92  87 bytes

This version uses modular exponentiation to support (much) higher input values.

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)

Try it online!

## How?

### Finding the first row

Given $$\1\le k, we use the helper function $$\g\$$ to compute $$\a_k(n)=k^n\bmod p\$$ for $$\1\le n.

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()

We look for $$\k\$$ such that there's only one value $$\n\$$ such that $$\a_k(n)=1\$$. We do that by sorting the array and testing if the 2nd element is greater than $$\1\$$.

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

This works even in lexicographical order -- which is the default behavior of sort() -- because:

• if there are several $$\1\$$'s, they will all be moved to the front just like they would in numeric order
• if there's only a single $$\1\$$, the 2nd value will be greater than $$\1\$$, no matter if it's really the 2nd value in numeric order or not

Example:

• for $$\k=1\$$, we get:
• $$\a_1=[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]\$$
• sorted as $$\[ 1, \color{red}1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]\$$
• for $$\k=2\$$, we get:
• $$\a_2=[ 2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 15, 13, 9, 1 ]\$$
• sorted as $$\[ 1, \color{red}1, 13, 13, 15, 15, 16, 16, 2, 2, 4, 4, 8, 8, 9, 9 ]\$$
• for $$\k=3\$$, we get:
• $$\a_3=[ 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1 ]\$$
• sorted as $$\[ 1, \color{red}{10}, 11, 12, 13, 14, 15, 16, 2, 3, 4, 5, 6, 7, 8, 9 ]\$$

### Building the matrix

Once we've found $$\k\$$, we invoke $$\g(k)\$$ again (to retrieve the unsorted version of the array) and invoke $$\g\$$ on each element of $$\g(k)\$$ to build the rows of the matrix.

This part can be simply written as:

g(k).map(g)
• .indexOf(1)>p-3 saves 3 bytes over .every.
– Neil
May 7, 2019 at 0:16
• @Neil Thanks. But I've found a shorter way after a good night's sleep. :) May 7, 2019 at 7:42

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

Try it online!

• Can't you do print instead of return? May 8, 2019 at 2:47

# 05AB1E, 19 16 bytes

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

-3 bytes thanks to @Emigna.

Try it online (the footer is to pretty-print the 2D list).

Explanation:

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)
• LεI<LmI%}ÐΘOÏн<è for 16 bytes. May 13, 2019 at 10:07
• @Emigna Thanks! Didn't realize would have been enough instead of the UΣXyk I had. May 13, 2019 at 10:54

Try it online!

# APL(NARS), 29 chars, 58 bytes

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

test:

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

# Pari/GP, 45 bytes

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

Try it online!