A078932 -id:A078932 - cp's OEIS frontend

A087221 Number of compositions (ordered partitions) of n into powers of 4.

1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 96, 133, 184, 254, 352, 488, 676, 935, 1294, 1792, 2482, 3436, 4756, 6584, 9116, 12621, 17473, 24190, 33490, 46365, 64190, 88868, 123034, 170334, 235818, 326478, 451994, 625764, 866338, 1199400, 1660510

Offset: 0

Paul D. Hanna, Aug 27 2003

nonn

Series trisections have a common ratio:
sum(k>=0, a(3k+1)*x^k) / sum(k>=0, a(3k)*x^k)
= sum(k>=0, a(3k+2)*x^k) / sum(k>=0, a(3k+1)*x^k)
= sum(k>=0, a(3k+3)*x^k) / sum(k>=0, a(3k+2)*x^k)
= sum(k>=0, x^((4^n-1)/3) ) = (1 + x + x^5 + x^21 + x^85 + x^341 +...).

			A(x) = A(x^4) + x*A(x^4)^2 + x^2*A(x^4)^3 + x^3*A(x^4)^4 + ...
= 1 +x + x^2 +x^3 +2x^4 +3x^5 +5x^6 +7x^7 + 10x^8 +...

T. D. Noe, Table of n, a(n) for n=0..500

Cf. A078932, A087222, A087232, A087224. Different from A003269.

a:= proc(n) option remember;
      `if`(n=0, 1, add(a(n-4^i), i=0..ilog[4](n)))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 11 2014

a[n_] := a[n] = If[n==0, 1, Sum[a[n-4^i], {i, 0, Log[4, n]}]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 24 2015, after Alois P. Heinz *)

a(n)=local(A,m); if(n<1,n==0,m=1; A=1+O(x); while(m<=n,m*=4; A=1/(1/subst(A,x,x^4)-x)); polcoeff(A,n))

N=66; x='x+O('x^N);
Vec( 1/( 1 - sum(k=0, ceil(log(N)/log(4)), x^(4^k)) ) )
/* Joerg Arndt, Oct 21 2012 */

G.f.: 1/( 1 - sum(k>=0, x^(4^k) ) ). [Joerg Arndt, Oct 21 2012]
G.f. satisfies A(x) = A(x^4)/(1 - x*A(x^4)), A(0) = 1.
a(n) ~ c * d^n, where d=1.384450093664460722709070772652942206959424183007359023442195..., c=0.526605891697738213614083414993893445498621299371909641096106... - Vaclav Kotesovec, May 01 2014

A235684 Number of compositions of n into powers of 3 and doubled powers of 3.

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 25, 46, 86, 162, 302, 565, 1058, 1978, 3700, 6923, 12949, 24223, 45316, 84769, 158575, 296645, 554923, 1038079, 1941911, 3632677, 6795551, 12712263, 23780486, 44485521, 83217888, 155673480, 291214232, 544766722, 1019080592, 1906366927

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Jan 13 2014

nonn

a(n+1)/a(n) tends to 1.87067337504749000600807516613083316430149226... (used Richardson's extrapolation) - Vaclav Kotesovec, Jan 14 2014

			a(3) = 4: 1+1+1, 2+1, 1+2, 3, thus we have 4 compositions with the allowed parts.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A078932, A235669, A235773.

a:= proc(n) option remember; `if`(n=0, 1, `if`(n<0, 0,
      add(a(n-3^i)+a(n-2*3^i), i=0..ilog[3](n))))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 13 2014

a[n_] := a[n] = If[n == 0, 1, If[n < 0, 0, Sum[a[n - 3^i] + a[n - 2*3^i], {i, 0, Log[3, n]}]]];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)

A374565 Expansion of g.f. A(x) satisfying A(x)^3 = A( x*A(x)^2/(1-x) ).

Original entry on oeis.org

1, 1, 1, 2, 5, 11, 24, 57, 141, 350, 881, 2267, 5920, 15601, 41497, 111399, 301293, 819843, 2243058, 6167211, 17029473, 47200752, 131270283, 366195789, 1024380648, 2872770381, 8074967031, 22745832254, 64196912681, 181516532273, 514107418321, 1458407886019, 4143318012685

Offset: 1

Paul D. Hanna, Jul 23 2024

nonn

			G.f.: A(x) = x + x^2 + x^3 + 2*x^4 + 5*x^5 + 11*x^6 + 24*x^7 + 57*x^8 + 141*x^9 + 350*x^10 + 881*x^11 + 2267*x^12 + 5920*x^13 + 15601*x^14 + 41497*x^15 + ...
