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

%I #168 Aug 05 2024 01:56:32

%S 1,3,7,11,21,21,43,43,61,63,111,77,157,129,147,171,273,183,343,231,

%T 301,333,507,301,521,471,547,473,813,441,931,683,777,819,903,671,1333,

%U 1029,1099,903,1641,903,1807,1221,1281,1521,2163,1197,2101,1563,1911,1727

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

%C 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

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

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

%C 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

%C From _Jake Duzyk_, Jun 06 2023: (Start)

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

%C 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).

%C (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.)

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

%D David M. Burton, Elementary Number Theory, Allyn and Bacon Inc., Boston MA, 1976, p. 152.

%D 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.

%D 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.

%H Amiram Eldar, <a href="/A057660/b057660.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe)

%H Habib Amiri and S. M. Jafarian Amiri, <a href="http://dx.doi.org/10.1142/S0219498811004057">Sum of element orders on finite groups of the same order</a>, J. Algebra Appl. 10 (2011), no. 2, 187--190. MR2795731 (2012d:20050)

%H Habib Amiri, S. M. Jafarian Amiri, and I. M. Isaacs, <a href="http://dx.doi.org/10.1080/00927870802502530">Sums of element orders in finite groups</a> Comm. Algebra 37 (2009), no. 9, 2978--2980. MR2554185 (2010i:20022)

%H Miriam Mahannah El-Farrah, <a href="https://digitalcommons.wku.edu/theses/1518/">Expectation Numbers of Cyclic Groups</a>, MS Thesis, Western Kentucky University, August 2015.

%H Steven R. Finch, <a href="https://doi.org/10.1017/9781316997741">Mathematical Constants II</a>, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 154-5.

%H Walther Janous, <a href="http://www.jstor.org/stable/2695482">Problem 10829</a>, Amer. Math. Monthly, 107 (2000), p. 753.

%H Yadollah Marefat, Ali Iranmanesh, and Abolfazl Tehranian, <a href="http://dx.doi.org/10.1142/S0219498813500266">On the sum of element orders of finite simple groups</a>, J. Algebra Applications, 12 (2013), #1350026.

%H Mathematical Reflections, <a href="https://www.awesomemath.org/wp-pdf-files/math-reflections/mr-2015-04/mr_3_2015_solutions.pdf">Solution to Problem U338</a>, Issue 4, 2015, p 17.

%H Joachim von zur Gathen, Arnold Knopfmacher, Florian Luca, Lutz G. Lucht, and Igor E. Shparlinski, <a href="https://doi.org/10.5802/jtnb.436">Average order of cyclic groups</a>, J. Théorie Nombres Bordeaux 16 (1) (2004) 107-123.

%F 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.

%F 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

%F a(n) = Sum_{d|n} A000010(d^2). - _Enrique Pérez Herrero_, Jul 12 2010

%F a(n) <= (n-1)*n + 1, with equality if and only if n is noncomposite. - _Daniel Forgues_, Apr 30 2013

%F 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

%F a(n) = Sum_{i=1..n} numerator(n/i). - _Wesley Ivan Hurt_, Feb 26 2017

%F 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

%F From _Richard L. Ollerton_, May 10 2021: (Start)

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

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

%F From _Vaclav Kotesovec_, Jun 13 2021: (Start)

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

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

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

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

%t Table[ DivisorSigma[ 2, n^2 ] / DivisorSigma[ 1, n^2 ], {n, 1, 128} ]

%t Table[Total[Denominator[Range[n]/n]], {n, 55}] (* _Alonso del Arte_, Oct 07 2011 *)

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

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

%o (PARI) a(n)=sumdivmult(n,d, eulerphi(d)*d) \\ _Charles R Greathouse IV_, Sep 09 2014

%o (Haskell)

%o a057660 n = sum $ map (div n) $ a050873_row n

%o -- _Reinhard Zumkeller_, Nov 25 2013

%o (Python)

%o from math import gcd

%o def A057660(n): return sum(n//gcd(n,k) for k in range(1,n+1)) # _Chai Wah Wu_, Aug 24 2023

%o (Python)

%o from math import prod

%o from sympy import factorint

%o 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

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

%Y Cf. A308471.

%K easy,nice,nonn,mult

%O 1,2

%A _Henry Gould_, Oct 15 2000

%E More terms from _James A. Sellers_, Oct 16 2000