A368739 a(n) = Sum_{k = 1..n} gcd(4*k, n).

1, 4, 5, 16, 9, 20, 13, 48, 21, 36, 21, 80, 25, 52, 45, 128, 33, 84, 37, 144, 65, 84, 45, 240, 65, 100, 81, 208, 57, 180, 61, 320, 105, 132, 117, 336, 73, 148, 125, 432, 81, 260, 85, 336, 189, 180, 93, 640, 133, 260, 165, 400, 105, 324, 189, 624, 185, 228, 117, 720, 121, 244, 273, 768

Offset: 1

Author

Peter Bala, Jan 07 2024

Keywords

• nonn
• mult
• easy

Crossrefs

Cf. A000010, A018804, A344372, A368736 - A368742.

Programs

Maple

seq(add(gcd(4*k, n), k = 1..n), n = 1..70);
# alternative faster program for large n
with(numtheory): seq(add(gcd(4,d)*phi(d)*n/d, d in divisors(n)), n = 1..70);

Mathematica

Table[Sum[GCD[4*k, n], {k, 1, n}], {n, 1, 100}] (* Vaclav Kotesovec, Jan 12 2024 *)

Formula

a(4*n) = 16*A018804(n); a(4*n+2) = 4*A018804(2*n+1); a(4*n+r) = A018804(4*n+r) for r = 1 and 3.

a(n) = Sum_{d divides n} gcd(4, d)*phi(d)*n/d, where phi(n) = A000010(n)

Multiplicative: a(2^k) = k*2^(k+1) for k >= 1; for odd prime p, a(p^k) = (k + 1)*p^k - k*p^(k-1).

Define D(n) = Sum_{d divides n} a(d). Then

D(4*n+r) = (4*n + r)*tau(4*n+r) for r = 1 and r = 3, where tau(n) = A000005(n), the number of divisors of n.

D(4*n+2) = (5/4)*(4*n + 2)*tau(4*n+2).

The sequence defined for n >= 1 by u(n) = (1/4)*( D(4*n) - D(n) ) begins {5, 16, 30, 44, 50, 96, 70, 112, 135, 160, 110, 264, 130, 224, 300, 272, 170, 432, 190, 440, 420, 352, ...} and appears to be multiplicative: that is, u(1)*u(n*m) = u(n)*u(m) for n and m coprime.

Dirichlet g.f.: (1 + 4/4^s)/(1 - 1/2^s) * zeta(s-1)^2/zeta(s).

Sum_{k=1..n} a(k) ~ n^2 * (5*log(n) - 5/2 + 10*gamma - 11*log(2)/3 - 30*zeta'(2)/Pi^2) / Pi^2, where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Jan 12 2024