login
The number of quadratic residues (mod p) greater than p/2, where p=prime(n).
2

%I #2 Mar 30 2012 17:22:56

%S 0,1,1,1,3,4,3,4,7,6,9,10,9,9,13,10,15,15,14,18,17,16,22,24,25,23,22,

%T 27,28,29,25,34,30,37,34,39,39,36,43,37,45,41,48,49,45,48,52,49,57,58,

%U 52,60,52,64,59,67,62,69,70,66,73,72,68,78,79,78,84,79,87,88,80,87,93,90

%N The number of quadratic residues (mod p) greater than p/2, where p=prime(n).

%C Sequence A063987 lists the quadratic residues (mod p) for each prime p. When p=1 (mod 4), there are an equal number of quadratic residues less than p/2 and greater than p/2. When p=3 (mod 4), there are always more quadratic residues less than p/2 than greater than p/2.

%H MathOverflow, <a href="http://mathoverflow.net/questions/25263">Most squares in the first half-interval</a>

%e The quadratic residues of 19, the 8th prime, are 1, 4, 5, 6, 7, 9, 11, 16, 17. Three of these are greater than 19/2. Hence a(8)=3.

%t Table[p=Prime[n]; Length[Select[Range[(p+1)/2,p-1], JacobiSymbol[ #,p]==1&]], {n,2,100}]

%Y Cf. A178151, A178153, A178154

%K nonn

%O 2,5

%A _T. D. Noe_, May 21 2010