A319311 Number of ordered pairs (i,j) with 0 < i < j < prime(n)/2 such that (i^2 mod prime(n)) > (j^2 mod prime(n)).

0, 0, 1, 4, 3, 9, 14, 22, 28, 40, 53, 73, 86, 101, 116, 168, 153, 234, 260, 246, 299, 362, 365, 435, 523, 583, 612, 559, 652, 835, 952, 918, 1022, 1154, 1286, 1237, 1486, 1554, 1489, 1730, 1694, 1975, 1889, 2078, 2241, 2520, 2672, 2996, 2784, 2892, 3148, 3058, 3488, 3570, 4023, 3881, 4222, 4087, 4363

Offset: 2

Author

Zhi-Wei Sun, Sep 16 2018

Keywords

• nonn

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 2018

Examples

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

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.

Crossrefs

Cf. A000040, A000290.

Programs

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

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