A368743 a(n) = Sum_{1 <= i, j <= n} gcd(i, j, n)^3.

1, 11, 35, 100, 149, 385, 391, 848, 1017, 1639, 1451, 3500, 2365, 4301, 5215, 6976, 5201, 11187, 7219, 14900, 13685, 15961, 12695, 29680, 19225, 26015, 28107, 39100, 25229, 57365, 30751, 56576, 50785, 57211, 58259, 101700, 52021, 79409, 82775, 126352

Offset: 1

Author

Peter Bala, Jan 20 2024

Keywords

• nonn
• mult
• easy

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• Peter Bala, GCD sum theorems. Two Multivariable Cesaro Type Identities.

Crossrefs

Cf. A007434, A059376, A069097, A343497, A343498, A360428.

Programs

Maple

seq( add(add(igcd(i, j, n)^3, i = 1..n), j = 1..n), n = 1..50);
# faster program for large n
with(numtheory):
A007434 := proc(n) add(d^2*mobius(n/d), d in divisors(n)) end proc:
seq( add(d^3*A007434(n/d), d in divisors(n)), n = 1..500);

Mathematica

f[p_, e_] := p^(3*e - 2)*(p^2 + p + 1) - p^(2*e - 2)*(p + 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jan 29 2024 *)

PARI

a(n) = {my(f = factor(n)); prod(i = 1, #f~, p = f[i,1]; e = f[i,2]; p^(3*e - 2)*(p^2 + p + 1) - p^(2*e - 2)*(p + 1));} \\ Amiram Eldar, Jan 29 2024

Python

from math import prod
from sympy import factorint
def A368743(n): return prod(p**(e-1<<1)*(p**e*(p*(q:=p+1)+1)-q) for p, e in factorint(n).items()) # Chai Wah Wu, Jan 29 2024

Formula

a(n) = Sum_{1 <= i, j, k <= n} gcd(i, j, k, n)^2.

a(n) = Sum_{d divides n} d^3 * J_2(n/d) = Sum_{d divides n} d^2 * J_3(n/d), where the Jordan totient functions J_2(n) = A007434(n) and J_3(n) = A059376(n).

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

a(n) is a multiplicative function: for prime p, a(p^k) = p^(3*k-2)*(p^2 + p + 1) - p^(2*k-2)*(p + 1).

Sum_{k=1..n} a(k) ~ c * n^4, where c = 15/(4*Pi^2) = 0.379954... . - Amiram Eldar, Jan 29 2024

a(n) = Sum_{d divides n} mobius(n/d) * d^2 * sigma(d). - Peter Bala, Jan 29 2024