cp's OEIS Frontend

A000188 (1) Number of solutions to x^2 == 0 (mod n). (2) Also square root of largest square dividing n. (3) Also max_{ d divides n } gcd(d, n/d).

%I A000188 #169 Jul 06 2025 22:28:22
%S A000188 1,1,1,2,1,1,1,2,3,1,1,2,1,1,1,4,1,3,1,2,1,1,1,2,5,1,3,2,1,1,1,4,1,1,
%T A000188 1,6,1,1,1,2,1,1,1,2,3,1,1,4,7,5,1,2,1,3,1,2,1,1,1,2,1,1,3,8,1,1,1,2,
%U A000188 1,1,1,6,1,1,5,2,1,1,1,4,9,1,1,2,1,1,1,2,1,3
%N A000188 (1) Number of solutions to x^2 == 0 (mod n). (2) Also square root of largest square dividing n. (3) Also max_{ d divides n } gcd(d, n/d).
%C A000188 Shadow transform of the squares A000290. - _Vladeta Jovovic_, Aug 02 2002
%C A000188 _Labos Elemer_ and _Henry Bottomley_ independently proved that (2) and (3) define the same sequence. Bottomley also showed that (1) and (2) define the same sequence.
%C A000188 Proof that (2) = (3): Let max{gcd(d, n/d)} = K, then d = Kx, n/d = Ky so n = KKxy where xy is the squarefree part of n, otherwise K is not maximal. Observe also that g = gcd(K, xy) is not necessarily 1. Thus K is also the "maximal square-root factor" of n. - _Labos Elemer_, Jul 2000
%C A000188 We can write sqrt(n) = b*sqrt(c) where c is squarefree. Then b = A000188(n) is the "inner square root" of n, c = A007913(n) and b*c = A019554(n) = "outer square root" of n.
%H A000188 T. D. Noe, <a href="/A000188/b000188.txt">Table of n, a(n) for n = 1..10000</a>
%H A000188 Henry Bottomley, <a href="http://fs.gallup.unm.edu/Bottomley-Sm-Mult-Functions.htm">Some Smarandache-type multiplicative sequences</a>.
%H A000188 Kevin A. Broughan, <a href="http://www.math.waikato.ac.nz/~kab/papers/div4.pdf">Restricted divisor sums</a>, preprint.
%H A000188 Kevin A. Broughan, <a href="https://doi.org/10.4064/aa101-2-2">Restricted divisor sums</a>, Acta Arithmetica, 101(2) (2002), 105-114.
%H A000188 Kevin A. Broughan, <a href="http://ijpam.eu/contents/2003-5-3/2/2.pdf">Relationship between the integer conductor and k-th root functions</a>, Int. J. Pure Appl. Math. 5(3) (2003), 253-275.
%H A000188 Kevin A. Broughan, <a href="http://nzjm.math.auckland.ac.nz/images/d/d6/Relaxations_of_the_ABC_Conjecture_using_integer_k%27th_roots.pdf">Relaxations of the ABC Conjecture using integer k'th roots</a>, New Zealand J. Math. 35(2) (2006), 121-136.
%H A000188 John M. Campbell, <a href="http://arxiv.org/abs/1105.3399">An Integral Representation of Kekulé Numbers, and Double Integrals Related to Smarandache Sequences</a>, arXiv preprint arXiv:1105.3399 [math.GM], 2011.
%H A000188 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 A000188 Vaclav Kotesovec, <a href="/A000188/a000188.jpg">Graph - the asymptotic ratio (100000 terms)</a>
%H A000188 Gerry Myerson, <a href="http://www.austms.org.au/Publ/Gazette/2008/Jul08/TechPaperMyerson.pdf">Trifectas in Geometric Progression</a>, Australian Mathematical Society Gazette 35(3) (2008), 189-194
%H A000188 Andrew Reiter, <a href="http://www.cw-complex.com/modNspirals/modNspirals.pdf">On (mod n) spirals</a> (2014), and posting to Number Theory Mailing List, Mar 23 2014.
%H A000188 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.
%H A000188 Florentin Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/CP2.pdf">Collected Papers, Vol. II</a>, Tempus Publ. Hse, Bucharest, 1996.
%H A000188 László Tóth, <a href="http://arxiv.org/abs/1404.4214">Counting solutions of quadratic congruences in several variables revisited</a>, arXiv preprint arXiv:1404.4214 [math.NT], 2014.
%H A000188 László Tóth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Toth/toth12.html">Counting Solutions of Quadratic Congruences in Several Variables Revisited</a>, J. Int. Seq. 17 (2014), # 14.11.6.
%F A000188 a(n) = n/A019554(n) = sqrt(A008833(n)).
%F A000188 a(n) = Sum_{d^2|n} phi(d), where phi is the Euler totient function A000010.
%F A000188 Multiplicative with a(p^e) = p^floor(e/2). - _David W. Wilson_, Aug 01 2001
%F A000188 Dirichlet series: Sum_{n >= 1} a(n)/n^s = zeta(2*s - 1)*zeta(s)/zeta(2*s), (Re(s) > 1).
%F A000188 Dirichlet convolution of A037213 and A008966. - _R. J. Mathar_, Feb 27 2011
%F A000188 Finch & Sebah show that the average order of a(n) is 3 log n/Pi^2. - _Charles R Greathouse IV_, Jan 03 2013
%F A000188 a(n) = sqrt(n/A007913(n)). - _M. F. Hasler_, May 08 2014
%F A000188 Sum_{n>=1} lambda(n)*a(n)*x^n/(1-x^n) = Sum_{n>=1} n*x^(n^2), where lambda() is the Liouville function A008836 (cf. A205801). - _Mamuka Jibladze_, Feb 15 2015
%F A000188 a(2*n) = a(n)*(A096268(n-1) + 1). - observed by _Velin Yanev_, Jul 14 2017, The formula says that a(2n) = 2*a(n) only when 2-adic valuation of n (A007814(n)) is odd, otherwise a(2n) = a(n). This follows easily from the definition (2). - _Antti Karttunen_, Nov 28 2017
%F A000188 Sum_{k=1..n} a(k) ~ 3*n*((log(n) + 3*gamma - 1)/Pi^2 - 12*zeta'(2)/Pi^4), where gamma is the Euler-Mascheroni constant A001620. - _Vaclav Kotesovec_, Dec 01 2020
%F A000188 Conjecture: a(n) = Sum_{k=1..n} A010052(n*k). - _Velin Yanev_, Jul 04 2021
%F A000188 G.f.: Sum_{k>=1} phi(k) * x^(k^2) / (1 - x^(k^2)). - _Ilya Gutkovskiy_, Aug 20 2021
%e A000188 a(8) = 2 because the largest square dividing 8 is 4, the square root of which is 2.
%e A000188 a(9) = 3 because 9 is a perfect square and its square root is 3.
%e A000188 a(10) = 1 because 10 is squarefree.
%p A000188 with(numtheory):A000188 := proc(n) local i: RETURN(op(mul(i,i=map(x->x[1]^floor(x[2]/2),ifactors(n)[2])))); end;
%t A000188 Array[Function[n, Count[Array[PowerMod[#, 2, n ] &, n, 0 ], 0 ] ], 100]
%t A000188 (* Second program: *)
%t A000188 nMax = 90; sList = Range[Floor[Sqrt[nMax]]]^2; Sqrt[#] &/@ Table[ Last[ Select[ sList, Divisible[n, #] &]], {n, nMax}] (* _Harvey P. Dale_, May 11 2011 *)
%t A000188 a[n_] := With[{d = Divisors[n]}, Max[GCD[d, Reverse[d]]]] (* _Mamuka Jibladze_, Feb 15 2015 *)
%t A000188 f[p_, e_] := p^Floor[e/2]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Sep 18 2020 *)
%o A000188 (PARI) a(n)=if(n<1,0,sum(i=1,n,i*i%n==0))
%o A000188 (PARI) a(n)=sqrtint(n/core(n)) \\ _Zak Seidov_, Apr 07 2009
%o A000188 (PARI) a(n)=core(n, 1)[2] \\ _Michel Marcus_, Feb 27 2013
%o A000188 (Haskell)
%o A000188 a000188 n = product $ zipWith (^)
%o A000188                       (a027748_row n) $ map (`div` 2) (a124010_row n)
%o A000188 -- _Reinhard Zumkeller_, Apr 22 2012
%o A000188 (Python)
%o A000188 from sympy.ntheory.factor_ import core
%o A000188 from sympy import integer_nthroot
%o A000188 def A000188(n): return integer_nthroot(n//core(n),2)[0] # _Chai Wah Wu_, Jun 14 2021
%Y A000188 Cf. A019554 (outer square root), A053150 (inner 3rd root), A019555 (outer 3rd root), A053164 (inner 4th root), A053166 (outer 4th root), A015052 (outer 5th root), A015053 (outer 6th root).
%Y A000188 Cf. A000189, A000190, A007947, A008833, A027748, A046951, A055210, A007913, A117811, A124010. For partial sums see A120486.
%Y A000188 Cf. A240976 (Dgf at s=2).
%K A000188 nonn,easy,nice,mult
%O A000188 1,4
%A A000188 _N. J. A. Sloane_
%E A000188 Edited by _M. F. Hasler_, May 08 2014