A063658 The number of integers m in [1..n] for which gcd(m,n) is divisible by a square greater than 1.

0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 3, 0, 0, 0, 4, 0, 2, 0, 5, 0, 0, 0, 6, 1, 0, 3, 7, 0, 0, 0, 8, 0, 0, 0, 12, 0, 0, 0, 10, 0, 0, 0, 11, 5, 0, 0, 12, 1, 2, 0, 13, 0, 6, 0, 14, 0, 0, 0, 15, 0, 0, 7, 16, 0, 0, 0, 17, 0, 0, 0, 24, 0, 0, 3, 19, 0, 0, 0, 20, 9, 0, 0, 21, 0, 0, 0, 22, 0, 10, 0, 23, 0, 0, 0, 24

Offset

1,8

Comments

Haviland (1944) proved that a(n) is the number of those arithmetic progressions among (m*n + s: m >= 0), s = 0, 1, ..., n-1, which contain a finite number of squarefree numbers. - Petros Hadjicostas, Jul 21 2019

Links

Harry J. Smith, Table of n, a(n) for n = 1..2000

E. K. Haviland, An analogue of Euler's phi-function, Duke Math. J. 11 (1944), 869-872.

Formula

Dirichlet g.f.: zeta(s - 1)/zeta(s)*(zeta(s) - zeta(s)/zeta(2*s)). - Geoffrey Critzer, Mar 21 2015

a(n) = Sum_{d|n} phi(n/d) * (1 - mu(d)^2). - Daniel Suteu, Jun 27 2018

Sum_{k=1..n} a(k) ~ n^2 * (1 - 90/Pi^4) / 2. - Vaclav Kotesovec, Feb 01 2019

Example

For n=12 we find gcd(4,12), gcd(8,12) and gcd(12,12) divisible by 4, so a(12) = 3.
From Petros Hadjicostas, Jul 21 2019: (Start)
We have a(2) = 0 because each of the two arithmetic progressions (2*m: m >= 0) and (2*m + 1: m >= 0) contains infinitely many squarefree numbers.
We have a(3) = 0 because each of the three arithmetic progressions (3*m: m >= 0), (3*m + 1: m >= 0), and (3*m + 2: m >= 0) contains infinitely many squarefree numbers.
We have  a(4) = 1 because, among the four arithmetic progressions (4*m: m >= 0), (4*m + 1: m >= 0), (4*m + 2: m >= 0), and (4*m + 3: m >= 0), only the first one contains a finite number of squarefree numbers (in this case, zero!).
We have a(8) = 2 because only the arithmetic progressions (8*m: m >= 0) and (8*m + 4: m >= 0) contain a finite number of squarefree numbers (in this case, zero!).
(End)

Mathematica

f[list_, i_] := list[[i]]; nn = 100; a =Table[EulerPhi[n], {n, 1, nn}]; b =Table[If[Max[FactorInteger[n][[All, 2]]] > 1, 1, 0], {n, 1, nn}]; Table[DirichletConvolve[f[a, n], f[b, n], n, m], {m, 1, nn}] (* Geoffrey Critzer, Mar 21 2015 *)
Table[Sum[EulerPhi[n/d]*(1-MoebiusMu[d]^2), {d, Divisors[n]}], {n, 1, 100}] (* Vaclav Kotesovec, Feb 01 2019 *)

Prog

(PARI) { for (n=1, 2000, a=0; for (m=2, n, if (!issquarefree(gcd(m, n)), a++)); write("b063658.txt", n, " ", a) ) } \\ Harry J. Smith, Aug 27 2009
(PARI) a(n) = sumdiv(n, d, eulerphi(n/d) * (1 - moebius(d)^2)); \\ Daniel Suteu, Jun 27 2018

Crossrefs

a(n) = n - A063659(n).

Sequence in context: A289358 A271698 A113263 * A237053 A364022 A363900

Adjacent sequences: A063655 A063656 A063657 * A063659 A063660 A063661

Keyword

nonn

Author

Floor van Lamoen, Jul 24 2001

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Vladeta Jovovic and Dean Hickerson, Jul 26 2001

Name edited by Petros Hadjicostas, Jul 21 2019

Status

approved