A178881 Sum of all pairs of greater 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,3

Comments

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

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

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)) - 1/2, 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)

Example

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

Prog

(C++)
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
  int N;
  for (N=1; N<=50; ++N) {
    int G=0, i, j;
    for(i=1; i<N; i++)
      for(j=i+1; j<=N; j++) {
        G+=__gcd(i, j);
      }
    cout <<G<<", ";
  }
  return 0;
}
(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

Crossrefs

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

Partial sums of A006579.

Sequence in context: A050577 A283178 A284298 * A244001 A333695 A061258

Adjacent sequences: A178878 A178879 A178880 * A178882 A178883 A178884

Keyword

nonn

Author

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

Status

approved