A368738 a(n) = Sum_{k = 1..n} gcd(3*k + 1, n).

1, 3, 3, 8, 9, 9, 13, 20, 9, 27, 21, 24, 25, 39, 27, 48, 33, 27, 37, 72, 39, 63, 45, 60, 65, 75, 27, 104, 57, 81, 61, 112, 63, 99, 117, 72, 73, 111, 75, 180, 81, 117, 85, 168, 81, 135, 93, 144, 133, 195, 99, 200, 105, 81, 189, 260, 111, 171, 117, 216, 121, 183, 117, 256, 225, 189, 133, 264, 135, 351

Offset

1,2

Links

Table of n, a(n) for n=1..70.

Formula

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

a(n) = Sum_{k = 1..n} gcd(9*k + r) for r = 1, 2, 4, 5, 7 and 8.

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

a(n) = Sum_{d divides n} X(d)*phi(d)*n/d, where phi(n) = A000010(n) and X(n) = A011655(n) is the principal Dirichlet character of the reduced residue system mod 3.

Multiplicative: a(3^k) = 3^k and for prime p not equal to 3, a(p^k) = (k + 1)*p^k - k*p^(k-1).

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

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

Maple

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

Mathematica

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

Crossrefs

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

Sequence in context: A021299 A141678 A231855 * A135477 A182473 A363125

Adjacent sequences: A368735 A368736 A368737 * A368739 A368740 A368741

Keyword

nonn,mult,easy

Author

Peter Bala, Jan 05 2024

Status

approved