login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A063659 The number of integers m in [1..n] for which gcd(m,n) is not divisible by a square greater than 1. 14
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 (list; graph; refs; listen; history; text; internal format)
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]

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: A097246 A277886 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 23 21:51 EST 2020. Contains 338603 sequences. (Running on oeis4.)