# Quadratic residues are so much fun!

## Definitions

An integer $$\r\$$ is called a quadratic residue modulo $$\n\$$ if there exists an integer $$\x\$$ such that:

$$x^2\equiv r \pmod n$$

The set of quadratic residues modulo $$\n\$$ can be simply computed by looking at the results of $$\x^2 \bmod n\$$ for $$\0 \le x \le \lfloor n/2\rfloor\$$.

### The challenge sequence

We define $$\a_n\$$ as the minimum number of occurrences of the same value $$\(r_0-r_1+n) \bmod n\$$ for all pairs $$\(r_0,r_1)\$$ of quadratic residues modulo $$\n\$$.

The first 30 terms are:

$$1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 3, 1, 3, 4, 1, 1, 4, 2, 5, 1, 2, 6, 6, 1, 2, 6, 2, 2, 7, 2$$

This is A316975 (submitted by myself).

## Example: $$\n=10\$$

The quadratic residues modulo $$\10\$$ are $$\0\$$, $$\1\$$, $$\4\$$, $$\5\$$, $$\6\$$ and $$\9\$$.

For each pair $$\(r_0,r_1)\$$ of these quadratic residues, we compute $$\(r_0-r_1+10) \bmod 10\$$, which leads to the following table (where $$\r_0\$$ is on the left and $$\r_1\$$ is on the top):

$$\begin{array}{c|cccccc} & 0 & 1 & 4 & 5 & 6 & 9\\ \hline 0 & 0 & 9 & 6 & 5 & 4 & 1\\ 1 & 1 & 0 & \color{blue}7 & 6 & 5 & \color{green}2\\ 4 & 4 & \color{magenta}3 & 0 & 9 & \color{red}8 & 5\\ 5 & 5 & 4 & 1 & 0 & 9 & 6\\ 6 & 6 & 5 & \color{green}2 & 1 & 0 & \color{blue}7\\ 9 & 9 & \color{red}8 & 5 & 4 & \color{magenta}3 & 0 \end{array}$$

The minimum number of occurrences of the same value in the above table is $$\2\$$ (for $$\\color{green}2\$$, $$\\color{magenta}3\$$, $$\\color{blue}7\$$ and $$\\color{red}8\$$). Therefore $$\a_{10}=2\$$.

• You may either:

• take an integer $$\n\$$ and print or return $$\a_n\$$ (either 0-indexed or 1-indexed)
• take an integer $$\n\$$ and print or return the $$\n\$$ first terms of the sequence
• take no input and print the sequence forever
• Your code must be able to process any of the 50 first values of the sequence in less than 1 minute.

• Given enough time and memory, your code must theoretically work for any positive integer supported by your language.

• This is .

