A344372 a(n) = Sum_{k = 1..n} gcd(2*k, n).

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

Offset: 1

Author

Max Alekseyev, May 16 2021

Keywords

• nonn
• mult
• easy

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

Examples

			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
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A106475, A344371, A344373.

Negated bisection of A199084.

Cf. A018804, A332794, A368736 - A368741.

Programs

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

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

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) = A344371(2*n) = -A199084(2*n) = 2*n - A106475(n-1).

a(n) = A018804(n) if n is odd, 4*A018804(n/2) if n is even. - Sebastian Karlsson, Aug 31 2021

From Peter Bala, Jan 11 2023: (Start)

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

a(n) = - A332794(2*n); a(2*n+1) = A368736(2*n+1).

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

Extensions

New name according to the formula by Peter Bala from Vaclav Kotesovec, Jan 13 2024