|
%I #12 Jan 12 2024 22:30:48
%S 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,
%T 75,27,104,57,81,61,112,63,99,117,72,73,111,75,180,81,117,85,168,81,
%U 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
%N a(n) = Sum_{k = 1..n} gcd(3*k + 1, n).
%F a(n) = Sum_{k = 1..n} gcd(3*k + 2, n).
%F a(n) = Sum_{k = 1..n} gcd(9*k + r) for r = 1, 2, 4, 5, 7 and 8.
%F a(3*n) = 3*a(n); a(3*n+1) = A018804(3*n+1); a(3*n+2) = A018804(3*n+2).
%F 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.
%F 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).
%F Dirichlet g.f.: (1 - 3/3^s)/(1 - 1/3^s) * zeta(s-1)^2/zeta(s).
%F 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
%p seq(add(gcd(3*k+1, n), k = 1..n), n = 1..70);
%p # alternative faster program for large n
%p with(numtheory): seq(add(irem(d^2,3)*phi(d)*n/d, d in divisors(n)), n = 1..70);
%t Table[Sum[GCD[3*k+1, n], {k, 1, n}], {n, 1, 100}] (* _Vaclav Kotesovec_, Jan 12 2024 *)
%Y Cf. A000010, A011655, A018804, A368736 - A368742.
%K nonn,mult,easy
%O 1,2
%A _Peter Bala_, Jan 05 2024
|
