%I #6 Oct 01 2018 05:55:42
%S 0,0,1,2,7,5,10,22,45,48,68,53,104,127,146,200,203,250,288,312,387,
%T 318,450,557,536,745,664,581,722,797,986,1011,1082,1474,1294,1317,
%U 1608,1684,1893,2096,1898,2297,2333,2090,2467,2652,2836,3352,3698,3326,3380,2981,3778,3902,4165,4743,4350,4652,4240
%N 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)).
%C 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)).
%C 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.
%C See also A319311, A319480, A319882 and A319894 for similar conjectures.
%H Zhi-Wei Sun, <a href="/A319903/b319903.txt">Table of n, a(n) for n = 2..1000</a>
%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/1809.07766">Quadratic residues and related permutations</a>, arXiv:1809.07766 [math.NT], 2018.
%e 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).
%e 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).
%t 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}]
%Y Cf. A000040, A001016, A319311, A319480, A319882, A319894.
%K nonn
%O 2,4
%A _Zhi-Wei Sun_, Oct 01 2018
|