A226459 a(n) = Sum_{d|n} phi(d^d), where phi(n) is the Euler totient function A000010(n).

1, 3, 19, 131, 2501, 15573, 705895, 8388739, 258280345, 4000002503, 259374246011, 2972033498453, 279577021469773, 4762288640230761, 233543408203127519, 9223372036863164547, 778579070010669895697, 13115469358432437487707, 1874292305362402347591139

Offset

1,2

Comments

Compare formula to the identity: Sum_{d|n} phi(d) = n.

Links

G. C. Greubel, Table of n, a(n) for n = 1..385

Formula

a(n) = Sum_{d|n} d^(d-1) * phi(d).

Equals the logarithmic derivative of A226458.

G.f.: Sum_{k>=1} phi(k^k)*x^k/(1 - x^k). - Ilya Gutkovskiy, Nov 06 2018

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

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

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

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

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

Example

L.g.f.: L(x) = x + 3*x^2/2 + 19*x^3/3 + 131*x^4/4 + 2501*x^5/5 + ...
where
exp(L(x)) = 1 + x + 2*x^2 + 8*x^3 + 41*x^4 + 547*x^5 + 3193*x^6 + ... + A226458(n)*x^n + ...

Mathematica

ttf[n_]:=Module[{d=Divisors[n]}, Total[EulerPhi[d^d]]]; Array[ttf, 20] (* Harvey P. Dale, Aug 21 2013 *)
With[{nmax = 30}, Rest[CoefficientList[Series[Sum[EulerPhi[k^k]*x^k/(1 - x^k), {k, 1, 2*nmax}], {x, 0, nmax}], x]]] (* G. C. Greubel, Nov 07 2018 *)

Prog

(PARI) {a(n)=sumdiv(n, d, eulerphi(d^d))}
for(n=1, 30, print1(a(n), ", "))
(PARI) a(n) = sum(k=1, n, (n/gcd(k, n))^(n/gcd(k, n)-1)); \\ Seiichi Manyama, Mar 11 2021
(Magma) m:=30; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!(  (&+[EulerPhi(k^k)*x^k/(1-x^k): k in [1..3*m]]) )); // G. C. Greubel, Nov 07 2018
(Python)
from sympy import totient, divisors
def A226459(n):
    return sum(totient(d)*d**(d-1) for d in divisors(n, generator=True)) # Chai Wah Wu, Feb 15 2020

Crossrefs

Cf. A226458, A226561, A000010.

Sequence in context: A074713 A199484 A063395 * A256092 A370159 A369627

Adjacent sequences: A226456 A226457 A226458 * A226460 A226461 A226462

Keyword

nonn

Author

Paul D. Hanna, Jun 08 2013

Status

approved