A095972 Number of quadratic nonresidues modulo n.

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

Author

Cino Hilliard, Jul 21 2004

Keywords

• nonn

Comments

A218578(n) is the number of times n occurs in this sequence. - Dmitri Kamenetsky, Nov 03 2012

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Quadratic Nonresidue

Crossrefs

Cf. A096013, A218578.

Programs

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 *)

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

Python

from math import prod
from sympy import factorint
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

Formula

a(n) = n - A000224(n). - R. J. Mathar, Nov 05 2012

Extensions

Edited by Don Reble, May 07 2006