login
This site is supported by donations to The OEIS 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). 82
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, 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, 1, 1, 1, 6, 1, 1, 5, 2, 1, 1, 1, 4, 9, 1, 1, 2, 1, 1, 1, 2, 1, 3 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

Shadow transform of the squares A000290. - Vladeta Jovovic, Aug 02 2002

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.

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

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.

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

Henry Bottomley, Some Smarandache-type multiplicative sequences

Kevin A. Broughan, Restricted divisor sums, Acta Arithmetica, vol. 101, (2002), pp. 105-114.

John M. Campbell, An Integral Representation of Kekulé Numbers, and Double Integrals Related to Smarandache Sequences, arXiv preprint arXiv:1105.3399, 2011.

Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n (arXiv:math.NT/0604465).

Gerry Myerson, Trifectas in Geometric Progression, Australian Mathematical Society Gazette, 35 (3) 2008, p 189-194

Andrew Reiter, On (mod n) spirals (2014), and posting to Number Theory Mailing List, Mar 23 2014.

N. J. A. Sloane, Transforms

L. Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint arXiv:1404.4214, 2014

FORMULA

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

Multiplicative with a(p^e) = p^[e/2]. - David W. Wilson, Aug 01 2001

Dirichlet series: Sum(n = 1..inf, a(n)/n^s) = zeta(2*s - 1)*zeta(s)/zeta(2*s), (Re(s) > 1).

Dirichlet convolution of A037213 and A008966. - R. J. Mathar, Feb 27 2011

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

a(n) = sqrt(n/A007913(n)). - M. F. Hasler, May 08 2014

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

EXAMPLE

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

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

a(10) = 1 because 10 is squarefree.

MAPLE

with(numtheory):A000188 := proc(n) local i: RETURN(op(mul(i, i=map(x->x[1]^floor(x[2]/2), ifactors(n)[2])))); end;

MATHEMATICA

Array[Function[n, Count[Array[PowerMod[#, 2, n ] &, n, 0 ], 0 ] ], 100]

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

With[{d = Divisors[n]}, Max[GCD[d, Reverse[d]]]] (* Mamuka Jibladze, Feb 15 2015 *)

PROG

(PARI) a(n)=if(n<1, 0, sum(i=1, n, i*i%n==0))

(PARI) a(n)=sqrtint(n/core(n)) \\ Zak Seidov, Apr 07 2009

(PARI) a(n)=core(n, 1)[2] \\ Michel Marcus, Feb 27 2013

(Haskell)

a000188 n = product $ zipWith (^)

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

-- Reinhard Zumkeller, Apr 22 2012

CROSSREFS

a(n) = n/A019554(n).

Cf. A008833, A007913, A117811, A046951, A055210, A027748, A124010, A007913, A007947, A019554. For partial sums see A120486.

Sequence in context: A249739 A249740 A071773 * A162401 A241898 A191090

Adjacent sequences:  A000185 A000186 A000187 * A000189 A000190 A000191

KEYWORD

nonn,easy,nice,mult

AUTHOR

N. J. A. Sloane

EXTENSIONS

Edited by M. F. Hasler, May 08 2014

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified May 31 10:13 EDT 2016. Contains 273543 sequences.