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

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, 24, 21, 29, 30, 31, 24, 33, 34, 35, 24, 37, 38, 39, 30, 41, 42, 43, 33, 40, 46, 47, 36, 48, 48, 51, 39, 53, 48, 55, 42, 57, 58, 59, 45, 61, 62, 56, 48, 65, 66, 67, 51, 69, 70, 71, 48

Offset

1,2

Comments

Equals Möbius transform of A001615. - Gary W. Adamson, May 23 2008

The absolute values of the Dirichlet inverse of A007913. - R. J. Mathar, Dec 22 2010

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000

Eckford Cohen, A generalized Euler phi-function, Math. Mag. 41 (1968), 276-279; this is function phi_2(n).

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

V. L. Klee, Jr., A generalization of Euler's phi function, Amer. Math. Monthly, 55(6) (1948), 358-359; this is function Phi_2(n).

Paul J. McCarthy, On a certain family of arithmetic functions, Amer. Math. Monthly 65 (1958), 586-590; this is function T_2(n).

Wolfgang Schramm, The Fourier transform of functions of the greatest common divisor, 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).

Formula

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

Multiplicative with a(p) = p and a(p^e) = p^e-p^(e-2), e>1. - Vladeta Jovovic, Jul 26 2001

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

a(n) = Sum_{k = 1..n} mu(gcd(n,k))^2. - Benoit Cloitre, Jun 14 2007

Dirichlet g.f.: zeta(s-1)/zeta(2s). - R. J. Mathar, Feb 27 2011

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

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]

From Richard L. Ollerton, May 09 2021: (Start)

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

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

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

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

Example

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

Maple

A063659 := proc(n)
    local a, ep, p, e;
    a := 1 ;
    for ep in ifactors(n)[2] do
        p := op(1, ep) ;
        e := op(2, ep) ;
        if e = 1 then
            a := a*p ;
        else
            a := a*(p^e-p^(e-2)) ;
        end if;
    end do ;
    a ;
end proc:
seq(A063659(n), n=1..100) ; # R. J. Mathar, Jul 04 2019

Mathematica

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[
DirichletConvolve[f[a, n], f[b, n], n, m], {m, 1, nn}] (* Geoffrey Critzer, Feb 22 2015 *)
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 *)

Prog

(PARI) a(n)=sum(k=1, n, moebius(gcd(n, k))^2) \\ Benoit Cloitre, Jun 14 2007
(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
(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

Crossrefs

Cf. A001615.

Absolute values of the Dirichlet inverse of A007913.

Row 2 of A309287.

Sequence in context: A277886 A359588 A337868 * A255563 A331288 A115350

Adjacent sequences: A063656 A063657 A063658 * A063660 A063661 A063662

Keyword

mult,nonn,easy

Author

Floor van Lamoen, Jul 24 2001

Extensions

More terms from Vladeta Jovovic and Dean Hickerson, Jul 26 2001

Name edited by Petros Hadjicostas, Jul 21 2019

Status

approved