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

%I #99 Jan 24 2024 08:02:57

%S 1,2,3,3,5,6,7,6,8,10,11,9,13,14,15,12,17,16,19,15,21,22,23,18,24,26,

%T 24,21,29,30,31,24,33,34,35,24,37,38,39,30,41,42,43,33,40,46,47,36,48,

%U 48,51,39,53,48,55,42,57,58,59,45,61,62,56,48,65,66,67,51,69,70,71,48

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

%C Equals Möbius transform of A001615. - _Gary W. Adamson_, May 23 2008

%C The absolute values of the Dirichlet inverse of A007913. - _R. J. Mathar_, Dec 22 2010

%H Amiram Eldar, <a href="/A063659/b063659.txt">Table of n, a(n) for n = 1..10000</a>

%H Eckford Cohen, <a href="https://www.jstor.org/stable/2688817">A generalized Euler phi-function</a>, Math. Mag. 41 (1968), 276-279; this is function phi_2(n).

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

%H V. L. Klee, Jr., <a href="https://www.jstor.org/stable/2304963">A generalization of Euler's phi function</a>, Amer. Math. Monthly, 55(6) (1948), 358-359; this is function Phi_2(n).

%H Paul J. McCarthy, <a href="https://www.jstor.org/stable/2309112">On a certain family of arithmetic functions</a>, Amer. Math. Monthly 65 (1958), 586-590; this is function T_2(n).

%H Wolfgang Schramm, <a href="http://www.emis.de/journals/INTEGERS/papers/i50/i50.Abstract.html">The Fourier transform of functions of the greatest common divisor</a>, Electronic Journal of Combinatorial Number Theory 8(1) (2008), #A50; see Example 5 with f(d) = mu(d)^2 (cf. the formulas by _Benoit Cloitre_ below).

%F a(n) = n - A063658(n).

%F Multiplicative with a(p) = p and a(p^e) = p^e-p^(e-2), e>1. - _Vladeta Jovovic_, Jul 26 2001

%F a(n) = Sum_{d|n} phi(d)*mu(n/d)^2, Dirichlet convolution of A000010 and A008966. - _Benoit Cloitre_, Sep 08 2002

%F a(n) = Sum_{k = 1..n} mu(gcd(n,k))^2. - _Benoit Cloitre_, Jun 14 2007

%F Dirichlet g.f.: zeta(s-1)/zeta(2s). - _R. J. Mathar_, Feb 27 2011

%F a(n) = Sum_{k=1..n} psi(gcd(k,n)) * cos(2*Pi*k/n), where psi is A001615. - _Enrique Pérez Herrero_, Jan 18 2013

%F Sum_{k=1..n} a(k) ~ 45*n^2 / Pi^4. - _Vaclav Kotesovec_, Jan 11 2019 [This is a special case of a general result by McCarthy (1958), which was reproved later by Cohen (1968). - _Petros Hadjicostas_, Jul 20 2019]

%F From _Richard L. Ollerton_, May 09 2021: (Start)

%F a(n) = Sum_{k=1..n} mu(gcd(n,k))^2.

%F a(n) = Sum_{k=1..n} mu(n/gcd(n,k))^2*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)

%F G.f.: Sum_{k>=1} mu(k) * x^(k^2) / (1 - x^(k^2))^2. - _Ilya Gutkovskiy_, Aug 20 2021

%F a(n) = Sum_{d divides n} mobius(n/d)*J_2(d)/phi(d); that is, the Dirichlet convolution of the Möbius function A008683(n) and the Dedekind psi function A001615(n), and where the Jordan totient function J_2(n) = A007434(n). - _Peter Bala_, Jan 23 2024

%e For n=12 we find only GCD(4,12), GCD(8,12) and GCD(12,12) divisible by 4, so a(12)=9.

%p A063659 := proc(n)

%p local a,ep,p,e;

%p a := 1 ;

%p for ep in ifactors(n)[2] do

%p p := op(1,ep) ;

%p e := op(2,ep) ;

%p if e = 1 then

%p a := a*p ;

%p else

%p a := a*(p^e-p^(e-2)) ;

%p end if;

%p end do ;

%p a ;

%p end proc:

%p seq(A063659(n),n=1..100) ; # _R. J. Mathar_, Jul 04 2019

%t nn = 72; f[list_, i_] := list[[i]]; a =Table[If[Max[FactorInteger[n][[All, 2]]] < 2, 1, 0], {n, 1, nn}]; b =Table[EulerPhi[n], {n, 1, nn}]; Table[

%t DirichletConvolve[f[a, n], f[b, n], n, m], {m, 1, nn}] (* _Geoffrey Critzer_, Feb 22 2015 *)

%t f[p_, e_] := If[e == 1, p, p^e - p^(e-2)]; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, May 29 2020 *)

%o (PARI) a(n)=sum(k=1,n,moebius(gcd(n,k))^2) \\ _Benoit Cloitre_, Jun 14 2007

%o (PARI) for (n=1, 2000, a=1; for (m=2, n, if (issquarefree(gcd(m, n)), a++)); write("b063659.txt", n, " ", a) ) \\ _Harry J. Smith_, Aug 27 2009

%o (PARI) a(n)=my(f=factor(n)); prod(i=1,#f~, if(f[i,2]>1, f[i,1]^(f[i,2]-2) * (f[i,1]^2 - 1), f[i,1])) \\ _Charles R Greathouse IV_, Jan 08 2018

%Y Cf. A001615.

%Y Absolute values of the Dirichlet inverse of A007913.

%Y Row 2 of A309287.

%K mult,nonn,easy

%O 1,2

%A _Floor van Lamoen_, Jul 24 2001

%E More terms from _Vladeta Jovovic_ and _Dean Hickerson_, Jul 26 2001

%E Name edited by _Petros Hadjicostas_, Jul 21 2019