A368741 a(n) = Sum_{k = 1..n} gcd(5*k + 1, n).

1, 3, 5, 8, 5, 15, 13, 20, 21, 15, 21, 40, 25, 39, 25, 48, 33, 63, 37, 40, 65, 63, 45, 100, 25, 75, 81, 104, 57, 75, 61, 112, 105, 99, 65, 168, 73, 111, 125, 100, 81, 195, 85, 168, 105, 135, 93, 240, 133, 75, 165, 200, 105, 243, 105, 260, 185, 171, 117, 200, 121, 183, 273, 256, 125, 315, 133, 264, 225, 195

Offset

1,2

Links

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

Formula

a(n) = Sum_{k = 1..n} gcd(5*k + r, n) for 1 <= r <= 4.

a(5*n) = 5*a(n); a(5*n+r) = A018804(5*n+r) for 1 <= r <= 4.

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

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

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

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

Maple

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

Mathematica

Table[Sum[GCD[5*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[5, e_] := 5^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(5*k + 1, n)) \\ Andrew Howroyd, Nov 11 2025
(PARI) a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i, 1] == 5, 5^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, A011558, A018804, A368736 - A368742.

Sequence in context: A136188 A073334 A375338 * A021740 A172370 A388447

Adjacent sequences: A368738 A368739 A368740 * A368742 A368743 A368744

Keyword

nonn,mult,easy

Author

Peter Bala, Jan 08 2024

Status

approved