login
A368738
a(n) = Sum_{k = 1..n} gcd(3*k + 1, n).
0
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
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
KEYWORD
nonn,mult,easy
AUTHOR
Peter Bala, Jan 05 2024
STATUS
approved