login
A368744
a(n) = Sum_{d|n} (-1)^(d+1)*phi(d), where phi(n) = A000010(n).
1
1, 0, 3, -2, 5, 0, 7, -6, 9, 0, 11, -6, 13, 0, 15, -14, 17, 0, 19, -10, 21, 0, 23, -18, 25, 0, 27, -14, 29, 0, 31, -30, 33, 0, 35, -18, 37, 0, 39, -30, 41, 0, 43, -22, 45, 0, 47, -42, 49, 0, 51, -26, 53, 0, 55, -42, 57, 0, 59, -30, 61, 0, 63, -62, 65, 0, 67, -34, 69, 0, 71, -54, 73, 0, 75
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.
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