login
A095972
Number of quadratic nonresidues modulo n.
10
0, 0, 1, 2, 2, 2, 3, 5, 5, 4, 5, 8, 6, 6, 9, 12, 8, 10, 9, 14, 13, 10, 11, 18, 14, 12, 16, 20, 14, 18, 15, 25, 21, 16, 23, 28, 18, 18, 25, 31, 20, 26, 21, 32, 33, 22, 23, 40, 27, 28, 33, 38, 26, 32, 37, 44, 37, 28, 29, 48, 30, 30, 47, 52, 44, 42, 33, 50, 45, 46, 35, 60, 36, 36, 53
OFFSET
1,4
COMMENTS
A218578(n) is the number of times n occurs in this sequence. - Dmitri Kamenetsky, Nov 03 2012
LINKS
Eric Weisstein's World of Mathematics, Quadratic Nonresidue
FORMULA
a(n) = n - A000224(n). - R. J. Mathar, Nov 05 2012
MAPLE
A095972 := proc(n)
local a, q;
a := 0 ;
for q from 0 to n-1 do
if numtheory[quadres](q, n) = -1 then
a := a+1 ;
end if;
end do;
a ;
end proc: # R. J. Mathar, Nov 05 2012
MATHEMATICA
Table[Length[Complement[Range[n-1], Union[Mod[Range[n]^2, n]]]], {n, 100}] (* T. D. Noe, Nov 06 2012 *)
PROG
(PARI) A095972(n)={local(v); v=vector(n, i, 1); for(i=0, floor(n/2), v[i^2%n+1]=0); sum(i=1, n, v[i])} \\ Michael B. Porter, Apr 30 2010
(PARI) a(n)=my(f=factor(n)); n-prod(i=1, #f[, 1], if(f[i, 1]==2, 2^f[1, 2]\6+2, f[i, 1]^(f[i, 2]+1)\(2*f[i, 1]+2)+1)) \\ Charles R Greathouse IV, Jul 15 2011
CROSSREFS
Sequence in context: A036355 A228390 A309256 * A091974 A029073 A058618
KEYWORD
nonn
AUTHOR
Cino Hilliard, Jul 21 2004
EXTENSIONS
Edited by Don Reble, May 07 2006
STATUS
approved