|
| |
|
|
A344372
|
|
a(n) = Sum_{k = 1..n} gcd(2*k, n).
|
|
15
|
|
|
|
1, 4, 5, 12, 9, 20, 13, 32, 21, 36, 21, 60, 25, 52, 45, 80, 33, 84, 37, 108, 65, 84, 45, 160, 65, 100, 81, 156, 57, 180, 61, 192, 105, 132, 117, 252, 73, 148, 125, 288, 81, 260, 85, 252, 189, 180, 93, 400, 133, 260, 165, 300, 105, 324, 189, 416, 185, 228, 117, 540, 121, 244, 273
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
For all n, a(n) >= 2*n - 1, where the equality holds if n is 1 or an odd prime.
a(n) equals the number of solutions to the congruence 2*x*y == 0 (mod n) for 1 <= x, y <= n. - Peter Bala, Jan 11 2024
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{k = 1..2*n} (-1)^k * gcd(k,2*n).
a(n) is multiplicative with a(2^d) = (d+1)*2^d, and a(p^d) = (d+1)*p^d - d*p^(d-1) for an odd prime p, d >= 1.
a(n) = Sum_{d divides n} phi(2*d)*n/d, where phi(n) = A000010(n).
Dirichlet g.f.: 1/(1 - 1/2^s) * zeta(s-1)^2/zeta(s).
Define D(n) = Sum_{d divides n} a(d). Then
D(2*n+1) = (2*n + 1)*tau(2*n+1), where tau(n) = A000005(n), the number of divisors of n.
The sequence {(1/4)*( D(2*n) - D(n) ) : n >= 1} begins {1, 3, 6, 8, 10, 18, 14, 20, 27, 30, 22, 48, 26, 42, 60, 48, 34, 81, 38, 80, 84, 66, ...} and appears to be multiplicative. (End)
Sum_{k=1..n} a(k) ~ 4*n^2 * (log(n) - 1/2 + 2*gamma - log(2)/3 - 6*zeta'(2)/Pi^2) / Pi^2, where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Jan 12 2024
|
|
|
EXAMPLE
|
a(6) = 20: the 20 solutions to the congruence 2*x*y == 0 (mod 6) for 1 <= x, y <= 6 are the pairs (x, y) = (k, 6) for 1 <= k <= 6, the pairs (6, k) for 1 <= k <= 5, the pairs (3, k) for 1 <= k <= 5 and the pairs (1, 3), (2, 3), (4, 3) and (5, 3). - Peter Bala, Jan 11 2024
|
|
|
MAPLE
|
seq(add((-1)^k*gcd(k, 2*n), k = 1..2*n), n = 1..70);
# alternative faster program for large n
with(numtheory): seq(add(gcd(2, d)*phi(d)*n/d, d in divisors(n)), n = 1..70); # Peter Bala, Jan 08 2024
|
|
|
MATHEMATICA
|
f[p_, e_] := (e + 1)*p^e - e*p^(e - 1); f[2, e_] := (e + 1)*2^e; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 20 2022 *)
Table[Sum[GCD[2*k, n], {k, 1, n}], {n, 1, 60}] (* or *)
Table[Sum[(-1)^k * GCD[k, 2*n], {k, 1, 2*n}], {n, 1, 60}] (* Vaclav Kotesovec, Jan 13 2024 *)
|
|
|
PROG
|
(PARI) { A344372(n) = my(f=factor(n)); prod(i=1, #f~, (f[i, 2]+1)*f[i, 1]^f[i, 2] - if(f[i, 1]>2, f[i, 2]*f[i, 1]^(f[i, 2]-1)) ); }
(PARI) a(n) = sum(k=1, 2*n, (-1)^k*gcd(k, 2*n)); \\ Michel Marcus, May 17 2021
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,mult,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
New name according to the formula by Peter Bala from Vaclav Kotesovec, Jan 13 2024
|
|
|
STATUS
|
approved
|
| |
|
|