where A(x)^3 = A( x*A(x)^2/(1-x) )
and A(x) = x + x*(A(x) + A(x)^3 + A(x)^9 + A(x)^27 + ... A(x)^(3^n) + ...).
RELATED SERIES.
A(x)^3 = x^3 + 3*x^4 + 6*x^5 + 13*x^6 + 33*x^7 + 84*x^8 + 208*x^9 + 522*x^10 + 1341*x^11 + 3479*x^12 + 9078*x^13 + 23907*x^14 + 63560*x^15 + ...
Let B(x) be the series reversion of A(x), B(A(x)) = x, then
B(x) = x - x^2 + x^3 - 2*x^4 + 3*x^5 - 4*x^6 + 6*x^7 - 9*x^8 + 13*x^9 - 20*x^10 + ... + (-1)^(n-1)*A078932(n-1)*x^n + ...
where x/B(x) = 1 + x + x^3 + x^9 + x^27 + x^81 + ... + x^(3^n) + ...
F(x) = A(x/(1+x)) = x + x^4 + 3*x^7 + 13*x^10 + 67*x^13 + 378*x^16 + 2253*x^19 + 13947*x^22 + 88803*x^25 + 577903*x^28 + 3826870*x^31 + 25703868*x^34 + ...
where F(x)^3 = F( x*F(x)^2/(1 - x*F(x)^2) )
and F(x) = x + x*(F(x)^3 + F(x)^9 + F(x)^27 + ... + F(x)^(3^n) + ...).
SPECIFIC VALUES.
A(t) = 2/3 at t = 0.3351780091733165997365854281871805851976265481916...
where 8/27 = A( (4/9)*t/(1-t) )
and t = (2/3)/(1 + Sum_{n>=0} (2/3)^(3^n)).
A(t) = 1/2 at t = 0.3073229277642929985518391822746766756418592443672...
where 1/8 = A( (1/4)*t/(1-t) )
and t = (1/2)/(1 + Sum_{n>=0} (1/2)^(3^n)).
A(1/3) = 0.640317989282342396539425948311398871030928082061168...
where A(1/3)^3 = A( A(1/3)^2/2 ).
A(1/4) = 0.347324237093006237340030053166266719890703533474663...
where A(1/4)^3 = A( A(1/4)^2/3 ).
A(1/5) = 0.254102848699628177600720471035831153854183353627930...
where A(1/5)^3 = A( A(1/5)^2/4 ).
A(1/10) = 0.111264157881789221767410282888976753122883279205707...
where A(1/10)^3 = A( A(1/10)^2/9 ).

Paul D. Hanna, Table of n, a(n) for n = 1..801

Cf. A078932, A075864.

{a(n) = my(A = serreverse(x/(1 + sum(n=0,ceil(log(n+1)/log(3)), x^(3^n)) + x^3*O(x^n)) )); polcoeff(A,n)}
for(n=1, 40, print1(a(n), ", "))

