A062355 a(n) = d(n) * phi(n), where d(n) is the number of divisors function.

1, 2, 4, 6, 8, 8, 12, 16, 18, 16, 20, 24, 24, 24, 32, 40, 32, 36, 36, 48, 48, 40, 44, 64, 60, 48, 72, 72, 56, 64, 60, 96, 80, 64, 96, 108, 72, 72, 96, 128, 80, 96, 84, 120, 144, 88, 92, 160, 126, 120, 128, 144, 104, 144, 160, 192, 144, 112, 116, 192, 120, 120, 216, 224

Offset

1,2

Comments

a(n) = sum of gcd(k-1,n) for 1 <= k <= n and gcd(k,n)=1 (Menon's identity).

For n = 2^(4*k^2 - 1), k >= 1, the terms of the sequence are square and for n = 2^((3*k + 2)^3 - 1), k >= 1, the terms of the sequence are cubes. - Marius A. Burtea, Nov 14 2019

Sum_{k>=1} 1/a(k) diverges. - Vaclav Kotesovec, Sep 20 2020

References

D. M. Burton, Elementary Number Theory, Allyn and Bacon Inc., Boston MA, 1976, Prob. 7.2 12, p. 141.

P. K. Menon, On the sum gcd(a-1,n) [(a,n)=1], J. Indian Math. Soc. (N.S.), 29 (1965), 155-163.

József Sándor, On Dedekind's arithmetical function, Seminarul de teoria structurilor (in Romanian), No. 51, Univ. Timișoara, 1988, pp. 1-15. See p. 11.

József Sándor, Some diophantine equations for particular arithmetic functions (in Romanian), Seminarul de teoria structurilor, No. 53, Univ. Timișoara, 1989, pp. 1-10. See p. 8.

Links

Antti Karttunen, Table of n, a(n) for n = 1..65537 (terms 1..1000 from Harry J. Smith)

Pentti Haukkanen and László Tóth, Menon-type identities again: Note on a paper by Li, Kim and Qiao, arXiv:1911.05411 [math.NT], 2019.

Vaclav Kotesovec, Graph - the asymptotic ratio (250000000 terms)

R. J. Mathar, Survey of Dirichlet series of multiplicative arithmetic functions, arXiv:1106.4038 [math.NT], 2011-2012, Section 3.15.

R. Sivaramakrishnan, Problem E 1962, Elementary Problems, The American Mathematical Monthly, Vol. 74, No. 2 (1967), p. 198; Solution, ibid., Vol. 75, No. 5 (1968), p. 550.

Marius Tarnauceanu, A generalization of the Menon's identity, arXiv:1109.2198 [math.GR], 2011-2012.

Laszlo Toth, Menon's identity and arithmetical sums representing functions of several variables, Rend. Sem. Mat. Univ. Politec. Torino, 69 (2011), 97-110.

Wikipedia, Arithmetic function (Menon's identity).

Formula

Dirichlet convolution of A047994 and A000010. - R. J. Mathar, Apr 15 2011

a(n) = A000005(n)*A000010(n). Multiplicative with a(p^e) = (e+1)*(p-1)*p^(e-1). - R. J. Mathar, Jun 23 2018

a(n) = A173557(n) * A318519(n) = A003557(n) * A304408(n). - Antti Karttunen, Sep 16 2018 & Sep 20 2019

From Vaclav Kotesovec, Jun 15 2020: (Start)

Let f(s) = Product_{primes p} (1 - 2*p^(-s) + p^(1-2*s)).

Dirichlet g.f.: zeta(s-1)^2 * f(s).

Sum_{k=1..n} a(k) ~ n^2 * (f(2)*(log(n)/2 + gamma - 1/4) + f'(2)/2), where f(2) = A065464 = Product_{primes p} (1 - 2/p^2 + 1/p^3) = 0.42824950567709444...,

f'(2) = 2 * A065464 * A335707 = f(2) * Sum_{primes p} 2*log(p) / (p^2 + p - 1) = 0.35866545223424232469545420783620795... and gamma is the Euler-Mascheroni constant A001620. (End)

From Amiram Eldar, Mar 02 2021: (Start)

a(n) >= n (Sivaramakrishnan, 1967).

a(n) >= sigma(n), for odd n (Sándor, 1988).

a(n) >= phi(n) + n - 1 (Sándor, 1989) (End)

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

a(n) = Sum_{k=1..n} uphi(gcd(n,k)), where uphi(n) = A047994(n).

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

Maple

seq(tau(n)*phi(n), n=1..64); # Zerinvary Lajos, Jan 22 2007

Mathematica

Table[EulerPhi[n] DivisorSigma[0, n], {n, 80}] (* Carl Najafi, Aug 16 2011 *)
f[p_, e_] := (e+1)*(p-1)*p^(e-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 21 2020 *)

Prog

(PARI) a(n)=numdiv(n)*eulerphi(n); vector(150, n, a(n))
(PARI) { for (n=1, 1000, write("b062355.txt", n, " ", numdiv(n)*eulerphi(n)) ) } \\ Harry J. Smith, Aug 05 2009
(PARI) for(n=1, 100, print1(direuler(p=2, n, (1 - 2*X + p*X^2)/(1 - p*X)^2)[n], ", ")) \\ Vaclav Kotesovec, Jun 15 2020
(Magma) [NumberOfDivisors(n)*EulerPhi(n):n in [1..65]]; // Marius A. Burtea, Nov 14 2019

Crossrefs

Cf. A003557, A173557, A061468, A062816, A079535, A062949 (inverse Mobius transform), A304408, A318519, A327169 (number of times n occurs in this sequence).

Cf. A062354, A064840.

Sequence in context: A063199 A219028 A333557 * A366602 A087671 A088308

Adjacent sequences: A062352 A062353 A062354 * A062356 A062357 A062358

Keyword

easy,nonn,mult

Author

Jason Earls, Jul 06 2001

Status

approved