A178881 - OEIS

%I #24 Jun 24 2022 19:44:38

%S 0,1,3,7,11,20,26,38,50,67,77,105,117,142,172,204,220,265,283,335,379,

%T 420,442,518,558,607,661,737,765,870,900,980,1052,1117,1199,1331,1367,

%U 1440,1526,1666,1706,1859,1901,2025,2169,2258,2304,2496,2580,2725

%N Sum of all pairs of greater common divisors for (i,j) where 1 <= i < j <= n.

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

%H Akshay Bansal, <a href="/A178881/b178881.txt">Table of n, a(n) for n = 1..10000</a>

%H Akshay Bansal, <a href="/A178881/a178881.c.txt">C program</a>

%H Olivier Bordellès, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Bordelles/bordelles90.html">A note on the average order of the gcd-sum function</a>, Journal of Integer Sequences, vol 10 (2007), article 07.3.3.

%H Uva Online Judge Algorithm <a href="http://uva.onlinejudge.org/external/114/11424.html">Problem number 11424</a>

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

%F From _Jianing Song_, Feb 07 2021: (Start)

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

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

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

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

%o (C++)

%o #include <iostream>

%o #include <algorithm>

%o #include <cmath>

%o using namespace std;

%o int main() {

%o   int N;

%o   for (N=1;N<=50;++N) {

%o     int G=0,i,j;

%o     for(i=1;i<N;i++)

%o       for(j=i+1;j<=N;j++) {

%o         G+=__gcd(i,j);

%o       }

%o     cout <<G<<",";

%o   }

%o   return 0;

%o }

%o (PARI) a(n)=sum(k=1, n, eulerphi(k)*(n\k)^2)/2-n*(n+1)/4 \\ _Charles R Greathouse IV_, Apr 11 2016

%o (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

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

%Y Partial sums of A006579.

%K nonn

%O 1,3

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