|
| |
|
|
A368737
|
|
a(n) = Sum_{k = 1..n} gcd(3*k, n).
|
|
3
|
|
|
|
1, 3, 9, 8, 9, 27, 13, 20, 45, 27, 21, 72, 25, 39, 81, 48, 33, 135, 37, 72, 117, 63, 45, 180, 65, 75, 189, 104, 57, 243, 61, 112, 189, 99, 117, 360, 73, 111, 225, 180, 81, 351, 85, 168, 405, 135, 93, 432, 133, 195, 297, 200, 105, 567, 189, 260, 333, 171, 117, 648, 121, 183, 585, 256, 225, 567, 133, 264, 405, 351
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
a(n) equals the number of solutions to the congruence 3*x*y == 0 (mod n) for 1 <= x, y <= n.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{d divides n} gcd(3, d)*phi(d)*n/d, where phi(n) = A000010(n)
Multiplicative: a(3^k) = (2*k + 1)*3^k and for prime p not equal to 3, a(p^k) = (k + 1)*p^k - k*p^(k-1).
Define D(n) = Sum_{d divides n} a(d). Then
D(3*n+1) = (3*n + 1)*tau(3*n+1) and D(3*n+2) = (3*n + 2)*tau(3*n+2), where tau(n) = A000005(n), the number of divisors of n.
The sequence {(1/9)*( D(3*n) - D(n) ) : n >= 1} begins {1, 4, 5, 12, 10, 20, 14, 32, 21, 40, 22, 60, 26, 56, 50, 80, 34, 84, 38, 120, 70, 88, ...} and appears to be multiplicative.
Dirichlet g.f.: (1 + 3/3^s)/(1 - 1/3^s) * zeta(s-1)^2/zeta(s).
Sum_{k=1..n} a(k) ~ 9*n^2 * (log(n)/2 - 1/4 + gamma - 3*log(3)/16 - 3*zeta'(2)/Pi^2) / Pi^2, where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Jan 11 2024
|
|
|
EXAMPLE
|
a(6) = 27: each of the 36 pairs (x, y), 1 <= x, y <= 6, is a solution to the congruence 3*x*y == 0 (mod 6) except for the 9 pairs (x, y) with both x and y odd.
|
|
|
MAPLE
|
seq(add(gcd(3*k, n), k = 1..n), n = 1..70);
# alternative faster program for large n
with(numtheory): seq(add(gcd(3, d)*phi(d)*n/d, d in divisors(n)), n = 1..70);
|
|
|
MATHEMATICA
|
Table[Sum[GCD[3*k, n], {k, 1, n}], {n, 1, 100}] (* Vaclav Kotesovec, Jan 11 2024 *)
|
|
|
PROG
|
(PARI) a(n) = sum(k = 1, n, gcd(3*k, n)); \\ Michel Marcus, Jan 11 2024
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,mult,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
