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

1, 4, 9, 20, 35, 78, 133, 280, 531, 1070, 2057, 4212, 8203, 16534, 32865, 65840, 131087, 262818, 524305, 1049740, 2097459, 4196390, 8388629, 16782024, 33554575, 67117102, 134218809, 268452212, 536870939, 1073777010, 2147483677, 4295033440, 8589938775, 17180000318, 34359739085

Offset: 1

Author

Ilya Gutkovskiy, Sep 17 2021

Keywords

• nonn

Crossrefs

Cf. A000010, A000031, A000225, A008965, A034738, A038199, A053635.

Programs

Mathematica

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

PARI

a(n) = sumdiv(n, d, eulerphi(n/d)*(2^d - 1)); \\ Michel Marcus, Sep 17 2021

Formula

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

a(n) = Sum_{k=1..n} (2^gcd(n,k) - 1).

a(n) = n * (A000031(n) - 1) = n * A008965(n).

Dirichlet convolution of A000225 and A000010. - R. J. Mathar, Sep 30 2021