login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A178881 Sum of all pairs of greater common divisors for (i,j) where 1 <= i < j <= n. 2
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 (list; graph; refs; listen; history; text; internal format)
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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 16:50 EDT 2021. Contains 347586 sequences. (Running on oeis4.)