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