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,5

Comments

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 +...).

Links

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

Formula

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

Example

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

Maple

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

Mathematica

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

Prog

(PARI) 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))
(PARI)
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 */

Crossrefs

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

Sequence in context: A003269 A367794 A352043 * A352041 A295072 A206739

Adjacent sequences: A087218 A087219 A087220 * A087222 A087223 A087224

Keyword

nonn

Author

Paul D. Hanna, Aug 27 2003

Status

approved