|
%I #17 Jan 12 2024 22:26:39
%S 1,2,5,4,9,10,13,8,21,18,21,20,25,26,45,16,33,42,37,36,65,42,45,40,65,
%T 50,81,52,57,90,61,32,105,66,117,84,73,74,125,72,81,130,85,84,189,90,
%U 93,80,133,130,165,100,105,162,189,104,185,114,117,180,121,122,273,64,225,210,133,132,225,234
%N a(n) = Sum_{k = 1..n} gcd(2*k+1, n).
%F a(2*n) = 2*a(n); a(2*n+1) = A018804(2*n+1) = A344372(2*n+1).
%F a(n) = Sum_{k = 1..n} gcd(4*k+1, n) = Sum_{k = 1..n} gcd(4*k+3, n).
%F a(n) = Sum_{d divides n} X(d)*phi(d)*n/d, where phi(n) = A000010(n) and X(n) = 1 if n is odd, else 0, that is, X(n) is the principal Dirichlet character of the reduced residue system mod 2. See A000035.
%F Multiplicative: a(2^k) = 2^k and for odd prime p, a(p^e) = (e + 1)*p^e - e*p^(e-1).
%F Dirichlet g.f.: (1 - 2/2^s)/(1 - 1/2^s) * zeta(s-1)^2/zeta(s).
%F Sum_{k=1..n} a(k) ~ n^2*(2*log(n) - 1 + 4*gamma + 4*log(2)/3 - 12*zeta'(2)/Pi^2) / Pi^2, where gamma is the Euler-Mascheroni constant A001620. - _Vaclav Kotesovec_, Jan 11 2024
%p seq(add(gcd(2*k+1, n), k = 1..n), n = 1..70);
%p # alternative faster program for large n
%p with(numtheory): seq(add(irem(d,2)*phi(d)*n/d, d in divisors(n)), n = 1..70);
%t Table[Sum[GCD[2*k + 1, n], {k, 1, n}], {n, 1, 100}] (* _Vaclav Kotesovec_, Jan 11 2024 *)
%o (PARI) a(n) = sum(k = 1, n, gcd(2*k+1, n)); \\ _Michel Marcus_, Jan 11 2024
%Y CF. A000010, A018804, A344372, A368737 - A368742.
%K nonn,mult,easy
%O 1,2
%A _Peter Bala_, Jan 04 2024
|
