login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 121

%I

%S 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 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 1,1,1,6,1,1,5,2,1,1,1,4,9,1,1,2,1,1,1,2,1,3

%N (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 Shadow transform of the squares A000290. - _Vladeta Jovovic_, Aug 02 2002

%C _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 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_, July 2000

%C 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), lcm(b,c) = A007947(n) = "squarefree kernel" of n and bc = A019554(n) = "outer square root" of n. [The relation with LCM is wrong if b is not squarefree. One must, e.g., replace b with A007947(b). - _M. F. Hasler_, Mar 03 2018]

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

%H Henry Bottomley, <a href="http://fs.gallup.unm.edu/Bottomley-Sm-Mult-Functions.htm">Some Smarandache-type multiplicative sequences</a>.

%H Kevin A. Broughan, <a href="http://www.math.waikato.ac.nz/~kab/papers/div4.pdf">Restricted divisor sums</a>, Acta Arithmetica, 101(2) (2002), 105-114.

%H 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 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 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 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 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 Vaclav Kotesovec, <a href="/A000188/a000188.jpg">Graph - the asymptotic ratio (100000 terms)</a>

%H 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 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 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.

%H Florentin Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/CP2.pdf">Collected Papers, Vol. II</a>, Tempus Publ. Hse, Bucharest, 1996.

%H 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 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 a(n) = n/A019554(n) = sqrt(A008833(n)).

%F a(n) = Sum_{d^2|n} phi(d), where phi is the Euler totient function A000010.

%F Multiplicative with a(p^e) = p^floor(e/2). - _David W. Wilson_, Aug 01 2001

%F Dirichlet series: Sum_{n >= 1} a(n)/n^s = zeta(2*s - 1)*zeta(s)/zeta(2*s), (Re(s) > 1).

%F Dirichlet convolution of A037213 and A008966. - _R. J. Mathar_, Feb 27 2011

%F Finch & Sebah show that the average order of a(n) is 3 log n/Pi^2. - _Charles R Greathouse IV_, Jan 03 2013

%F a(n) = sqrt(n/A007913(n)). - _M. F. Hasler_, May 08 2014

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

%e a(8) = 2 because the largest square dividing 8 is 4, the square root of which is 2.

%e a(9) = 3 because 9 is a perfect square and its square root is 3.

%e a(10) = 1 because 10 is squarefree.

%p 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 Array[Function[n, Count[Array[PowerMod[#, 2, n ] &, n, 0 ], 0 ] ], 100]

%t (* Second program: *)

%t nMax = 90; sList = Range[Floor[Sqrt[nMax]]]^2; Sqrt[#] &/@ Table[ Last[ Select[ sList, Divisible[n, #] &]], {n, nMax}] (* _Harvey P. Dale_, May 11 2011 *)

%t a[n_] := With[{d = Divisors[n]}, Max[GCD[d, Reverse[d]]]] (* _Mamuka Jibladze_, Feb 15 2015 *)

%t 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 (PARI) a(n)=if(n<1,0,sum(i=1,n,i*i%n==0))

%o (PARI) a(n)=sqrtint(n/core(n)) \\ _Zak Seidov_, Apr 07 2009

%o (PARI) a(n)=core(n, 1)[2] \\ _Michel Marcus_, Feb 27 2013

%o (Haskell)

%o a000188 n = product $ zipWith (^)

%o (a027748_row n) $ map (`div` 2) (a124010_row n)

%o -- _Reinhard Zumkeller_, Apr 22 2012

%Y 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 Cf. A000189, A000190, A007947, A008833, A027748, A046951, A055210, A007913, A117811, A124010. For partial sums see A120486.

%K nonn,easy,nice,mult

%O 1,4

%A _N. J. A. Sloane_

%E Edited by _M. F. Hasler_, May 08 2014

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 13 01:36 EDT 2021. Contains 342934 sequences. (Running on oeis4.)