cp's OEIS Frontend

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

%I A319311 #20 Aug 03 2025 23:39:51
%S A319311 0,0,1,4,3,9,14,22,28,40,53,73,86,101,116,168,153,234,260,246,299,362,
%T A319311 365,435,523,583,612,559,652,835,952,918,1022,1154,1286,1237,1486,
%U A319311 1554,1489,1730,1694,1975,1889,2078,2241,2520,2672,2996,2784,2892,3148,3058,3488,3570,4023,3881,4222,4087,4363
%N 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)).
%C A319311 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)).
%C A319311 We have verified this conjecture for all primes p < 50000 with p == 3 (mod 4).
%C A319311 The conjecture was confirmed by the author in the preprint arXiv:1809.07766v4. - _Zhi-Wei Sun_, Oct 03 2018
%H A319311 Zhi-Wei Sun, <a href="/A319311/b319311.txt">Table of n, a(n) for n = 2..2500</a>
%H A319311 Zhi-Wei Sun, <a href="http://arxiv.org/abs/1809.07766">Quadratic residues and related permutations</a>, arXiv:1809.07766 [math.NT], 2018.
%e A319311 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).
%e A319311 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).
%t A319311 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}]
%o A319311 (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
%Y A319311 Cf. A000040, A000290.
%K A319311 nonn
%O A319311 2,4
%A A319311 _Zhi-Wei Sun_, Sep 16 2018