OFFSET
1,2
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(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
KEYWORD
nonn,mult,easy
AUTHOR
Peter Bala, Jan 05 2024
STATUS
approved