login
A368743
a(n) = Sum_{1 <= i, j <= n} gcd(i, j, n)^3.
8
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,2
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
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,mult,easy
AUTHOR
Peter Bala, Jan 20 2024
STATUS
approved