cp's OEIS Frontend

A095972 Number of quadratic nonresidues modulo n.

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