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,2

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

Table of n, a(n) for n=0..24.

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]

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)

Mathematica

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

Prog

(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 */

Crossrefs

Cf. A000079, A020522, A055376.

Sequence in context: A322202 A000935 A035071 * A122877 A192680 A000150

Adjacent sequences: A055888 A055889 A055890 * A055892 A055893 A055894

Keyword

nonn

Author

Christian G. Bower, Jun 09 2000

Status

approved