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