A368742 - OEIS

%I #10 Jan 12 2024 22:31:56

%S 1,4,9,12,9,36,13,32,45,36,21,108,25,52,81,80,33,180,37,108,117,84,45,

%T 288,65,100,189,156,57,324,61,192,189,132,117,540,73,148,225,288,81,

%U 468,85,252,405,180,93,720,133,260,297,300,105,756,189,416,333,228,117,972,121,244,585,448

%N a(n) = Sum_{k = 1..n} gcd(6*k, n).

%C a(n) equals the number of solutions to the congruence 6*x*y == 0 (mod n) for 1 <= x, y <= n.

%F a(6*n) = 36*A018804(n); a(6*n+2) = 4*A018804(3*n+1);

%F a(6*n+3) = 9*A018804(2*n+1); a(6*n+4) = 4*A018804(3*n+2);

%F a(6*n+r) = A018804(6*n+r) for r = 1 and 5.

%F Define a_m(n) = Sum_{k = 1..n} gcd(m*k, n). Then

%F a(n) = a_2(n) * a_3(n) / a_1(n) = A344372(n) * A368737(n) / A018804(n).

%F a(n) = Sum_{d divides n} gcd(6, d)*phi(d)*n/d, where phi(n) = A000010(n).

%F Multiplicative: a(2^k) = (k + 1)*2^k, a(3^k) = (2*k + 1)*3^k, and for prime p > 3, a(p^k) = (k + 1)*p^k - k*p^(k-1).

%F Dirichlet g.f.: ( 1 + 3/3^s)/((1 - 1/2^s)*(1 - 1/3^s)) * zeta(s-1)^2/zeta(s).

%F Sum_{k=1..n} a(k) ~ n^2 * (6*log(n) - 3 + 12*gamma - 2*log(2) - 9*log(3)/4 - 36*zeta'(2)/Pi^2) / Pi^2, where gamma is the Euler-Mascheroni constant A001620. - _Vaclav Kotesovec_, Jan 12 2024

%e a(4) = 12: each of the 16 pairs (x, y), 1 <= x, y <= 4, is a solution to the congruence 6*x*y == 0 (mod 4) except for the 4 pairs (1, 1) , (1, 3), (3, 1) and (3, 3) with both x and y odd.

%p seq(add(gcd(6*k, n), k = 1..n), n = 1..70);

%p # alternative faster program for large n

%p with(numtheory): seq(add(gcd(6,d)*phi(d)*n/d, d in divisors(n)), n = 1..70);

%t Table[Sum[GCD[6*k, n], {k, 1, n}], {n, 1, 100}] (* _Vaclav Kotesovec_, Jan 12 2024 *)

%Y Cf. A000010, A018804, A344372, A368736 - A368741.

%K nonn,mult,easy

%O 1,2

%A _Peter Bala_, Jan 08 2024