11
\$\begingroup\$

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\$ if and only if \$m\mid a-b\$. 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.

\$\endgroup\$
  • \$\begingroup\$ Related OEIS sequence: A001918 (the lowest valid value for the top-left corner). \$\endgroup\$ – Arnauld May 7 at 11:44
  • 2
    \$\begingroup\$ "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. \$\endgroup\$ – Peter Taylor May 7 at 13:59
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – vrugtehagel May 7 at 14:01

12 Answers 12

5
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 36 bytes

≔E…¹θ﹪Xι…¹θIθηE⊟Φη⁼¹№ι¹⪫E§η⊖ι◧IλL⊖θ 

Try it online! Link is to verbose version of code. Note: Trailing space. Explanation:

≔E…¹θ﹪Xι…¹θIθη

Create a p-1 by p-1 array of powers of 1..p-1 to indices 1..p-1 (modulo p).

E⊟Φη⁼¹№ι¹

Map over one of the rows which has exactly one 1.

⪫E§η⊖ι◧IλL⊖θ 

Rearrange the rows into the order given by the selected row and format the output.

\$\endgroup\$
2
\$\begingroup\$

J, 35 32 31 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 46 43 bytes

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

Try it online!

-3 thanks to alephalpha

\$\endgroup\$
2
\$\begingroup\$

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<p\$, we use the helper function \$g\$ to compute \$a_k(n)=k^n\bmod p\$ for \$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()

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 \$p=17\$:

  • 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)
\$\endgroup\$
  • \$\begingroup\$ .indexOf(1)>p-3 saves 3 bytes over .every. \$\endgroup\$ – Neil May 7 at 0:16
  • \$\begingroup\$ @Neil Thanks. But I've found a shorter way after a good night's sleep. :) \$\endgroup\$ – Arnauld May 7 at 7:42
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Zsh, 117 bytes

f(){a=();for i ({1..$[$2-2]})a+=($[$1**i%$2])}
a=(1)
for ((;${${:-1}:*a};))f $[++x] $1
for y ($a 1){f $y $1;<<<$a\ 1}

Try it online!

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)
}
\$\endgroup\$
1
\$\begingroup\$

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

Wolfram Language (Mathematica), 67 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 48 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.