A062355 - OEIS

%I #108 Sep 08 2022 08:45:03

%S 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,

%T 48,72,72,56,64,60,96,80,64,96,108,72,72,96,128,80,96,84,120,144,88,

%U 92,160,126,120,128,144,104,144,160,192,144,112,116,192,120,120,216,224

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

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

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

%C Sum_{k>=1} 1/a(k) diverges. - _Vaclav Kotesovec_, Sep 20 2020

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

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

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

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

%H Antti Karttunen, <a href="/A062355/b062355.txt">Table of n, a(n) for n = 1..65537</a> (terms 1..1000 from Harry J. Smith)

%H Pentti Haukkanen and László Tóth, <a href="https://arxiv.org/abs/1911.05411">Menon-type identities again: Note on a paper by Li, Kim and Qiao</a>, arXiv:1911.05411 [math.NT], 2019.

%H Vaclav Kotesovec, <a href="/A062355/a062355.jpg">Graph - the asymptotic ratio</a> (250000000 terms)

%H R. J. Mathar, <a href="http://arxiv.org/abs/1106.4038">Survey of Dirichlet series of multiplicative arithmetic functions</a>, arXiv:1106.4038 [math.NT], 2011-2012, Section 3.15.

%H R. Sivaramakrishnan, <a href="http://www.jstor.org/stable/2315622">Problem E 1962</a>, Elementary Problems, The American Mathematical Monthly, Vol. 74, No. 2 (1967), p. 198; <a href="http://www.jstor.org/stable/2314747">Solution</a>, ibid., Vol. 75, No. 5 (1968), p. 550.

%H Marius Tarnauceanu, <a href="http://arxiv.org/abs/1109.2198">A generalization of the Menon's identity</a>, arXiv:1109.2198 [math.GR], 2011-2012.

%H Laszlo Toth, <a href="http://www.seminariomatematico.polito.it/rendiconti/69-1/97.pdf">Menon's identity and arithmetical sums representing functions of several variables</a>, Rend. Sem. Mat. Univ. Politec. Torino, 69 (2011), 97-110.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Arithmetic_function#Menon&#39;s_identity">Arithmetic function (Menon's identity)</a>.

%F Dirichlet convolution of A047994 and A000010. - _R. J. Mathar_, Apr 15 2011

%F a(n) = A000005(n)*A000010(n). Multiplicative with a(p^e) = (e+1)*(p-1)*p^(e-1). - _R. J. Mathar_, Jun 23 2018

%F a(n) = A173557(n) * A318519(n) = A003557(n) * A304408(n). - _Antti Karttunen_, Sep 16 2018 & Sep 20 2019

%F From _Vaclav Kotesovec_, Jun 15 2020: (Start)

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

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

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

%F From _Amiram Eldar_, Mar 02 2021: (Start)

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

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

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

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

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

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

%p seq(tau(n)*phi(n), n=1..64); # _Zerinvary Lajos_, Jan 22 2007

%t Table[EulerPhi[n] DivisorSigma[0, n], {n, 80}] (* _Carl Najafi_, Aug 16 2011 *)

%t 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 *)

%o (PARI) a(n)=numdiv(n)*eulerphi(n); vector(150,n,a(n))

%o (PARI) { for (n=1, 1000, write("b062355.txt", n, " ", numdiv(n)*eulerphi(n)) ) } \\ _Harry J. Smith_, Aug 05 2009

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

%o (Magma) [NumberOfDivisors(n)*EulerPhi(n):n in [1..65]]; // _Marius A. Burtea_, Nov 14 2019

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

%Y Cf. A062354, A064840.

%K easy,nonn,mult

%O 1,2

%A _Jason Earls_, Jul 06 2001