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

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.

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.

Example

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

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

Crossrefs

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

Sequence in context: A024691 A220606 A232898 * A135076 A155546 A073132

Adjacent sequences: A319900 A319901 A319902 * A319904 A319905 A319906

Keyword

nonn

Author

Zhi-Wei Sun, Oct 01 2018

Status

approved