OFFSET
1,3
COMMENTS
Recall Gauss's identity Sum_{d|n} phi(d) = n.
a(n) is a multiplicative function of n since both (-1)^(n+1) and phi(n) are multiplicative functions of n.
LINKS
Paolo Xausa, Table of n, a(n) for n = 1..10000
FORMULA
a(n) = -Sum_{k = 1..n} (-1)^(lcm(k, n)/k) = -Sum_{k = 1..n} (-1)^(n/gcd(k, n)).
a(2*n+1) = 2*n + 1; a(4*n+2) = 0.
Multiplicative: a(2^k) = 2 - 2^k and for odd prime p, a(p^k) = p^k.
Dirichlet g.f.: (1 - 3/2^s)/(1 - 1/2^s) * zeta(s-1).
From Amiram Eldar, Jan 31 2024: (Start)
a(n) = (2/A006519(n) - 1) * n.
Sum_{k=1..n} a(k) ~ n^2/6. (End)
MAPLE
with(numtheory): seq( add( (-1)^(d+1)*phi(d), d in divisors(n)), n = 1..75);
MATHEMATICA
A368744[n_] := DivisorSum[n, (-1)^(#+1)*EulerPhi[#]&];
Array[A368744, 100] (* Paolo Xausa, Jan 30 2024 *)
a[n_] := (2^(1-IntegerExponent[n, 2]) - 1) * n ; Array[a, 100] (* Amiram Eldar, Jan 31 2024 *)
PROG
(PARI) a(n) = sumdiv(n, d, (-1)^(d+1)*eulerphi(d)); \\ Michel Marcus, Jan 30 2024
(PARI) a(n) = (2/(1<<valuation(n, 2)) - 1) * n; \\ Amiram Eldar, Jan 31 2024
(Python)
def A368744(n): return ((n<<1)>>(~n & n-1).bit_length())-n # Chai Wah Wu, Jan 30 2024
CROSSREFS
KEYWORD
sign,mult,easy
AUTHOR
Peter Bala, Jan 21 2024
STATUS
approved