A055891 CIK (necklace, indistinct, unlabeled) transform of powers of 2.

1, 2, 7, 20, 64, 200, 686, 2324, 8194, 29084, 104860, 381116, 1398148, 5161592, 19173958, 71580752, 268435474, 1010572832, 3817749138, 14467230668, 54975581488, 209430687944, 799644820114, 3059510251700, 11728124035248

Offset: 0

Author

Christian G. Bower, Jun 09 2000

Keywords

• nonn

Comments

From Petros Hadjicostas, Dec 06 2017: (Start)

The g.f. is clear from J. Arndt's PARI program below.

The CIK transform of sequence (a(n): n>=1} with g.f. A(x) = Sum_{n>=1} a(n)*x^n has g.f. CIK(A(x)) = 1 - Sum_{n>=1} (phi(n)/n)*log(1-A(x^n)). Sometimes, the constant 1 is dropped from the formula. Here, A(x) = 2*x/(1-2*x).

To find the auxiliary sequence (c(n): n>=1} used in the formula a(n) = (1/n)*Sum_{d|n} phi(n/d)*c(d), we use the formula C(x) = Sum_{n>=1} c(n)*x^n = x*(dA(x)/dx)/(1-A(x)). Here, C(x) = 2*x/((1-4*x)*(1-2*x)), from which we can prove that c(n) = 2^n*(2^n-1) = A020522(n).

(End)

Links

• C. G. Bower, Transforms (2)
• P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
• P. Flajolet and M. Soria, The Cycle Construction. [pdf file]

Crossrefs

Cf. A000079, A020522, A055376.

Programs

Mathematica

{1}~Join~Table[(1/n) DivisorSum[n, EulerPhi[n/#] *2^#*(2^# - 1) &], {n, 24}] (* Michael De Vlieger, Dec 06 2017 *)

PARI

N = 66;  x = 'x + O('x^N);
f(x)=sum(n=1,N, 2^n*x^n );
gf = 1 + sum(n=1,N, eulerphi(n)/n*log(1/(1-f(x^n)))  );
v = Vec(gf)
/* Joerg Arndt, Jan 21 2013 */

Formula

From Petros Hadjicostas, Dec 06 2017: (Start)

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

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

(End)