login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of quadratic residues (mod p) in the interval [1,2k+1], for primes p=4k+3.
1

%I #10 Jul 14 2012 11:32:34

%S 1,2,4,6,7,9,12,14,19,18,21,22,25,28,31,34,40,39,41,42,47,52,54,54,57,

%T 59,64,67,73,72,73,75,81,87,87,94,99,96,99,104,118,118,117,118,119,

%U 127,132,125,136,129,136,138,141,154,150,157,162

%N Number of quadratic residues (mod p) in the interval [1,2k+1], for primes p=4k+3.

%C For primes of the form p=4k+3 (A002145), count numbers in [1,2k+1] which are quadratic residues mod p.

%C R. K. Guy asks whether there is an elementary proof for the fact that there are always less quadratic residues in the interval [2k+2,4k+2] than in [1,2k+1].

%F a(n) = A104635(n) - A186709(n) = A186709(n) + A178154(n) = (A104635(n) + A178154(n))/2 = (A002145(n) + 2*A178154(n) - 1)/4.

%o (PARI) forprime( p=1,499, p%4==3|next; u=3; c=[1,0]; for(i=2,p-2, bittest(u,i^2%p) & next; u+=1<<(i^2%p); c[i^2%p*2\p+1]++); print1(c[1]", "))

%Y Cf. A002145, A104635, A186709, A178154.

%K nonn

%O 1,2

%A _M. F. Hasler_, Feb 25 2011