A174405 Partial sums of Sum_{k=1..n} n/gcd(n,k), or partial sums of Sum_{d|n} d*phi(d) (see A057660).

1, 4, 11, 22, 43, 64, 107, 150, 211, 274, 385, 462, 619, 748, 895, 1066, 1339, 1522, 1865, 2096, 2397, 2730, 3237, 3538, 4059, 4530, 5077, 5550, 6363, 6804, 7735, 8418, 9195, 10014, 10917, 11588, 12921, 13950, 15049, 15952, 17593, 18496, 20303, 21524, 22805, 24326, 26489, 27686, 29787, 31350, 33261, 34988

Offset: 1

Author

Jonathan Vos Post, Nov 27 2010

Keywords

• nonn

Comments

The subsequence of primes in this sequence begins 11, 43, 107, 211, 619, 5077, 26489. The subsequence of squares in this sequence begins 1, 4, 64, 18496 = 2^6 * 17^2.

Examples

			a(9) = 1 + 3 + 7 + 11 + 21 + 21 + 43 + 43 + 61 = 211 is prime.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• Marko Riedel, answer to 'Euler phi function, number theory', MathStackExchange, 2014.
• Günter Rote, Moritz Rüber, and Morteza Saghafian, Grid Peeling of Parabolas, arXiv:2402.15787 [cs.CG], 2024. See p. 9.
• J. Sándor and A. V. Kramer, Über eine zahlentheoretische Funktion. Mathematica Moravica, 3 (1999), 53-62.

Crossrefs

Cf. A000010, A057660.

Programs

Mathematica

f[p_, e_] := (p^(2*e + 1) + 1)/(p + 1); a[n_] := Times @@ (f @@@ FactorInteger[n]); Accumulate @ Array[a, 100] (* Amiram Eldar, Nov 21 2020 *)

PARI

a(n)=sum(k=1,n,sumdiv(k,d,eulerphi(d)*d)) \\ Charles R Greathouse IV, May 21 2014

PARI

a(n) = sum(k=1, n, k * eulerphi(k) * (n\k)); \\ Michel Marcus, May 30 2018

Formula

a(n) = Sum_{i=1..n} A057660(i) = Sum_{i=1..n} Sum_{k=1..i} i/gcd(i,k) = Sum_{i=1..n} ( Sum_{d|i} A000010(d^2) ) = Sum_{i=1..n} ( Sum_{d|i} d*A000010(d) ) = Sum_{i=1..n} (sum of the orders of the elements in a cyclic group with i elements).

Riedel, and Sándor&Kramer give a(n) ~ 2/Pi^2 * zeta(3) * n^3. - Charles R Greathouse IV, May 21 2014; Günter Rote, Nov 03 2021

G.f.: (1/(1 - x))*Sum_{k>=1} k*phi(k)*x^k/(1 - x^k), where phi() is the Euler totient function (A000010). - Ilya Gutkovskiy, Aug 31 2017

a(n) = Sum_{k=1..n} k * phi(k) * floor(n/k), where phi(k) is the Euler totient function. - Daniel Suteu, May 30 2018