|
%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&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_
|
