A368736 a(n) = Sum_{k = 1..n} gcd(2*k+1, n).

1, 2, 5, 4, 9, 10, 13, 8, 21, 18, 21, 20, 25, 26, 45, 16, 33, 42, 37, 36, 65, 42, 45, 40, 65, 50, 81, 52, 57, 90, 61, 32, 105, 66, 117, 84, 73, 74, 125, 72, 81, 130, 85, 84, 189, 90, 93, 80, 133, 130, 165, 100, 105, 162, 189, 104, 185, 114, 117, 180, 121, 122, 273, 64, 225, 210, 133, 132, 225, 234

Offset: 1

Author

Peter Bala, Jan 04 2024

Keywords

• nonn
• mult
• easy

Crossrefs

CF. A000010, A018804, A344372, A368737 - A368742.

Programs

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

PARI

a(n) = sum(k = 1, n, gcd(2*k+1, n)); \\ Michel Marcus, Jan 11 2024

Formula

a(2*n) = 2*a(n); a(2*n+1) = A018804(2*n+1) = A344372(2*n+1).

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