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

0, 0, 1, 2, 7, 5, 10, 22, 45, 48, 68, 53, 104, 127, 146, 200, 203, 250, 288, 312, 387, 318, 450, 557, 536, 745, 664, 581, 722, 797, 986, 1011, 1082, 1474, 1294, 1317, 1608, 1684, 1893, 2096, 1898, 2297, 2333, 2090, 2467, 2652, 2836, 3352, 3698, 3326, 3380, 2981, 3778, 3902, 4165, 4743, 4350, 4652, 4240

Offset: 2

Author

Zhi-Wei Sun, Oct 01 2018

Keywords

• nonn

Comments

Conjecture 1: Let p be an odd prime, and let N be the number of ordered pairs (i,j) with 0 < i < j < p/2 and (i^8 mod p) > (j^8 mod p). When p == 1 (mod 8), we have 2 | N if and only if 2 is a quartic residue modulo p. Also, N is even if p == 3 (mod 8). When p == 5 (mod 8), we have N == (p-5)/8 (mod 2). If p == 7 (mod 8) then N == (h(-p)+1)/2 (mod 2), where h(-p) is the class number of the imaginary quadratic field Q(sqrt(-p)).

Conjecture 2: Let p be an odd prime, and let N' be the number of ordered pairs (i,j) with 0 < i < j < p/2 and R(i^8,p) > R(j^8,p), where R(k,p) denotes the unique integer r among 0,...,(p-1)/2 with k congruent to r or -r modulo p. When p == 9 (mod 16), we have 2 | N' if and only if 2 is a quartic residue modulo p. Also, N' == floor((p+1)/8) (mod 2) if p is not congruent to 9 modulo 16.

See also A319311, A319480, A319882 and A319894 for similar conjectures.

Examples

			a(4) = 1 since prime(4) = 7, and (R(1^8,7),R(2^8,7),R(3^8,7)) = (1,3,2) with R(2^8,7) > R(3^8,7).
a(5) = 2 since prime(5) = 11, and (R(1^8,11),...,R(5^8,11)) = (1,3,5,2,4) with R(2^8,11) > R(4^8,11), R(3^8,11) > R(4^8,11) and R(3^8,11) > R(5^8,11).
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 2..1000
• Zhi-Wei Sun, Quadratic residues and related permutations, arXiv:1809.07766 [math.NT], 2018.

Crossrefs

Cf. A000040, A001016, A319311, A319480, A319882, A319894.

Programs

Mathematica

f[k_,p_]:=f[k,p]=PowerMod[k,8,p];Inv[p_]:=Inv[p]=Sum[Boole[f[i,p]>f[j,p]],{j,2,(p-1)/2},{i,1,j-1}];Table[Inv[Prime[n]],{n,2,60}]