cp's OEIS Frontend

A105612 Number of nonzero quadratic residues (mod n) (cf. A000224).

%I A105612 #42 Apr 12 2025 09:43:19
%S A105612 0,1,1,1,2,3,3,2,3,5,5,3,6,7,5,3,8,7,9,5,7,11,11,5,10,13,10,7,14,11,
%T A105612 15,6,11,17,11,7,18,19,13,8,20,15,21,11,11,23,23,7,21,21,17,13,26,21,
%U A105612 17,11,19,29,29,11,30,31,15,11,20,23,33,17,23,23,35,11,36,37,21,19,23
%N A105612 Number of nonzero quadratic residues (mod n) (cf. A000224).
%H A105612 Reinhard Zumkeller, <a href="/A105612/b105612.txt">Table of n, a(n) for n = 1..10000</a>
%H A105612 S. R. Finch and Pascal Sebah, <a href="https://arxiv.org/abs/math/0604465">Squares and Cubes Modulo n</a>, arXiv:math/0604465 [math.NT], 2006-2016.
%H A105612 E. J. F. Primrose, <a href="http://dx.doi.org/10.2307/3617445">The number of quadratic residues mod m</a>, Math. Gaz. v. 61 (1977) n. 415, 60-61.
%H A105612 W. D. Stangl, <a href="http://www.jstor.org/stable/2690536">Counting Squares in Z_n</a>, Mathematics Magazine, pp. 285-289, Vol. 69 No. 4 (October 1996).
%H A105612 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>
%F A105612 a(n) = A000224(n) - 1.
%F A105612 If p is an odd prime, then a(p) = (p - 1)/2. - _Thomas Ordowski_, Apr 09 2025
%t A105612 a[n_]:=Count[Union[Mod[Range[Floor[n/2]]^2,n]],_?Positive];Table[a[n],{n,1,80}] (* _Jean-François Alcover_,  Feb 09 2011 *)
%o A105612 (PARI) /* based on code by _Franklin T. Adams-Watters_, see A000224 */
%o A105612 A105612(n)=local(v,i);v=vector(n,i,0);for(i=0,floor(n/2),v[i^2%n+1]=1);sum(i=2,n,v[i]) \\ _Michael B. Porter_, May 04 2010
%o A105612 (PARI) a(n)=my(f=factor(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))-1 \\ _Charles R Greathouse IV_, Sep 10 2013
%o A105612 (Haskell)
%o A105612 a105612 = (subtract 1) . a000224  -- _Reinhard Zumkeller_, Aug 01 2012
%K A105612 nonn
%O A105612 1,5
%A A105612 _Eric W. Weisstein_, Apr 15 2005