login
Number of quadratic nonresidues modulo n.
10

%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