• Grats on getting a sequence published on OEIS! – AdmBorkBork Sep 21 '18 at 15:43
• @AdmBorkBork Thanks. :) (As a matter of fact, I usually avoid posting an OEIS sequence as-is as a challenge, but I guess that's OK for this one.) – Arnauld Sep 21 '18 at 16:14
• Doesn't the +n inside the (...)mod n have no effect? If so it's very weird that is part of the definition. – Jonathan Allan Sep 21 '18 at 17:01
• @JonathanAllan Actually, I made a similar remark in the draft version of the sequence and suggested that it was removed. But I didn't find any clear consensus, nor did I get any feedback about that. (And I seem to recall having seen other sequences with (some_potentially_negative_value + n) mod n.) I think it's better to have it in a programming challenge, though, since the sign of the result depends on the language. – Arnauld Sep 21 '18 at 17:09
• I've tried to find a direct formula without success. The sequence is multiplicative and on primes it equals a_p = round(p/4), which gives us the values for all squarefree numbers. But the situation seems complicated on powers of primes, and the 3 mod 4 and 1 mod 4 cases need to be handled separately. – xnor Sep 22 '18 at 16:53

# MATL, 14 bytes

:UG\u&-G\8#uX<


### Explanation

:      % Implicit input. Range
U      % Square, element-wise
G      % Push input again
\      % Modulo, element-wise
u      % Unique elements
&-     % Table of pair-wise differences
G      % Push input
\      % Modulo, element-wise
8#u    % Number of occurrences of each element
X<     % Minimum. Implicit display


# Japt-g, 22 20 bytes

Spent too long figuring out what the challenge was actually about, ran out of time for further golfing :\

Outputs the nth term in the sequence. Starts struggling when input >900.

õ_²uUÃâ ïÍmuU
£è¥XÃn


## Explanation

                  :Implicit input of integer U
õ                 :Range [1,U]
_                :Map
²               :  Square
uU             :  Modulo U
Ã            :End map
â           :Deduplicate
ï         :Cartesian product of the resulting array with itself
Í        :Reduce each pair by subtraction
m       :Map
uU     :  Absolute value of modulo U
\n                :Reassign to U
£                 :Map each X
è                :  Count the elements in U that are
¥X              :   Equal to X
Ã             :End map
n            :Sort
:Implicitly output the first element in the array


# Jelly,  13  10 bytes

-1 thanks to Dennis (forcing dyadic interpretation with a leading ð)
-2 more also thanks to Dennis (since the pairs may be de-duplicated we can avoid an R and a 2)

ðp²%QI%ĠẈṂ


A monadic link accepting a positive integer which yields a non-negative integer.

### How?

ðp²%QI%ĠẈṂ - Link: integer, n                   e.g. 6
ð          - start a new dyadic chain - i.e. f(Left=n, Right=n)
p         - Cartesian product of (implicit ranges)  [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6]]
²        - square (vectorises)                     [[1,1],[1,4],[1,9],[1,16],[1,25],[1,36],[4,1],[4,4],[4,9],[4,16],[4,25],[4,36],[9,1],[9,4],[9,9],[9,16],[9,25],[9,36],[16,1],[16,4],[16,9],[16,16],[16,25],[16,36],[25,1],[25,4],[25,9],[25,16],[25,25],[25,36],[36,1],[36,4],[36,9],[36,16],[36,25],[36,36]]
%       - modulo (by Right) (vectorises)          [[1,1],[1,4],[1,3],[1,4],[1,1],[1,0],[4,1],[4,4],[4,3],[4,4],[4,1],[4,0],[3,1],[3,4],[3,3],[3,4],[3,1],[3,0],[4,1],[4,4],[4,3],[4,4],[4,1],[4,0],[1,1],[1,4],[1,3],[1,4],[1,1],[1,0],[0,1],[0,4],[0,3],[0,4],[0,1],[0,0]]
Q      - de-duplicate                            [[1,1],[1,4],[1,3],[1,0],[4,1],[4,4],[4,3],[4,0],[3,1],[3,4],[3,3],[3,0],[0,1],[0,4],[0,3],[0,0]]
I     - incremental differences (vectorises)    [0,3,2,-1,-3,0,-1,-4,-2,1,0,-3,1,4,3,0]
%    - modulo (by Right) (vectorises)          [0,3,2,5,3,0,5,2,4,1,0,3,1,4,3,0]
Ġ   - group indices by value                  [[1,6,11,16],[10,13],[3,8],[2,5,12,15],[9,14],[4,7]]
Ẉ  - length of each                          [3,2,2,4,2,2]
Ṃ - minimum                                 2


# 05AB1E, 222015 13 bytes

LnI%êãÆI%D.m¢


-2 bytes thanks to @Mr. Xcoder.

Try it online or verify the first 99 test cases (in about 3 seconds). (NOTE: The Python legacy version is used on TIO instead of the new Elixir rewrite. It's about 10x faster, but requires a trailing ¬ (head) because .m returns a list instead of a single item, which I've added to the footer.)

Explanation:

