A000224 - OEIS

%I #79 Oct 07 2024 15:28:45

%S 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,

%T 16,7,12,18,12,8,19,20,14,9,21,16,22,12,12,24,24,8,22,22,18,14,27,22,

%U 18,12,20,30,30,12,31,32,16,12,21,24,34,18,24,24,36,12

%N Number of squares mod n.

%C For any n > 2, there are quadratic nonresidues mod n, so a(n) < n. - _Charles R Greathouse IV_, Oct 28 2022

%H T. D. Noe, <a href="/A000224/b000224.txt">Table of n, a(n) for n = 1..10000</a>

%H Imanuel Chen and Michael Z. Spivey, <a href="http://soundideas.pugetsound.edu/summer_research/238">Integral Generalized Binomial Coefficients of Multiplicative Functions</a>, Preprint 2015; Summer Research Paper 238, Univ. Puget.

%H Steven 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 Shuguang Li, <a href="http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-aav86i2p113bwm">On the number of elements with maximal order in the multiplicative group modulo n</a>, Acta Arithm. 86 (2) (1998) 113, see proof of theorem 2.1.

%H Param Parekh, Paavan Parekh, Sourav Deb, and Manish K. Gupta, <a href="https://arxiv.org/abs/2310.11768">On the Classification of Weierstrass Elliptic Curves over Z_n</a>, arXiv:2310.11768 [cs.CR], 2023. See p. 6.

%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 Walter D. Stangl, <a href="http://www.jstor.org/stable/2690536">Counting Squares in Z_n</a>, Math. Mag. 69 (1996) 285-289.

%F a(n) = A105612(n) + 1.

%F 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

%F 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

%F 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

%e 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

%p A000224 := proc(m)

%p     {seq( modp(b^2,m),b=0..m-1) };

%p     nops(%) ;

%p end proc: # _Emeric Deutsch_

%p # 2nd implementation

%p A000224 := proc(n)

%p     local a,ifs,f,p,e,c ;

%p     a := 1 ;

%p     ifs := ifactors(n)[2] ;

%p     for f in ifs do

%p         p := op(1,f) ;

%p         e := op(2,f) ;

%p         if p = 2 then

%p             if type(e,'odd') then

%p                 a := a*(2^(e-1)+5)/3 ;

%p             else

%p                 a := a*(2^(e-1)+4)/3 ;

%p             end if;

%p         else

%p             if type(e,'odd') then

%p                 c := 2*p+1 ;

%p             else

%p                 c := p+2 ;

%p             end if;

%p             a := a*(p^(e+1)+c)/2/(p+1) ;

%p         end if;

%p     end do:

%p     a ;

%p end proc: # _R. J. Mathar_, Oct 10 2014

%t Length[Union[#]]& /@ Table[Mod[k^2, n], {n, 65}, {k, n}] (* _Jean-François Alcover_, Aug 30 2011 *)

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

%o (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

%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)) \\ _Charles R Greathouse IV_, Jul 15 2011

%o (Haskell)

%o a000224 n = product $ zipWith f (a027748_row n) (a124010_row n) where

%o    f 2 e = 2 ^ e `div` 6 + 2

%o    f p e = p ^ (e + 1) `div` (2 * p + 2) + 1

%o -- _Reinhard Zumkeller_, Aug 01 2012

%o (Python)

%o from math import prod

%o from sympy import factorint

%o 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

%Y Cf. A095972, A046530 (cubic residues), A052273 (4th powers), A052274 (5th powers), A052275 (6th powers), A085310 (7th powers), A085311 (8th powers), A085312 (9th powers), A085313 (10th powers), A085314 (11th powers), A228849 (12th powers).

%K nonn,easy,nice,mult

%O 1,2

%A _N. J. A. Sloane_