OFFSET
1,2
FORMULA
a(n) = Sum_{k = 1..n} gcd(4*k+1, n) = Sum_{k = 1..n} gcd(4*k+3, n).
a(n) = Sum_{d divides n} X(d)*phi(d)*n/d, where phi(n) = A000010(n) and X(n) = 1 if n is odd, else 0, that is, X(n) is the principal Dirichlet character of the reduced residue system mod 2. See A000035.
Multiplicative: a(2^k) = 2^k and for odd prime p, a(p^e) = (e + 1)*p^e - e*p^(e-1).
Dirichlet g.f.: (1 - 2/2^s)/(1 - 1/2^s) * zeta(s-1)^2/zeta(s).
Sum_{k=1..n} a(k) ~ n^2*(2*log(n) - 1 + 4*gamma + 4*log(2)/3 - 12*zeta'(2)/Pi^2) / Pi^2, where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Jan 11 2024
MAPLE
seq(add(gcd(2*k+1, n), k = 1..n), n = 1..70);
# alternative faster program for large n
with(numtheory): seq(add(irem(d, 2)*phi(d)*n/d, d in divisors(n)), n = 1..70);
MATHEMATICA
Table[Sum[GCD[2*k + 1, n], {k, 1, n}], {n, 1, 100}] (* Vaclav Kotesovec, Jan 11 2024 *)
PROG
(PARI) a(n) = sum(k = 1, n, gcd(2*k+1, n)); \\ Michel Marcus, Jan 11 2024
CROSSREFS
KEYWORD
nonn,mult,easy
AUTHOR
Peter Bala, Jan 04 2024
STATUS
approved