L       # Create a list in the range [1, (implicit) input]
n      # Square each
I%    # And then modulo each with the input
ê   # Sort and uniquify the result (faster than just uniquify apparently)
ã      # Create pairs (cartesian product with itself)
Æ     # Get the differences between each pair
I%   # And then modulo each with the input
D.m     # Take the least frequent number (numbers in the legacy version)
¢    # Take the count it (or all the numbers in the legacy version, which are all the same)
# (and output it implicitly)

• Ýns%ÙãÆI%D.m¢. (not in legacy, in the new version) – Mr. Xcoder Sep 21 '18 at 18:01
• @Mr.Xcoder Ah, I'm an idiot to use Dâ instead of ã.. >.> And didn't knew the .m acted differently in the Elixir rewrite. I originally had the new version, but switched to the legacy after I noticed the ¥ wasn't working (which you've fixed with the Æ). I still use the legacy on TIO though, because it's way faster for this challenge. – Kevin Cruijssen Sep 21 '18 at 19:21

# C (gcc), 202200190188187 186 bytes

• Saved two twelve fourteen fifteen bytes thanks to ceilingcat.
• Saved a byte.
Q(u,a){int*d,*r,A[u],t,i[a=u],*c=i,k;for(;a--;k||(*c++=a*a%u))for(k=a[A]=0,r=i;r<c;)k+=a*a%u==*r++;for(r=c;i-r--;)for(d=i;d<c;++A[(u+*r-*d++)%u]);for(t=*A;++a<u;t=k&&k<t?k:t)k=A[a];u=t;}


Try it online!

• @ceilingcat Cool; declaring another integer actually allows to save another byte. – Jonathan Frech Sep 25 '18 at 20:53
• @ceilingcat I think those expressions are not equivalent as I need the smallest positive modulo residue. – Jonathan Frech Dec 19 '18 at 7:39

# Python 2, 97 bytes

def f(n):r={i*i%n for i in range(n)};r=[(s-t)%n for s in r for t in r];return min(map(r.count,r))


Try it online!

# K (ngn/k), 29 bytes

{&/#:'=,/x!r-\:r:?x!i*i:!x}


Try it online!

{ } function with argument x

!x integers from 0 to x-1

i: assign to i

x! mod x

? unique

r: assign to r

-\: subtract from each left

r-\:r matrix of all differences

x! mod x

,/ concatenate the rows of the matrix

= group, returns a dictionary from unique values to lists of occurrence indices

#:' length of each value in the dictionary

&/ minimum

# Wolfram Language (Mathematica), 64 bytes

Min[Last/@Tally@Mod[Tuples[Union@Mod[Range@#^2,#],2].{1,-1},#]]&


Try it online!

# Ruby, 88 bytes

->n{(z=(w=(0..n).map{|x|x*x%n}|[]).product(w).map{|a,b|(a-b)%n}).map{|c|z.count(c)}.min}


Try it online!

# APL (Dyalog Unicode), 28 24 bytes

{⌊/⊢∘≢⌸∊⍵|∘.-⍨∪⍵|×⍨⍳⍵+1}


Try it online!

Prefix direct function. Uses ⎕IO←0.

Thanks to Cows quack for 4 bytes!

### How:

{⌊/⊢∘≢⌸∊⍵|∘.-⍨∪⍵|×⍨⍳⍵+1} ⍝ Dfn, argument ⍵

⍳⍵+1 ⍝ Range [0..⍵]
×⍨     ⍝ Squared
⍵|       ⍝ Modulo ⍵
∪         ⍝ Unique
∘.-⍨          ⍝ Pairwise subtraction table
∊⍵|              ⍝ Modulo ⍵, flattened
⌸                 ⍝ Key; groups indices (in its ⍵) of values (in its ⍺).
⊢∘≢                  ⍝ Tally (≢) the indices. This returns the number of occurrences of each element.
⌊/                      ⍝ Floor reduction; returns the smallest number.

• Couple of small byte-shavings, 2*⍨×⍨, r←¨⊂r∘.-⍨, {≢⍵}⊢∘≢ – user41805 Sep 26 '18 at 7:20