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

1, 4, 9, 12, 9, 36, 13, 32, 45, 36, 21, 108, 25, 52, 81, 80, 33, 180, 37, 108, 117, 84, 45, 288, 65, 100, 189, 156, 57, 324, 61, 192, 189, 132, 117, 540, 73, 148, 225, 288, 81, 468, 85, 252, 405, 180, 93, 720, 133, 260, 297, 300, 105, 756, 189, 416, 333, 228, 117, 972, 121, 244, 585, 448

Offset: 1

Author

Peter Bala, Jan 08 2024

Keywords

• nonn
• mult
• easy

Comments

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

Examples

			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.
		

Crossrefs

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

Programs

Maple

seq(add(gcd(6*k, n), k = 1..n), n = 1..70);
# alternative faster program for large n
with(numtheory): seq(add(gcd(6,d)*phi(d)*n/d, d in divisors(n)), n = 1..70);

Mathematica

Table[Sum[GCD[6*k, n], {k, 1, n}], {n, 1, 100}] (* Vaclav Kotesovec, Jan 12 2024 *)

Formula

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

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

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

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

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

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

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).

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

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