login
Dirichlet convolution of b_n = 2^(n-1) with phi(n).
19

%I #48 Nov 23 2021 20:56:40

%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.

%H Silvana Ramaj, <a href="https://digitalcommons.georgiasouthern.edu/cgi/viewcontent.cgi?article=3464&amp;context=etd">New Results on Cyclic Compositions and Multicompositions</a>, Master's Thesis, Georgia Southern Univ., 2021. See pp. 47-48, 50.

%F a(n) = A053635(n)/2.

%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

%F a(n) = Sum_{k=1..n} 2^(gcd(k, n) - 1). - _Seiichi Manyama_, Apr 17 2021

%F a(n) = Sum_{k=1..n} 2^(n/gcd(n,k) - 1)*phi(gcd(n,k))/phi(n/gcd(n,k)). - _Richard L. Ollerton_, May 06 2021

%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 *)

%o (PARI) a(n) = sum(k=1, n, 2^(gcd(k, n)-1)); \\ _Seiichi Manyama_, Apr 17 2021

%o (PARI) a(n) = sumdiv(n, d, eulerphi(n/d)*2^(d-1)); \\ _Seiichi Manyama_, Apr 17 2021

%o (PARI) my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k/(1-2*x^k))) \\ _Seiichi Manyama_, Apr 17 2021

%Y Cf. A000010, A000740, A034754, A053635, A078392.

%K nonn

%O 1,2

%A _Erich Friedman_