A272718 Partial sums of gcd-sum sequence A018804.
1, 4, 9, 17, 26, 41, 54, 74, 95, 122, 143, 183, 208, 247, 292, 340, 373, 436, 473, 545, 610, 673, 718, 818, 883, 958, 1039, 1143, 1200, 1335, 1396, 1508, 1613, 1712, 1829, 1997, 2070, 2181, 2306, 2486, 2567, 2762, 2847, 3015, 3204, 3339, 3432, 3672, 3805, 4000, 4165
Offset: 1
Examples
The gcd-sum function takes values 1,3,5 for n = 1,2,3; therefore a(3) = 1+3+5 = 9.
Links
- Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
- 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.
Programs
-
Mathematica
b[n_] := GCD[n, #]& /@ Range[n] // Total; Array[b, 100] // Accumulate (* Jean-François Alcover, Jun 05 2021 *) f[p_, e_] := (e*(p - 1)/p + 1)*p^e; s[n_] := Times @@ f @@@ FactorInteger[n]; Accumulate[Array[s, 100]] (* Amiram Eldar, Dec 10 2024 *)
-
PARI
first(n)=my(v=vector(n),f); v[1]=1; for(i=2,n, f=factor(i); v[i] = v[i-1] + prod(j=1, #f~, (f[j, 2]*(f[j, 1]-1)/f[j, 1] + 1)*f[j, 1]^f[j, 2])); v \\ Charles R Greathouse IV, May 05 2016
Formula
According to Bordellès (2007), a(n) = (n^2 / (2*zeta(2)))*(log n + gamma - 1/2 + log(A^12/(2*Pi))) + O(n^(1+theta+epsilon)) where 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.
G.f.: (1/(1 - x))*Sum_{k>=1} phi(k)*x^k/(1 - x^k)^2, where phi(k) is the Euler totient function. - Ilya Gutkovskiy, Jan 02 2017
a(n) = (1/2)*Sum_{k=1..n} phi(k) * floor(n/k) * floor(1+n/k), where phi(k) is the Euler totient function. - Daniel Suteu, May 28 2018
From Jianing Song, Feb 07 2021: (Start)
a(n) = Sum_{i=1..n, j=i..n} gcd(i,j).
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) = A178881(n) + n*(n+1)/2.
Comments