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

Andrew Howroyd, Table of n, a(n) for n = 1..10000

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 *)
f[p_, e_] := (e+1)*p^e - e*p^(e-1); f[3, e_] := 3^e; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 16 2025 *)

Prog

(PARI) a(n)=sum(k=1, n, gcd(3*k + 1, n)) \\ Andrew Howroyd, Nov 15 2025
(PARI) a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i, 1] == 3, 3^f[i, 2], (f[i, 2]+1)*f[i, 1]^f[i, 2] - f[i, 2]*f[i, 1]^(f[i, 2]-1))); } \\ Amiram Eldar, Nov 16 2025

Crossrefs

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

Sequence in context: A021299 A141678 A231855 * A135477 A182473 A383111

Adjacent sequences: A368735 A368736 A368737 * A368739 A368740 A368741

Keyword

nonn,mult,easy

Author

Peter Bala, Jan 05 2024

Status

approved