cp's OEIS Frontend

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

%I A178881 #31 Feb 09 2025 09:18:57
%S A178881 0,1,3,7,11,20,26,38,50,67,77,105,117,142,172,204,220,265,283,335,379,
%T A178881 420,442,518,558,607,661,737,765,870,900,980,1052,1117,1199,1331,1367,
%U A178881 1440,1526,1666,1706,1859,1901,2025,2169,2258,2304,2496,2580,2725
%N A178881 Sum of all pairs of greatest common divisors for (i,j) where 1 <= i < j <= n.
%C A178881 You could also be looking for the case where i = j is allowed, which gives A272718(n) = a(n) + n*(n+1)/2.
%H A178881 Akshay Bansal, <a href="/A178881/b178881.txt">Table of n, a(n) for n = 1..10000</a>
%H A178881 Akshay Bansal, <a href="/A178881/a178881.c.txt">C program</a>.
%H A178881 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 A178881 Uva Online Judge Algorithm <a href="http://uva.onlinejudge.org/external/114/11424.html">Problem number 11424</a>.
%F A178881 a(n) = Sum_{i=1..n-1, j=i+1..n} gcd(i,j).
%F A178881 From _Jianing Song_, Feb 07 2021: (Start)
%F A178881 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 A178881 a(n) = A018806(n) - A272718(n).
%F A178881 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)
%e A178881 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
%t A178881 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 *)
%o A178881 (C++)
%o A178881 #include <iostream>
%o A178881 #include <algorithm>
%o A178881 #include <cmath>
%o A178881 using namespace std;
%o A178881 int main() {
%o A178881   int N;
%o A178881   for (N=1;N<=50;++N) {
%o A178881     int G=0,i,j;
%o A178881     for(i=1;i<N;i++)
%o A178881       for(j=i+1;j<=N;j++) {
%o A178881         G+=__gcd(i,j);
%o A178881       }
%o A178881     cout <<G<<",";
%o A178881   }
%o A178881   return 0;
%o A178881 }
%o A178881 (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 A178881 (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 A178881 Cf. A018806, A000010, A001620, A074962, A272718.
%Y A178881 Partial sums of A006579.
%K A178881 nonn
%O A178881 1,3
%A A178881 Enric Cusell (cusell(AT)gmail.com), Jun 20 2010