OFFSET
2,4
COMMENTS
Conjecture: Let p be an odd prime and let s(p) be the number of ordered pairs (i,j) with 0 < i < j < p/2 and (i^2 mod p) > (j^2 mod p). Then s(p) is even when p == 3 (mod 8). If p == 7 (mod 8), then s(p) == (h(-p)+1)/2 (mod 2), where h(-p) is the class number of the imaginary quadratic field Q(sqrt(-p)).
We have verified this conjecture for all primes p < 50000 with p == 3 (mod 4).
The conjecture was confirmed by the author in the preprint arXiv:1809.07766v4. - Zhi-Wei Sun, Oct 03 18
LINKS
Zhi-Wei Sun, Table of n, a(n) for n = 2..2500
Zhi-Wei Sun, Quadratic residues and related permutations, arXiv:1809.07766 [math.NT], 2018.
EXAMPLE
a(4) = 1 since prime(4) = 7, and (2,3) is the only ordered pair (i,j) with 0 < i < j < 7/2 and (i^2 mod 7) > (j^2 mod 7).
a(5) = 4 since prime(5) = 11, and the only ordered pairs (i,j) with 0 < i < j < 11/2 and (i^2 mod 11) > (j^2 mod 11) are (2,5), (3,4), (3,5) and (4,5).
MATHEMATICA
s[p_]:=s[p]=Sum[Boole[Mod[i^2, p]>Mod[j^2, p]], {j, 2, (p-1)/2}, {i, 1, j-1}]; Table[s[Prime[n]], {n, 2, 60}]
PROG
(PARI) a(n) = my(p=prime(n), c=0); for(j=2, p/2, for(i=1, j-1, if((i^2%p) > (j^2%p), c++))); c \\ Felix Fröhlich, Oct 04 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Zhi-Wei Sun, Sep 16 2018
STATUS
approved