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,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

Cf. A000040, A000290.

Sequence in context: A197694 A187770 A103218 * A107381 A242531 A275160

Adjacent sequences: A319308 A319309 A319310 * A319312 A319313 A319314

Keyword

nonn

Author

Zhi-Wei Sun, Sep 16 2018

Status

approved