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

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, 15, 6, 11, 17, 11, 7, 18, 19, 13, 8, 20, 15, 21, 11, 11, 23, 23, 7, 21, 21, 17, 13, 26, 21, 17, 11, 19, 29, 29, 11, 30, 31, 15, 11, 20, 23, 33, 17, 23, 23, 35, 11, 36, 37, 21, 19, 23

Offset

1,5

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

S. R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

E. J. F. Primrose, The number of quadratic residues mod m, Math. Gaz. v. 61 (1977) n. 415, 60-61.

W. D. Stangl, Counting Squares in Z_n, Mathematics Magazine, pp. 285-289, Vol. 69 No. 4 (October 1996).

Eric Weisstein's World of Mathematics, Quadratic Residue

Formula

a(n) = A000224(n) - 1.

Mathematica

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

Prog

(PARI) /* based on code by Franklin T. Adams-Watters, see A000224 */
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
(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
(Haskell)
a105612 = (subtract 1) . a000224  -- Reinhard Zumkeller, Aug 01 2012

Crossrefs

Sequence in context: A046677 A283104 A109747 * A141744 A089783 A302939

Adjacent sequences: A105609 A105610 A105611 * A105613 A105614 A105615

Keyword

nonn

Author

Eric W. Weisstein, Apr 15 2005

Status

approved