{a(n) = my(A=[1], Ax);
for(i=1, n, A=concat(A, 0); Ax=x*Ser(A);
A[#A] = -polcoeff( Ax^3 - subst(Ax, x, Ax^2*x/(1-x) ), #A+2) ); A[n]}
for(n=1, 40, print1(a(n), ", "))

G.f. A(x) = Sum_{n>=1} a(n)*x^n satisfies the following formulas.
(1) A(x) = x + x*Sum_{n>=0} A(x)^(3^n).
(2) A(x) = Series_Reversion( x/(1 + Sum_{n>=0} x^(3^n)) ).
(3) A(x)^3 = A( x*A(x)^2/(1-x) ).
(4) A(x)^9 = A( x*A(x)^8/(1 - x - x*A(x)^2) ).
(5) A(x)^27 = A( x*A(x)^26/(1 - x - x*A(x)^2 - x*A(x)^8) ).
(6) A(x)^(3^n) = A( x*A(x)^(3^n-1) / (1 - x*Sum_{k=0..n-1} A(x)^(3^k-1)) ) for n >= 1.
The radius of convergence r and A(r) satisfy r = 1/(Sum_{n>=0} 3^n*A(r)^(3^n-1)) and A(r) = A( A(r)^2*r/(1-r) )^(1/3), where r = 0.3359879296886914478616860912190963818298151003686099... and A(r) = 0.6985186992950193189255500784091315877737446624401085...

A087218 Satisfies A(x) = 1 + xA(x)f(x)^2, where f(x) = Sum_{k>=0} x^((3^n-1)/2) and f(x)^2 = 2 - f(x^2) + 2*Sum_{n>0} x^A023745(n).

Original entry on oeis.org

1, 1, 3, 6, 13, 30, 66, 147, 327, 726, 1614, 3588, 7974, 17725, 39399, 87573, 194655, 432669, 961716, 2137659, 4751490, 10561392, 23475378, 52179987, 115983270, 257802273, 573031011, 1273706934, 2831137095, 6292921101, 13987615113

Offset: 0

Paul D. Hanna, Aug 26 2003

nonn

			Given f(x) = 1 + x + x^4 + x^13 + x^40 + x^121 + ... so that f(x)^2 = 1 + 2x + x^2 + 2x^4 + 2x^5 + x^8 + 2*x^13 + ... then A(x) = 1 + x*A(x)*(1 + 2x + x^2 + 2x^4 + 2x^5 + x^8 + ...) = 1 + x + 3x^2 + 6x^3 + 13x^4 + 30x^5 + ...

Cf. A078932, A023745, A087219.

a(n)=local(A,m); if(n<1,1,m=1; A=1+O(x); while(m<=2*n,m*=3; A=1/(1/subst(A,x,x^3)-x)); polcoeff(A,2*n));

a(n) = A078932(2n). a(m) = 1 (mod 3) when m = (3^n - 1)/2, otherwise a(m) = 0 (mod 3).

A087219 Satisfies A(x) = f(x) + xA(x)f(x)^2, where f(x) = Sum_{k>=0} x^((3^n-1)/2) and f(x)^2 = 2 - f(x^2) + 2Sum_{n>0} x^A023745(n). Also, A(x) = f(x)B(x), where B(x) = Sum_{k>=0} A087218(k)*x^k.

Original entry on oeis.org

1, 2, 4, 9, 20, 44, 99, 219, 487, 1083, 2406, 5349, 11889, 26426, 58739, 130563, 290208, 645062, 1433814, 3187014, 7083951, 15745878, 34999212, 77794638, 172918335, 384354909, 854326387, 1898957331, 4220914872, 9382055124

Offset: 0

Paul D. Hanna, Aug 27 2003

nonn

			Given f(x) = 1 + x + x^4 + x^13 + x^40 + x^121 + ... so that f(x)^2 = 1 + 2x + x^2 + 2x^4 + 2x^5 + x^8 + 2*x^13 + ... then A(x) = (1 + x + x^4 + ...) + x*A(x)*(1 + 2x + x^2 + 2x^4 + 2x^5 + ...) = 1 + 2x + 4x^2 + 9x^3 + 20x^4 + 44x^5 + ...

Cf. A078932, A087218.

a(n)=local(A,m); if(n<1,1,m=1; A=1+O(x); while(m<=2*n+1,m*=3; A=1/(1/subst(A,x,x^3)-x)); polcoeff(A,2*n+1));

a(n) = A078932(2n+1). a(m) = 1 (mod 3) when m = (3^n-1)/2 (mod 3), else a(m) = 2 (mod 3) when m = A023745(n), otherwise a(m) = 0 (mod 3).

A235773 Number of compositions of n into distinct powers of 3 and doubled powers of 3.

Original entry on oeis.org

1, 1, 1, 3, 2, 2, 7, 2, 2, 9, 8, 8, 32, 6, 6, 26, 6, 6, 31, 26, 26, 128, 6, 6, 26, 6, 6, 33, 32, 32, 158, 30, 30, 152, 30, 30, 176, 150, 150, 870, 24, 24, 126, 24, 24, 146, 126, 126, 750, 24, 24, 126, 24, 24, 151, 146, 146, 872, 126, 126, 770, 126, 126, 872

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Jan 15 2014

			Let n=5. We have only two allowed compositions 2+3 = 3+2. So a(5) = 2.
For n=6, we have compositions 6 = 1+2+3 = 1+3+2 = 2+3+1 = 2+1+3 = 3+2+1 = 3+1+2. Thus a(6) = 7.

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A235684, A078932, A235669.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<0, 0,
      expand(b(n, i-1)+`if`(3*3^i>n, 0, b(n-3*3^i, i-1)*x^2)
      +add(`if`(j*3^i>n, 0, b(n-j*3^i, i-1))*x, j=1..2))))
    end:
a:= n->(p->add(coeff(p, x, j)*j!, j=0..degree(p)))(b(n, ilog[3](n))):
seq(a(n), n=0..100);  # Alois P. Heinz, Jan 15 2014

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<0, 0, Expand[b[n, i-1] + If[3^(i+1) > n, 0, b[n-3^(i+1), i-1]x^2] + Sum[If[3^i j > n, 0, b[n-3^i j, i-1]]x, {j, 1, 2}]]]];
a[n_] := With[{p = b[n, Log[3, n] // Floor]}, Sum[Coefficient[p, x, j] j!, {j, 0, Exponent[p, x]}]];
a /@ Range[0, 100] (* Jean-François Alcover, Nov 12 2020, after Alois P. Heinz *)

A382190 Expansion of 1/(1 - 9 * Sum_{k>=0} x^(3^k))^(1/3).

Original entry on oeis.org

1, 3, 18, 129, 981, 7749, 62766, 517401, 4320864, 36446565, 309876444, 2651681826, 22812645339, 197144727876, 1710267824304, 14886242261595, 129946357148661, 1137235357935279, 9975129925544568, 87672540348112779, 771962724133452441, 6808329943495097076

Offset: 0

Seiichi Manyama, Mar 18 2025

Cf. A078932, A382189.

Cf. A382196.

G.f. A(x) satisfies A(x) = 1/(1/A(x^3)^3 - 9*x)^(1/3).

A281228 Expansion of (Sum_{k>=0} x^(3^k))^2 [even terms only].

Original entry on oeis.org

0, 1, 2, 1, 0, 2, 2, 0, 0, 1, 0, 0, 0, 0, 2, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Ilya Gutkovskiy, Jan 18 2017

nonn

Number of ways to write 2n as an ordered sum of two powers of 3.

First bisection of self-convolution of characteristic function of powers of 3.

			G.f. = x^2 + 2*x^4 + x^6 + 2*x^10 + 2*x^12 + x^18 + 2*x^28 + 2*x^30 + 2*x^36 + ...
a(2) = 2 because we have [3, 1] and [1, 3].

Index entries for sequences related to compositions

Cf. A000244, A055235, A073267, A078932.

Take[CoefficientList[Series[Sum[x^3^k, {k, 0, 15}]^2, {x, 0, 260}], x], {1, -1, 2}]

G.f.: (Sum_{k>=0} x^(3^k))^2 [even terms only].

A346564 Number of compositions (ordered partitions) of 3^n into powers of 3.

Original entry on oeis.org

1, 2, 20, 26426, 61390791862967, 769671787836269530451291677988751813890576

Offset: 0

Ilya Gutkovskiy, Jul 23 2021

nonn

The next term is too large to include.

Index entries for sequences related to compositions

Cf. A000244, A078125, A078932, A248377, A337990, A346565.

Table[SeriesCoefficient[1/(1 - Sum[x^(3^k), {k, 0, n}]), {x, 0, 3^n}], {n, 0, 5}]

a(n) = [x^(3^n)] 1 / (1 - Sum_{k>=0} x^(3^k)).

a(n) = A078932(A000244(n)).

A382189 Expansion of 1/(1 - 4 * Sum_{k>=0} x^(3^k))^(1/2).

Original entry on oeis.org

1, 2, 6, 22, 82, 312, 1210, 4752, 18834, 75186, 301868, 1217664, 4930918, 20033432, 81621456, 333357656, 1364395770, 5594799576, 22980090870, 94529049296, 389367825444, 1605758772136, 6629456308464, 27397510466856, 113329594803078, 469183242566016, 1943927996932656

Offset: 0

Seiichi Manyama, Mar 18 2025

Cf. A078932, A382190.

G.f. A(x) satisfies A(x) = 1/(1/A(x^3)^2 - 4*x)^(1/2).

cp's OEIS Frontend

A087221 Number of compositions (ordered partitions) of n into powers of 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A235684 Number of compositions of n into powers of 3 and doubled powers of 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A374565 Expansion of g.f. A(x) satisfying A(x)^3 = A( x*A(x)^2/(1-x) ).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A087218 Satisfies A(x) = 1 + x*A(x)*f(x)^2, where f(x) = Sum_{k>=0} x^((3^n-1)/2) and f(x)^2 = 2 - f(x^2) + 2*Sum_{n>0} x^A023745(n).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A087219 Satisfies A(x) = f(x) + x*A(x)*f(x)^2, where f(x) = Sum_{k>=0} x^((3^n-1)/2) and f(x)^2 = 2 - f(x^2) + 2*Sum_{n>0} x^A023745(n). Also, A(x) = f(x)*B(x), where B(x) = Sum_{k>=0} A087218(k)*x^k.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A235773 Number of compositions of n into distinct powers of 3 and doubled powers of 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A382190 Expansion of 1/(1 - 9 * Sum_{k>=0} x^(3^k))^(1/3).

Views

Author

Keywords

Crossrefs

Formula

A281228 Expansion of (Sum_{k>=0} x^(3^k))^2 [even terms only].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

A087218 Satisfies A(x) = 1 + xA(x)f(x)^2, where f(x) = Sum_{k>=0} x^((3^n-1)/2) and f(x)^2 = 2 - f(x^2) + 2*Sum_{n>0} x^A023745(n).

A087219 Satisfies A(x) = f(x) + xA(x)f(x)^2, where f(x) = Sum_{k>=0} x^((3^n-1)/2) and f(x)^2 = 2 - f(x^2) + 2Sum_{n>0} x^A023745(n). Also, A(x) = f(x)B(x), where B(x) = Sum_{k>=0} A087218(k)*x^k.