A178881 Sum of all pairs of greatest common divisors for (i,j) where 1 <= i < j <= n.

0, 1, 3, 7, 11, 20, 26, 38, 50, 67, 77, 105, 117, 142, 172, 204, 220, 265, 283, 335, 379, 420, 442, 518, 558, 607, 661, 737, 765, 870, 900, 980, 1052, 1117, 1199, 1331, 1367, 1440, 1526, 1666, 1706, 1859, 1901, 2025, 2169, 2258, 2304, 2496, 2580, 2725

Offset: 1

Author

Enric Cusell (cusell(AT)gmail.com), Jun 20 2010

Keywords

• nonn

Comments

You could also be looking for the case where i = j is allowed, which gives A272718(n) = a(n) + n*(n+1)/2.

Examples

			Denote gcd(i,j) by (i,j), then a(6) = (1,2) + (1,3) + (1,4) + (1,5) + (1,6) + (2,3) + (2,4) + (2,5) + (2,6) + (3,4) + (3,5) + (3,6) + (4,5) + (4,6) + (5,6) = 20. - _Jianing Song_, Feb 07 2021
		

Links

• Akshay Bansal, Table of n, a(n) for n = 1..10000
• Akshay Bansal, C program.
• Olivier Bordellès, A note on the average order of the gcd-sum function, Journal of Integer Sequences, Vol. 10 (2007), Article 07.3.3.
• Uva Online Judge Algorithm Problem number 11424.

Crossrefs

Cf. A018806, A000010, A001620, A074962, A272718.

Partial sums of A006579.

Programs

Mathematica

f[p_, e_] := (e*(p - 1)/p + 1)*p^e; s[n_] := Times @@ f @@@ FactorInteger[n] - n; Accumulate[Array[s, 100]] (* Amiram Eldar, Dec 10 2024 *)

PARI

a(n)=sum(k=1, n, eulerphi(k)*(n\k)^2)/2-n*(n+1)/4 \\ Charles R Greathouse IV, Apr 11 2016

PARI

first(n)=my(v=vector(n),t); for(k=1,n, t=eulerphi(k); for(m=k,n, v[m] += t*(m\k)^2)); v/2-vector(n,k,k*(k+1)/4) \\ Charles R Greathouse IV, Apr 11 2016

Formula

a(n) = Sum_{i=1..n-1, j=i+1..n} gcd(i,j).

From Jianing Song, Feb 07 2021: (Start)

a(n) = (A018806(n) - n*(n+1)/2) / 2 = (Sum_{k=1..n} phi(k)*(floor(n/k))^2 - n*(n+1)/2) / 2, phi = A000010.

a(n) = A018806(n) - A272718(n).

According to Bordellès (2007), a(n) = (3/Pi^2)*n^2*log(n) + k*n^2 + O(n^(1+theta+epsilon)), where k = (3/Pi^2)*(gamma - 1/2 + log(A^12/(2*Pi))), gamma = A001620, A ~= 1.282427129 is the Glaisher-Kinkelin constant A074962, theta is a certain constant defined in terms of the divisor function and known to lie between 1/4 and 131/416, and epsilon is any positive number. See also A272718. (End)