A316975 a(n) is the minimum number of occurrences of the same value (r0-r1+n) mod n for all pairs (r0,r1) of quadratic residues mod n.

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, 8, 1, 3, 8, 2, 1, 9, 10, 3, 1, 10, 4, 11, 3, 1, 12, 12, 1, 8, 4, 4, 3, 13, 4, 3, 2, 5, 14, 15, 1, 15, 16, 2, 1, 3, 6, 17, 4, 6, 4, 18, 1, 18, 18, 2, 5, 6, 6, 20, 1, 4, 20

Offset: 1

Author

Arnauld Chevallier, Jul 17 2018

Keywords

• nonn
• mult

Comments

Multiplicative by the Chinese remainder theorem since if gcd(m,n) = 1 then r is a quadratic residue mod m*n iff it is a quadratic residue mod m and a quadratic residue mod n. - Andrew Howroyd, Aug 07 2018

Examples

			The quadratic residues mod 10 are 0, 1, 4, 5, 6 and 9. For each pair (r0,r1) of these quadratic residues, we compute (r0-r1+10) mod 10, leading to:
      0 1 4 5 6 9
    +------------
  0 | 0 9 6 5 4 1
  1 | 1 0 7 6 5 2
  4 | 4 3 0 9 8 5
  5 | 5 4 1 0 9 6
  6 | 6 5 2 1 0 7
  9 | 9 8 5 4 3 0
The minimum number of occurrences of the same value in the above table is 2 (for 2, 3, 7 and 8). Therefore a(10) = 2.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A096008.

Programs

Mathematica

Table[Min@ Tally[#][[All, -1]] &@ Flatten[Mod[#, n] & /@ Outer[Subtract, #, #]] &@ Union@ PowerMod[Range@ n, 2, n], {n, 82}] (* Michael De Vlieger, Jul 20 2018 *)

PARI

a(n)={my(r=Set(vector(n,i,i^2%n))); my(v=vector(n)); for(i=1, #r, for(j=1, #r, v[(r[i]-r[j])%n + 1]++)); vecmin(select(t->t>0, v))} \\ Andrew Howroyd, Aug 07 2018