The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A056789 a(n) = Sum_{k=1..n} lcm(k,n)/gcd(k,n). 10
 1, 3, 10, 19, 51, 48, 148, 147, 253, 253, 606, 352, 1015, 738, 960, 1171, 2313, 1263, 3250, 1869, 2803, 3028, 5820, 2784, 6301, 5073, 6814, 5458, 11775, 4798, 14416, 9363, 11505, 11563, 14898, 9343, 24643, 16248, 19276, 14797, 33621, 14013, 38830 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS For prime p, a(p) = 1 + p^2*(p-1)/2. We note lcm(k,n) = k*n iff gcd(k,n) = 1 (and in general lcm(k,n) equals k*n/gcd(k,n)), and so for these values LCM/GCD = k*n. From A023896, we have that Sum_{k=1..n-1: gcd(k,n)=1} k = n*phi(n)/2, and so Sum_{k=1..n-1: gcd(k,n)=1} k*n = n * Sum_{k=1..n-1: gcd(k,n)=1} k = n^2*phi(n)/2. As this is true, certainly Sum_{k=1..n} lcm(k,n)/gcd(k,n) > n^2*phi(n)/2. - Jon Perry, Nov 09 2014 [Edited by Petros Hadjicostas, May 27 2020] Conjecture: for prime p, a(p^n) = 1 + (1/2)*(p - 1)*p^2*(p^(3*n) - 1)/(p^3 - 1) for n = 1,2,3,.... Cf. A339384. - Peter Bala, Dec 04 2020 The conjecture can be proven by splitting up the sum like this: a(p^n) = 1 + Sum_{1 <= r < p^n if gcd(p,r) = 1} lcm(p^n,r)/gcd(p^n,r) + Sum_{1 <= r < p^(n-1) if gcd(p,r) = 1} lcm(p^n,p*r)/gcd(p^n,p*r) + … + Sum_{1 <= r < p if gcd(p,r) = 1} lcm(p^n,p^(n-1)*r)/gcd(p^n,p^(n-1)*r) = 1 + Sum_{1 <= r < p^n if gcd(p,r) = 1} p^n*r + Sum_{1 <= r < p^(n-1) if gcd(p,r) = 1} p^(n-1)*r + … + Sum_{1 <= r < p if gcd(p,r) = 1} p*r = 1 + p^n*(1/2)*p^n*phi(p^n) + p^(n-1)*(1/2)*p^(n-1)*phi(p^(n-1)) + … + p*(1/2)*p*phi(p) = 1 + (1/2)*(p-1)*Sum_{k=1..n} p^(3k-1) = 1 + (1/2)*(p-1)*p^2*(p^(3*n)-1)/(p^3-1). - Sebastian Karlsson, Dec 07 2020 LINKS T. D. Noe, Table of n, a(n) for n = 1..1000 FORMULA a(n) > n^2*phi(n)/2. - Thomas Ordowski, Nov 08 2014 a(n) = Sum_{k=1..n} k*n/gcd(k,n)^2. - Thomas Ordowski, Nov 08 2014 a(n) = (1/2)*Sum_{d|n} d^2*(d+1) Sum_{j|n/d} mu(j)*j^2. - Felix A. Pahl, Nov 23 2019 a(n) = 1 + Sum_{d|n, d > 1} phi(d^3)/2. - Daniel Suteu, Dec 10 2020 From Amiram Eldar, Oct 05 2023: (Start) a(n) = (A068963(n)+1)/2. Sum_{k=1..n} a(k) ~ (Pi^2/120) * n^4. (End) a(n) < n^3 / 2, n > 1. - Bill McEachen, Jul 18 2024 Hence n^3/log log n << a(n) << n^3. - Charles R Greathouse IV, Jul 25 2024 EXAMPLE a(6) = 6/1 + 6/2 + 6/3 + 12/2 + 30/1 + 6/6 = 48. MATHEMATICA Table[ Sum[ LCM[k, n] / GCD[k, n], {k, 1, n}], {n, 1, 50}] f[p_, e_] := p^2*(p-1)*(p^(3*e)-1)/(p^3-1)+1; a[1] = 1; a[n_] := (1 + Times @@ f @@@ FactorInteger[n])/2; Array[a, 40] (* Amiram Eldar, Oct 05 2023 *) PROG (Haskell) a056789 = sum . a051537_row -- Reinhard Zumkeller, Jul 07 2013 (PARI) vector(50, n, sum(k=1, n, lcm(k, n)/gcd(k, n))) \\ Michel Marcus, Nov 08 2014 (PARI) a(n) = sumdiv(n, d, if(d>1, d^2*eulerphi(d)/2, 1)); \\ Daniel Suteu, Dec 10 2020 CROSSREFS Row sums of triangle in A051537. Cf. A023896, A068963, A339384. Sequence in context: A294421 A027177 A048343 * A174476 A098645 A089693 Adjacent sequences: A056786 A056787 A056788 * A056790 A056791 A056792 KEYWORD nonn,easy,nice,changed AUTHOR Leroy Quet, Aug 20 2000 EXTENSIONS Additional comments from Amarnath Murthy, May 09 2002 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 3 23:57 EDT 2024. Contains 374905 sequences. (Running on oeis4.)