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

0, 2, 6, 12, 24, 40, 84, 140, 288, 540, 1080, 2068, 4224, 8216, 16548, 32880, 65856, 131104, 262836, 524324, 1049760, 2097480, 4196412, 8388652, 16782048, 33554600, 67117128, 134218836, 268452240, 536870968, 1073777040, 2147483708, 4295033472, 8589938808

Offset: 0

Author

N. J. A. Sloane, Mar 23 2000

Keywords

• nonn

Comments

Dirichlet convolution of phi(n) and 2^n. - Richard L. Ollerton, May 06 2021

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..3321
• James East and Ron Niles, Integer polygons of given perimeter, arXiv:1710.11245 [math.CO], 2017.
• James East and Ron Niles, Integer polygons of given perimeter, Bull. Aust. Math. Soc. 100(1) (2019), 131-147.
• T. Pisanski, D. Schattschneider, and B. Servatius, Applying Burnside's lemma to a one-dimensional Escher problem, Math. Mag., 79 (2006), 167-180. See v(n).

Crossrefs

Cf. A000031, A053634, A053636. Twice A034738.

Column k=2 of A185651.

Programs

Magma

[0] cat  [&+[EulerPhi(d)*2^(n div d): d in Divisors(n)]: n in [1..40]]; // Vincenzo Librandi, Jul 20 2019

Maple

with(numtheory); A053685:=n->add( phi(n/d)*2^d, d in divisors(n)); # N. J. A. Sloane, Nov 21 2009

Mathematica

a[0] = 0; a[n_] := Sum[EulerPhi[d] 2^(n/d), {d, Divisors[n]}];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Aug 30 2018 *)

PARI

a(n) = if (n, sumdiv(n, d, eulerphi(d)*2^(n/d)), 0); \\ Michel Marcus, Sep 20 2017

Formula

a(n) = n * A000031(n).

a(n) = Sum_{k=1..n} 2^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021

a(n) = Sum_{k=1..n} 2^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 06 2021