|
%I #28 Sep 20 2017 02:51:41
%S 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 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 17,11,19,29,29,11,30,31,15,11,20,23,33,17,23,23,35,11,36,37,21,19,23
%N Number of nonzero quadratic residues (mod n) (cf. A000224).
%H Reinhard Zumkeller, <a href="/A105612/b105612.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>
%F a(n) = A000224(n) - 1.
%t 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 (PARI) /* based on code by _Franklin T. Adams-Watters_, see A000224 */
%o 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 (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 (Haskell)
%o a105612 = (subtract 1) . a000224 -- _Reinhard Zumkeller_, Aug 01 2012
%K nonn
%O 1,5
%A _Eric W. Weisstein_, Apr 15 2005
|
