The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A034738 Dirichlet convolution of b_n = 2^(n-1) with phi(n). 10

%I

%S 1,3,6,12,20,42,70,144,270,540,1034,2112,4108,8274,16440,32928,65552,

%T 131418,262162,524880,1048740,2098206,4194326,8391024,16777300,

%U 33558564,67109418,134226120,268435484,536888520,1073741854,2147516736

%N Dirichlet convolution of b_n = 2^(n-1) with phi(n).

%C Sum of GCD's of parts in all compositions of n. - _Vladeta Jovovic_, Aug 13 2003

%C From _Petros Hadjicostas_, Dec 07 2017: (Start)

%C It also equals the sum of all lengths of all cyclic compositions of n. This was proved in Perez (2008).

%C The bivariate g.f. for the number b(n,k) of all cyclic of compositions of n with k parts is Sum_{n,k>=1} b(n,k)*x^n*y^k = -Sum_{s>=1} (phi(s)/s)*log(1 - y^s*Sum_{t>=1} x^{s*t}) = -Sum_{s>=1} (phi(s)/s)*log(1 - y^s*x^s/(1-x^s)). See, for example, Hadjicostas (2016). Differentiating w.r.t. y and setting y = 1, we get Sum_{n>=1} a(n)*x^n = Sum_{n>=1} (Sum_{k=1..n} b(n,k)*k)*x^n = Sum_{s>=1} phi(s)*x^s/(1-2*x^s).

%C (End)

%H Amiram Eldar, <a href="/A034738/b034738.txt">Table of n, a(n) for n = 1..3322</a>

%H P. Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence</a>, J. Integer Sequences 19 (2016), Article 16.8.2.

%H R. A. Perez, <a href="http://www.pphmj.com/abstract/3608.htm">Compositions versus cyclic compositions</a>, JP Journal of Algebra, Number Theory and Applications, Vol. 12, Issue 1 (2008), pp. 41-48.

%F a(n) = (1/2)* Sum_{d|n} phi(d)*2^(n/d), n >= 1.

%F G.f.: Sum_{s>=1} phi(s)*x^s/(1-2*x^s). - _Petros Hadjicostas_, Dec 07 2017

%F a(n) ~ 2^(n-1). - _Vaclav Kotesovec_, Feb 07 2019

%e For the compositions of n=4 we have a(4) = gcd(4) + gcd(1,3) + gcd(3,1) + gcd(2,2) + gcd(2,1,1) + gcd(1,2,1) + gcd(1,1,2) + gcd(1,1,1,1) = 4 + 1 + 1 + 2 + 1 + 1 + 1 + 1 = 12. Also, for cyclic compositions of n=4, we have length(4) + length(1,3) + length(2,2) + length(1,1,2) + length(1,1,1,1) = 1 + 2 + 2 + 3 + 4 = 12.

%t Table[Sum[EulerPhi[d]*2^(n/d-1), {d, Divisors[n]}], {n, 1, 40}] (* _Vaclav Kotesovec_, Feb 07 2019 *)

%Y Equals A053635 / 2.

%Y Cf. A000740, A078392.

%K nonn

%O 1,2

%A _Erich Friedman_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 7 17:44 EDT 2020. Contains 336278 sequences. (Running on oeis4.)