A309369 a(n) = Sum_{d|n} phi(n/d)^d, where phi = Euler totient function (A000010).

1, 2, 3, 4, 5, 8, 7, 10, 15, 22, 11, 34, 13, 44, 105, 42, 17, 116, 19, 314, 357, 112, 23, 426, 1045, 158, 747, 1474, 29, 5290, 31, 594, 3069, 274, 24185, 6082, 37, 344, 9945, 67922, 41, 63542, 43, 12170, 303225, 508, 47, 74834, 279979, 1050022, 135201, 29098, 53, 309872, 4294345

Offset: 1

Author

Ilya Gutkovskiy, Jul 25 2019

Keywords

• nonn

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..5000

Crossrefs

Cf. A000010, A055225, A164941, A264782, A279789.

Programs

Mathematica

Table[Sum[EulerPhi[n/d]^d, {d, Divisors[n]}], {n, 1, 55}]
nmax = 55; CoefficientList[Series[Sum[EulerPhi[k] x^k/(1 - EulerPhi[k] x^k), {k, 1, nmax}], {x, 0, nmax}], x] // Rest
nmax = 55; CoefficientList[Series[-Log[Product[(1 - EulerPhi[k] x^k)^(1/k), {k, 1, nmax}]], {x, 0, nmax}], x] Range[0, nmax] // Rest

PARI

a(n) = sum(k=1, n, eulerphi(n/gcd(k, n))^(gcd(k, n)-1)); \\ Seiichi Manyama, Mar 13 2021

Formula

G.f.: Sum_{k>=1} phi(k)*x^k/(1 - phi(k)*x^k).

L.g.f.: -log(Product_{k>=1} (1 - phi(k)*x^k)^(1/k)).

a(p) = p for p prime.

a(n) = Sum_{k=1..n} phi(n/gcd(k, n))^(gcd(k, n) - 1). - Seiichi Manyama, Mar 13 2021