A023359 Number of compositions (ordered partitions) of n into powers of 2.
1, 1, 2, 3, 6, 10, 18, 31, 56, 98, 174, 306, 542, 956, 1690, 2983, 5272, 9310, 16448, 29050, 51318, 90644, 160118, 282826, 499590, 882468, 1558798, 2753448, 4863696, 8591212, 15175514, 26805983, 47350056, 83639030, 147739848, 260967362
Offset: 0
Examples
A(x) = A(x^2) + x*A(x^2)^2 + x^2*A(x^2)^3 + x^3*A(x^2)^4 + ... = 1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + 18x^6 + 31x^7 + .... From _Joerg Arndt_, Dec 28 2012: (Start) There are a(6)=18 compositions of 6 into powers of 2: [ 1] [ 1 1 1 1 1 1 ] [ 2] [ 1 1 1 1 2 ] [ 3] [ 1 1 1 2 1 ] [ 4] [ 1 1 2 1 1 ] [ 5] [ 1 1 2 2 ] [ 6] [ 1 1 4 ] [ 7] [ 1 2 1 1 1 ] [ 8] [ 1 2 1 2 ] [ 9] [ 1 2 2 1 ] [10] [ 1 4 1 ] [11] [ 2 1 1 1 1 ] [12] [ 2 1 1 2 ] [13] [ 2 1 2 1 ] [14] [ 2 2 1 1 ] [15] [ 2 2 2 ] [16] [ 2 4 ] [17] [ 4 1 1 ] [18] [ 4 2 ] (End)
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n = 0..200 from T. D. Noe)
- G. Alkauskas, Congruence properties of the function that counts compositions into powers of 2, J. Integer Sequences 13 (2010), Article: 10.5.3, 2010.
- Giedrius Alkauskas, Algebraic functions with Fermat property, eigenvalues of transfer operator and Riemann zeros, and other open problems, arXiv:1609.09842 [math.NT], 2016. Mentions this sequence.
- Jung-Chao Ban, Wen-Guei Hu, Guan-Yu Lai, and Lingmin Liao, Entropy of axial product of multiplicative subshifts, arXiv:2402.19324 [math.DS], 2024. See p. 13.
- N. J. A. Sloane, Transforms.
- Wikipedia, Location arithmetic.
Programs
-
Maple
a:= proc(n) option remember; `if`(n=0, 1, add(a(n-2^i), i=0..ilog2(n))) end: seq(a(n), n=0..50); # Alois P. Heinz, Jan 11 2014 -
Mathematica
CoefficientList[Series[1/(1 - Sum[x^(2^i), {i, 0, 20}]), {x, 0, 20}], x] a[0] = 1; a[n_] := a[n] = Sum[a[n-2^k], {k, 0, Log[2, n]}]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Oct 25 2015, after Alois P. Heinz *) -
PARI
{a(n) = local(A, m); if( n<0, 0, m=1; A = 1 + O(x); while( m<=n, m*=2; A = 1 /(1 / subst(A, x, x^2) - x)); polcoeff(A, n))}; /* Michael Somos, Dec 20 2002 */ -
PARI
N=66; x='x+O('x^N); Vec( 1/(1-sum(k=0,ceil(log(N)/log(2)), x^(2^k) ) ) ) /* Joerg Arndt, Oct 21 2012 */
Formula
G.f.: 1 / (1 - Sum_{k>=0} x^(2^k)). - Joerg Arndt, Oct 21 2012
a(n) = [n=0] + Sum_{k>=0} a(n-2^k). - Len Smiley, May 07 2001
A(x) = A(x^2)/(1 - x*A(x^2)). - Paul D. Hanna, Dec 16 2002
INVERT transform of characteristic function of powers of 2, i.e., A036987 interpreted with an offset 1 instead of 0. - Antti Karttunen, Dec 12 2003
a(n) seems to be asymptotic to A*B^n where A=0.332198..., B=1.766398... - Benoit Cloitre, Dec 17 2002. More accurately: B=1.76639811455017359722848839244009973023206928795707277527828507440838434..., A=0.58679374529351144845013208294162259198824401250194713608555348278359775... - Vaclav Kotesovec, Apr 30 2014
Satisfies A(x) = 1 + A(x) * Sum_{k>=0} x^(2^k). a(m) == 1 (mod 2) when m=2^n-1, otherwise a(m) == 0 (mod 2). - Paul D. Hanna, Aug 27 2003
a(m) == 0 (mod 4) if A000120(m+2) >= 4. In general, a(m) == 0 (mod 2^N) if A000120(m+2^(N-1)) >= 2^N. - Giedrius Alkauskas, Mar 05 2010
Extensions
Edited by Franklin T. Adams-Watters, Aug 05 2005
Comments