|
|
A186708
|
|
Number of quadratic residues (mod p) in the interval [1,2k+1], for primes p=4k+3.
|
|
1
|
|
|
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, 59, 64, 67, 73, 72, 73, 75, 81, 87, 87, 94, 99, 96, 99, 104, 118, 118, 117, 118, 119, 127, 132, 125, 136, 129, 136, 138, 141, 154, 150, 157, 162
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
For primes of the form p=4k+3 (A002145), count numbers in [1,2k+1] which are quadratic residues mod p.
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].
|
|
LINKS
|
|
|
FORMULA
|
|
|
PROG
|
(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]", "))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|