A063658 - OEIS

%I #35 Jul 21 2019 09:09:25

%S 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,

%T 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,

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

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

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

%H Harry J. Smith, <a href="/A063658/b063658.txt">Table of n, a(n) for n = 1..2000</a>

%H E. K. Haviland, <a href="https://projecteuclid.org/euclid.dmj/1077472821">An analogue of Euler's phi-function</a>, Duke Math. J. 11 (1944), 869-872.

%F Dirichlet g.f.: zeta(s - 1)/zeta(s)*(zeta(s) - zeta(s)/zeta(2*s)). - _Geoffrey Critzer_, Mar 21 2015

%F a(n) = Sum_{d|n} phi(n/d) * (1 - mu(d)^2). - _Daniel Suteu_, Jun 27 2018

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

%e For n=12 we find gcd(4,12), gcd(8,12) and gcd(12,12) divisible by 4, so a(12) = 3.

%e From _Petros Hadjicostas_, Jul 21 2019: (Start)

%e 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.

%e 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.

%e 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!).

%e 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!).

%e (End)

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

%t Table[Sum[EulerPhi[n/d]*(1-MoebiusMu[d]^2), {d, Divisors[n]}], {n, 1, 100}] (* _Vaclav Kotesovec_, Feb 01 2019 *)

%o (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

%o (PARI) a(n) = sumdiv(n, d, eulerphi(n/d) * (1 - moebius(d)^2)); \\ _Daniel Suteu_, Jun 27 2018

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

%K nonn

%O 1,8

%A _Floor van Lamoen_, Jul 24 2001

%E More terms from Larry Reeves (larryr(AT)acm.org), _Vladeta Jovovic_ and Dean Hickerson, Jul 26 2001

%E Name edited by _Petros Hadjicostas_, Jul 21 2019