%I #39 Oct 07 2024 15:28:55
%S 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,
%T 14,18,15,25,21,16,23,28,18,18,25,31,20,26,21,32,33,22,23,40,27,28,33,
%U 38,26,32,37,44,37,28,29,48,30,30,47,52,44,42,33,50,45,46,35,60,36,36,53
%N Number of quadratic nonresidues modulo n.
%C A218578(n) is the number of times n occurs in this sequence. - _Dmitri Kamenetsky_, Nov 03 2012
%H T. D. Noe, <a href="/A095972/b095972.txt">Table of n, a(n) for n = 1..10000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QuadraticNonresidue.html">Quadratic Nonresidue</a>
%F a(n) = n - A000224(n). - _R. J. Mathar_, Nov 05 2012
%p A095972 := proc(n)
%p local a,q;
%p a := 0 ;
%p for q from 0 to n-1 do
%p if numtheory[quadres](q,n) = -1 then
%p a := a+1 ;
%p end if;
%p end do;
%p a ;
%p end proc: # _R. J. Mathar_, Nov 05 2012
%t Table[Length[Complement[Range[n-1], Union[Mod[Range[n]^2, n]]]], {n, 100}] (* _T. D. Noe_, Nov 06 2012 *)
%o (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
%o (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
%o (Python)
%o from math import prod
%o from sympy import factorint
%o def A095972(n): return n-prod((p**(e+1)//((p+1)*(q:=1+(p==2)))>>1)+q for p, e in factorint(n).items()) # _Chai Wah Wu_, Oct 07 2024
%Y Cf. A096013, A218578.
%K nonn
%O 1,4
%A _Cino Hilliard_, Jul 21 2004
%E Edited by _Don Reble_, May 07 2006