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
Examples
For n=12 we find only GCD(4,12), GCD(8,12) and GCD(12,12) divisible by 4, so a(12)=9.
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).
Programs
-
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 *) -
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
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
Extensions
More terms from Vladeta Jovovic and Dean Hickerson, Jul 26 2001
Name edited by Petros Hadjicostas, Jul 21 2019
Comments