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!)
A272718 Partial sums of gcd-sum sequence A018804. 6
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

a(n) is the sum of all pairs of greater common divisors for (i,j) where 1 <= i <= j <= n. - Jianing Song, Feb 07 2021

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.

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.

a(n) = A018806(n) - A178881(n). (End)

EXAMPLE

The gcd-sum function takes values 1,3,5 for n=1,2,3; therefore a(3) = 1+3+5=9.

MATHEMATICA

b[n_] := GCD[n, #]& /@ Range[n] // Total;

Array[b, 100] // Accumulate (* Jean-François Alcover, Jun 05 2021 *)

PROG

(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

CROSSREFS

Partial sums of A018804.

Cf. A018806, A000010, A001620, A074962, A178881.

Sequence in context: A170879 A134578 A189979 * A301255 A009851 A026403

Adjacent sequences:  A272715 A272716 A272717 * A272719 A272720 A272721

KEYWORD

nonn,easy,changed

AUTHOR

Gareth McCaughan, May 05 2016

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 June 17 22:14 EDT 2021. Contains 345086 sequences. (Running on oeis4.)