cp's OEIS Frontend

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

%I A055891 #30 Dec 31 2018 14:15:15
%S A055891 1,2,7,20,64,200,686,2324,8194,29084,104860,381116,1398148,5161592,
%T A055891 19173958,71580752,268435474,1010572832,3817749138,14467230668,
%U A055891 54975581488,209430687944,799644820114,3059510251700,11728124035248
%N A055891 CIK (necklace, indistinct, unlabeled) transform of powers of 2.
%C A055891 From _Petros Hadjicostas_, Dec 06 2017: (Start)
%C A055891 The g.f. is clear from J. Arndt's PARI program below.
%C A055891 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).
%C A055891 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).
%C A055891 (End)
%H A055891 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H A055891 P. Flajolet and M. Soria, <a href="http://algo.inria.fr/flajolet/Publications/cycle2.ps.gz">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H A055891 P. Flajolet and M. Soria, <a href="/A055891/a055891.pdf">The Cycle Construction.</a> [pdf file]
%F A055891 From _Petros Hadjicostas_, Dec 06 2017: (Start)
%F A055891 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.
%F A055891 G.f.: 1 - Sum_{n>=1} (phi(n)/n)*log((1-4*x^n)/(1-2*x^n)).
%F A055891 (End)
%t A055891 {1}~Join~Table[(1/n) DivisorSum[n, EulerPhi[n/#] *2^#*(2^# - 1) &], {n, 24}] (* _Michael De Vlieger_, Dec 06 2017 *)
%o A055891 (PARI)
%o A055891 N = 66;  x = 'x + O('x^N);
%o A055891 f(x)=sum(n=1,N, 2^n*x^n );
%o A055891 gf = 1 + sum(n=1,N, eulerphi(n)/n*log(1/(1-f(x^n)))  );
%o A055891 v = Vec(gf)
%o A055891 /* _Joerg Arndt_, Jan 21 2013 */
%Y A055891 Cf. A000079, A020522, A055376.
%K A055891 nonn
%O A055891 0,2
%A A055891 _Christian G. Bower_, Jun 09 2000