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

%I #72 Jan 31 2024 02:00:41

%S 1,4,5,12,9,20,13,32,21,36,21,60,25,52,45,80,33,84,37,108,65,84,45,

%T 160,65,100,81,156,57,180,61,192,105,132,117,252,73,148,125,288,81,

%U 260,85,252,189,180,93,400,133,260,165,300,105,324,189,416,185,228,117,540,121,244,273

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

%C For all n, a(n) >= 2*n - 1, where the equality holds if n is 1 or an odd prime.

%C 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

%H Seiichi Manyama, <a href="/A344372/b344372.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = Sum_{k = 1..2*n} (-1)^k * gcd(k,2*n).

%F 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.

%F a(n) = A344371(2*n) = -A199084(2*n) = 2*n - A106475(n-1).

%F a(n) = A018804(n) if n is odd, 4*A018804(n/2) if n is even. - _Sebastian Karlsson_, Aug 31 2021

%F From _Peter Bala_, Jan 11 2023: (Start)

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

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

%F Dirichlet g.f.: 1/(1 - 1/2^s) * zeta(s-1)^2/zeta(s).

%F Define D(n) = Sum_{d divides n} a(d). Then

%F D(2*n+1) = (2*n + 1)*tau(2*n+1), where tau(n) = A000005(n), the number of divisors of n.

%F 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)

%F 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

%e 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

%p seq(add((-1)^k*gcd(k, 2*n), k = 1..2*n), n = 1..70);

%p # alternative faster program for large n

%p with(numtheory): seq(add(gcd(2,d)*phi(d)*n/d, d in divisors(n)), n = 1..70); # _Peter Bala_, Jan 08 2024

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

%t Table[Sum[GCD[2*k, n], {k, 1, n}], {n, 1, 60}] (* or *)

%t Table[Sum[(-1)^k * GCD[k, 2*n], {k, 1, 2*n}], {n, 1, 60}] (* _Vaclav Kotesovec_, Jan 13 2024 *)

%o (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)) ); }

%o (PARI) a(n) = sum(k=1, 2*n, (-1)^k*gcd(k,2*n)); \\ _Michel Marcus_, May 17 2021

%Y Cf. A106475, A344371, A344373.

%Y Negated bisection of A199084.

%Y Cf. A018804, A332794, A368736 - A368741.

%K nonn,mult,easy

%O 1,2

%A _Max Alekseyev_, May 16 2021

%E New name according to the formula by Peter Bala from _Vaclav Kotesovec_, Jan 13 2024