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

Author

Floor van Lamoen, Jul 24 2001

Keywords

• nonn

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

Examples

			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)
		

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.

Crossrefs

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

Programs

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

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

Formula

Dirichlet g.f.: zeta(s - 1)/zeta(s)*(zeta(s) - zeta(s)/zeta(2*s)) = zeta(s-1)*(zeta(2s)-1)/zeta(2s). - 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

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