cp's OEIS Frontend

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

%I A174405 #46 Aug 02 2025 08:28:56
%S A174405 1,4,11,22,43,64,107,150,211,274,385,462,619,748,895,1066,1339,1522,
%T A174405 1865,2096,2397,2730,3237,3538,4059,4530,5077,5550,6363,6804,7735,
%U A174405 8418,9195,10014,10917,11588,12921,13950,15049,15952,17593,18496,20303,21524,22805,24326,26489,27686,29787,31350,33261,34988
%N A174405 Partial sums of Sum_{k=1..n} n/gcd(n,k), or partial sums of Sum_{d|n} d*phi(d) (see A057660).
%C A174405 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.
%H A174405 Amiram Eldar, <a href="/A174405/b174405.txt">Table of n, a(n) for n = 1..10000</a>
%H A174405 Marko Riedel, <a href="http://math.stackexchange.com/a/787082/1778">answer to 'Euler phi function, number theory'</a>, MathStackExchange, 2014.
%H A174405 Günter Rote, Moritz Rüber, and Morteza Saghafian, <a href="https://arxiv.org/abs/2402.15787">Grid Peeling of Parabolas</a>, arXiv:2402.15787 [cs.CG], 2024. See p. 9.
%H A174405 J. Sándor and A. V. Kramer, <a href="http://www.moravica.ftn.kg.ac.rs/Vol_3/10-Sandor-Kramer.pdf">Über eine zahlentheoretische Funktion</a>. Mathematica Moravica, 3 (1999), 53-62.
%F A174405 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).
%F A174405 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
%F A174405 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
%F A174405 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
%e A174405 a(9) = 1 + 3 + 7 + 11 + 21 + 21 + 43 + 43 + 61 = 211 is prime.
%t A174405 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 *)
%o A174405 (PARI) a(n)=sum(k=1,n,sumdiv(k,d,eulerphi(d)*d)) \\ _Charles R Greathouse IV_, May 21 2014
%o A174405 (PARI) a(n) = sum(k=1, n, k * eulerphi(k) * (n\k)); \\ _Michel Marcus_, May 30 2018
%Y A174405 Cf. A000010, A057660.
%K A174405 nonn
%O A174405 1,2
%A A174405 _Jonathan Vos Post_, Nov 27 2010