A057660 a(n) = Sum_{k=1..n} n/gcd(n,k).

1, 3, 7, 11, 21, 21, 43, 43, 61, 63, 111, 77, 157, 129, 147, 171, 273, 183, 343, 231, 301, 333, 507, 301, 521, 471, 547, 473, 813, 441, 931, 683, 777, 819, 903, 671, 1333, 1029, 1099, 903, 1641, 903, 1807, 1221, 1281, 1521, 2163, 1197, 2101, 1563, 1911, 1727

Offset: 1

Author

Henry Gould, Oct 15 2000

Keywords

• easy
• nice
• nonn
• mult

Comments

Also sum of the orders of the elements in a cyclic group with n elements, i.e., row sums of A054531. - Avi Peretz (njk(AT)netvision.net.il), Mar 31 2001

Also inverse Moebius transform of EulerPhi(n^2), A002618.

Sequence is multiplicative with a(p^e) = (p^(2*e+1)+1)/(p+1). Example: a(10) = a(2)*a(5) = 3*21 = 63.

a(n) is the number of pairs (a, b) such that the equation ax = b is solvable in the ring (Zn, +, x). See the Mathematical Reflections link. - Michel Marcus, Jan 07 2017

From Jake Duzyk, Jun 06 2023: (Start)

These are the "contraharmonic means" of the improper divisors of square integers (inclusive of 1 and the square integer itself).

Permitting "Contraharmonic Divisor Numbers" to be defined analogously to Øystein Ore's Harmonic Divisor Numbers, the only numbers for which there exists an integer contraharmonic mean of the divisors are the square numbers, and a(n) is the n-th integer contraharmonic mean, expressible also as the sum of squares of divisors of n^2 divided by the sum of divisors of n^2. That is, a(n) = sigma_2(n^2)/sigma(n^2).

(a(n) = A001157(k)/A000203(k) where k is the n-th number such that A001157(k)/A000203(k) is an integer, i.e., k = n^2.)

This sequence is an analog of A001600 (Harmonic means of divisors of harmonic numbers) and A102187 (Arithmetic means of divisors of arithmetic numbers). (End)

References

• David M. Burton, Elementary Number Theory, Allyn and Bacon Inc., Boston MA, 1976, p. 152.
• H. W. Gould and Temba Shonhiwa, Functions of GCD's and LCM's, Indian J. Math. (Allahabad), Vol. 39, No. 1 (1997), pp. 11-35.
• H. W. Gould and Temba Shonhiwa, A generalization of Cesaro's function and other results, Indian J. Math. (Allahabad), Vol. 39, No. 2 (1997), pp. 183-194.

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
• Habib Amiri and S. M. Jafarian Amiri, Sum of element orders on finite groups of the same order, J. Algebra Appl. 10 (2011), no. 2, 187--190. MR2795731 (2012d:20050)
• Habib Amiri, S. M. Jafarian Amiri, and I. M. Isaacs, Sums of element orders in finite groups Comm. Algebra 37 (2009), no. 9, 2978--2980. MR2554185 (2010i:20022)
• Miriam Mahannah El-Farrah, Expectation Numbers of Cyclic Groups, MS Thesis, Western Kentucky University, August 2015.
• Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 154-5.
• Walther Janous, Problem 10829, Amer. Math. Monthly, 107 (2000), p. 753.
• Yadollah Marefat, Ali Iranmanesh, and Abolfazl Tehranian, On the sum of element orders of finite simple groups, J. Algebra Applications, 12 (2013), #1350026.
• Mathematical Reflections, Solution to Problem U338, Issue 4, 2015, p 17.
• Joachim von zur Gathen, Arnold Knopfmacher, Florian Luca, Lutz G. Lucht, and Igor E. Shparlinski, Average order of cyclic groups, J. Théorie Nombres Bordeaux 16 (1) (2004) 107-123.

Crossrefs

Cf. A000010, A000203, A000290, A001157, A018804, A050873, A051193, A054522, A057661, A061255, A065764, A078747, A174405 (partial sums), A176797, A226512.

Cf. A308471.

Programs

Haskell

a057660 n = sum $ map (div n) $ a050873_row n
-- Reinhard Zumkeller, Nov 25 2013

Mathematica

Table[ DivisorSigma[ 2, n^2 ] / DivisorSigma[ 1, n^2 ], {n, 1, 128} ]
Table[Total[Denominator[Range[n]/n]], {n, 55}] (* Alonso del Arte, Oct 07 2011 *)
f[p_, e_] := (p^(2*e + 1) + 1)/(p + 1); a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Nov 21 2020 *)

PARI

a(n)=if(n<1,0,sumdiv(n,d,d*eulerphi(d)))

PARI

a(n)=sumdivmult(n,d, eulerphi(d)*d) \\ Charles R Greathouse IV, Sep 09 2014

Python

from math import gcd
def A057660(n): return sum(n//gcd(n,k) for k in range(1,n+1)) # Chai Wah Wu, Aug 24 2023

Python

from math import prod
from sympy import factorint
def A057660(n): return prod((p**((e<<1)+1)+1)//(p+1) for p,e in factorint(n).items()) # Chai Wah Wu, Aug 05 2024

Formula

a(n) = Sum_{d|n} d*A000010(d) = Sum_{d|n} d*A054522(n,d), sum of d times phi(d) for all divisors d of n, where phi is Euler's phi function.

a(n) = sigma_2(n^2)/sigma_1(n^2) = A001157(A000290(n))/A000203(A000290(n)) = A001157(A000290(n))/A065764(n). - Labos Elemer, Nov 21 2001

a(n) = Sum_{d|n} A000010(d^2). - Enrique Pérez Herrero, Jul 12 2010

a(n) <= (n-1)*n + 1, with equality if and only if n is noncomposite. - Daniel Forgues, Apr 30 2013

G.f.: Sum_{n >= 1} n*phi(n)*x^n/(1 - x^n) = x + 3*x^2 + 7*x^3 + 11*x^4 + .... Dirichlet g.f.: sum {n >= 1} a(n)/n^s = zeta(s)*zeta(s-2)/zeta(s-1) for Re s > 3. Cf. A078747 and A176797. - Peter Bala, Dec 30 2013

a(n) = Sum_{i=1..n} numerator(n/i). - Wesley Ivan Hurt, Feb 26 2017

L.g.f.: -log(Product_{k>=1} (1 - x^k)^phi(k)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 21 2018

From Richard L. Ollerton, May 10 2021: (Start)

a(n) = Sum_{k=1..n} lcm(n,k)/k.

a(n) = Sum_{k=1..n} gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)

From Vaclav Kotesovec, Jun 13 2021: (Start)

Sum_{k=1..n} a(k)/k ~ 3*zeta(3)*n^2/Pi^2.

Sum_{k=1..n} k^2/a(k) ~ A345294 * n.

Sum_{k=1..n} k*A000010(k)/a(k) ~ A345295 * n. (End)

Sum_{k=1..n} a(k) ~ 2*zeta(3)*n^3/Pi^2. - Vaclav Kotesovec, Jun 10 2023

Extensions

More terms from James Sellers, Oct 16 2000