

A105612


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


7



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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], 20062016.
E. J. F. Primrose, The number of quadratic residues mod m, Math. Gaz. v. 61 (1977) n. 415, 6061.
W. D. Stangl, Counting Squares in Z_n, Mathematics Magazine, pp. 285289, 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}] (* JeanFrançois Alcover, Feb 09 2011 *)


PROG

(PARI) /* based on code by Franklin T. AdamsWatters, 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



