A000224 Number of squares mod n.
1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, 18, 14, 27, 22, 18, 12, 20, 30, 30, 12, 31, 32, 16, 12, 21, 24, 34, 18, 24, 24, 36, 12
Offset: 1
Examples
The sequence of squares (A000290) modulo 10 reads 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, 1, 4, 9, 6, 5, 6, 9, 4, 1,... and this reduced sequence contains a(10) = 6 different values, {0,1,4,5,6,9}. - _R. J. Mathar_, Oct 10 2014
Links
- T. D. Noe, Table of n, a(n) for n = 1..10000
- Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget.
- Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
- Shuguang Li, On the number of elements with maximal order in the multiplicative group modulo n, Acta Arithm. 86 (2) (1998) 113, see proof of theorem 2.1.
- Param Parekh, Paavan Parekh, Sourav Deb, and Manish K. Gupta, On the Classification of Weierstrass Elliptic Curves over Z_n, arXiv:2310.11768 [cs.CR], 2023. See p. 6.
- E. J. F. Primrose, The number of quadratic residues mod m, Math. Gaz. v. 61 (1977) n. 415, 60-61.
- Walter D. Stangl, Counting Squares in Z_n, Math. Mag. 69 (1996) 285-289.
Crossrefs
Programs
-
Haskell
a000224 n = product $ zipWith f (a027748_row n) (a124010_row n) where f 2 e = 2 ^ e `div` 6 + 2 f p e = p ^ (e + 1) `div` (2 * p + 2) + 1 -- Reinhard Zumkeller, Aug 01 2012
-
Maple
A000224 := proc(m) {seq( modp(b^2,m),b=0..m-1) }; nops(%) ; end proc: # Emeric Deutsch # 2nd implementation A000224 := proc(n) local a,ifs,f,p,e,c ; a := 1 ; ifs := ifactors(n)[2] ; for f in ifs do p := op(1,f) ; e := op(2,f) ; if p = 2 then if type(e,'odd') then a := a*(2^(e-1)+5)/3 ; else a := a*(2^(e-1)+4)/3 ; end if; else if type(e,'odd') then c := 2*p+1 ; else c := p+2 ; end if; a := a*(p^(e+1)+c)/2/(p+1) ; end if; end do: a ; end proc: # R. J. Mathar, Oct 10 2014
-
Mathematica
Length[Union[#]]& /@ Table[Mod[k^2, n], {n, 65}, {k, n}] (* Jean-François Alcover, Aug 30 2011 *) a[2] = 2; a[n_] := a[n] = Switch[fi = FactorInteger[n], {{, 1}}, (fi[[1, 1]] + 1)/2, {{2, }}, 3/2 + 2^fi[[1, 2]]/6 + (-1)^(fi[[1, 2]]+1)/6, {{, }}, {p, k} = fi[[1]]; 3/4 + (p-1)*(-1)^(k+1)/(4*(p+1)) + p^(k+1)/(2*(p+1)), , Times @@ Table[ a[Power @@ f], {f, fi}]]; Table[a[n], {n, 1, 100}] (* _Jean-François Alcover, Mar 09 2015 *) -
PARI
a(n) = local(v,i); v = vector(n,i,0); for(i=0, floor(n/2),v[i^2%n+1] = 1); sum(i=1,n,v[i]) \\ Franklin T. Adams-Watters, Nov 05 2006
-
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)) \\ Charles R Greathouse IV, Jul 15 2011
-
Python
from math import prod from sympy import factorint def A000224(n): return 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) = A105612(n) + 1.
Multiplicative with a(p^e) = floor(p^e/6) + 2 if p = 2; floor(p^(e+1)/(2p + 2)) + 1 if p > 2. - David W. Wilson, Aug 01 2001
a(2^n) = A023105(n). a(3^n) = A039300(n). a(5^n) = A039302(n). a(7^n) = A039304(n). - R. J. Mathar, Sep 28 2017
Sum_{k=1..n} a(k) ~ c * n^2/sqrt(log(n)), where c = (17/(32*sqrt(Pi))) * Product_{p prime} (1 - (p^2+2)/(2*(p^2+1)*(p+1))) * (1-1/p)^(-1/2) = 0.37672933209687137604... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022
If p is an odd prime, then a(p) = (p + 1)/2. - Thomas Ordowski, Apr 09 2025
Comments