A023359 -id:A023359 - cp's OEIS frontend

A073266 Triangle read by rows: T(n,k) is the number of compositions of n as the sum of k integral powers of 2.

1, 1, 1, 0, 2, 1, 1, 1, 3, 1, 0, 2, 3, 4, 1, 0, 2, 4, 6, 5, 1, 0, 0, 6, 8, 10, 6, 1, 1, 1, 3, 13, 15, 15, 7, 1, 0, 2, 3, 12, 25, 26, 21, 8, 1, 0, 2, 6, 10, 31, 45, 42, 28, 9, 1, 0, 0, 6, 16, 30, 66, 77, 64, 36, 10, 1, 0, 2, 4, 18, 40, 76, 126, 126, 93, 45, 11, 1, 0, 0, 6, 16, 50, 96, 168, 224, 198, 130, 55, 12, 1

Offset: 1

Antti Karttunen, Jun 25 2002

Upper triangular region of the table A073265 read by rows. - Emeric Deutsch, Feb 04 2005

Also the convolution triangle of A209229. - Peter Luschny, Oct 07 2022

			T(6,3) = 4 because there are four ordered partitions of 6 into 3 powers of 2, namely: 4+1+1, 1+4+1, 1+1+4 and 2+2+2.
Triangle begins:
  1;
  1, 1;
  0, 2, 1;
  1, 1, 3, 1;
  0, 2, 3, 4, 1;
  0, 2, 4, 6, 5, 1;

G. C. Greubel, Rows n = 1..100 of triangle, flattened
S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210.

Cf. A048298, A073265, A023359 (row sums), A089052 (partitions of n).

T(2n,n) gives A333047.

b:= proc(n) option remember; expand(`if`(n=0, 1,
       add(b(n-2^j)*x, j=0..ilog2(n))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n)):
seq(T(n), n=1..14);  # Alois P. Heinz, Mar 06 2020
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, n -> if n = 2^ilog2(n) then 1 else 0 fi); # Peter Luschny, Oct 07 2022

m:= 10; T[n_, k_]:= T[n, k]= Coefficient[(Sum[x^(2^j), {j,0,m+1}])^k, x, n]; Table[T[n, k], {n,10}, {k,n}]//Flatten (* G. C. Greubel, Mar 06 2020 *)

T(n, k) = coefficient of x^n in the formal power series (x + x^2 + x^4 + x^8 + x^16 + ...)^k. - Emeric Deutsch, Feb 04 2005
T(0, k) = T(n, 0) = 0, T(n, k) = 0 if k > n, T(n, 1) = 1 if n = 2^m, 0 otherwise and in other cases T(n, k) = Sum_{i=0..floor(log_2(n-1))} T(n-(2^i), k-1). - Emeric Deutsch, Feb 04 2005
Sum_{k=0..n} T(n,k) = A023359(n). - Philippe Deléham, Nov 04 2006

A248377 Number of compositions of 1 into parts 1/2^k with 0 <= k <= n.

Original entry on oeis.org

1, 2, 6, 56, 5272, 47350056, 3820809588459176, 24878564279781563409541239097464, 1054787931172699885204409659788147413348784265452313995416385160

Offset: 0

Bassam Abdul-Baki, Oct 05 2014

nonn

Equivalently, the number of compositions of 2^n into powers of 2.

			a(0) = 1: [1].
a(1) = 2: [1/2,1/2], [1].
a(2) = 6: [1/4,1/4,1/4,1/4], [1/2,1/4,1/4], [1/4,1/2,1/4], [1/4,1/4,1/2],  [1/2,1/2], [1].

Alois P. Heinz, Table of n, a(n) for n = 0..11
B. Abdul-Baki, Rhythmic Figures

Cf. A023359.

Row sums of A323840.

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-2^j), j=0..ilog2(n)))
    end:
a:= n-> b(2^n):
seq(a(n), n=0..10);  # Alois P. Heinz, Oct 20 2014

$RecursionLimit = 2000; Clear[b]; b[n_] := b[n] = If[n == 0, 1, Sum[b[n - 2^j], {j, 0, Log[2, n] // Floor}]]; a[n_] := b[2^n]; Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Oct 30 2014, after Alois P. Heinz *)

a(n) = A023359(2^n).

lim_{n->oo} a(n+1)/a(n)^2 = 1.704176310706592045608982.... - Bassam Abdul-Baki, Sep 03 2020

A342250 Number of ways to write n as an ordered sum of seven powers of 2.

Original entry on oeis.org

1, 7, 21, 42, 77, 126, 168, 218, 294, 357, 427, 546, 637, 672, 756, 840, 854, 966, 1134, 1218, 1302, 1408, 1484, 1554, 1680, 1827, 1995, 2002, 1925, 2016, 1988, 1904, 2142, 2352, 2282, 2352, 2534, 2520, 2604, 2954, 3080, 3276, 3262, 3234, 3150, 3248, 3164, 3402, 3640

Offset: 7

Ilya Gutkovskiy, Mar 07 2021

Robert Israel, Table of n, a(n) for n = 7..10000

Cf. A000079, A023359, A073267, A151759, A151760, A151761, A151762, A209229, A342247, A342251, A342252, A342254.

N:= 100:
S:= add(x^(2^j),j=0..ilog2(N-6))^7:
[seq](coeff(S,x,j),j=7..N); # Robert Israel, Feb 26 2023

nmax = 55; CoefficientList[Series[Sum[x^(2^k), {k, 0, Floor[Log[2, nmax]] + 1}]^7, {x, 0, nmax}], x] // Drop[#, 7] &

G.f.: ( Sum_{k>=0} x^(2^k) )^7.

A342251 Number of ways to write n as an ordered sum of eight powers of 2.

Original entry on oeis.org

1, 8, 28, 64, 126, 224, 336, 464, 645, 840, 1044, 1344, 1666, 1904, 2192, 2528, 2730, 3024, 3528, 3920, 4284, 4768, 5168, 5488, 5965, 6552, 7140, 7616, 7834, 8176, 8400, 8352, 8862, 9632, 9800, 10080, 10788, 10976, 11152, 12208, 13090, 13664, 14392, 14672, 14868, 15008, 15344

Offset: 8

Ilya Gutkovskiy, Mar 07 2021

nonn

Robert Israel, Table of n, a(n) for n = 8..10000

Cf. A000079, A023359, A073267, A151759, A151760, A151761, A151762, A209229, A342248, A342250, A342252, A342254.

N:= 100:
S:= add(x^(2^j),j=0..ilog2(N-7))^8:
seq(coeff(S,x,j),j=8..N); # Robert Israel, Feb 26 2023

nmax = 54; CoefficientList[Series[Sum[x^(2^k), {k, 0, Floor[Log[2, nmax]] + 1}]^8, {x, 0, nmax}], x] // Drop[#, 8] &

G.f.: ( Sum_{k>=0} x^(2^k) )^8.

A162439 Write down the binary representation of n. Partition the string which is this binary representation by placing a '+' just left of every 1. Add the resulting base 2 numbers. a(n) = decimal equivalent of this sum.

Original entry on oeis.org

1, 2, 2, 4, 3, 3, 3, 8, 5, 4, 4, 5, 4, 4, 4, 16, 9, 6, 6, 6, 5, 5, 5, 9, 6, 5, 5, 6, 5, 5, 5, 32, 17, 10, 10, 8, 7, 7, 7, 10, 7, 6, 6, 7, 6, 6, 6, 17, 10, 7, 7, 7, 6, 6, 6, 10, 7, 6, 6, 7, 6, 6, 6, 64, 33, 18, 18, 12, 11, 11, 11, 12, 9, 8, 8, 9, 8, 8, 8, 18, 11, 8, 8, 8, 7, 7, 7, 11, 8, 7, 7, 8, 7, 7

Offset: 1

Leroy Quet, Jul 03 2009

From Vladimir Shevelev, Dec 11 2014: (Start)
Or, sum of parts of the form 10...0 with nonnegative number of zeros in binary representation of n as the corresponding powers of 2. For example, n=50 in binary is a concatenation of parts (1)(100)(10). Then a(50)=1+4+2=7.
Every positive number k occurs a finite number of times, such that the position of the last appearance of k is 2^k-1.
  Moreover, the number of times of appearances of k is the number of compositions of k into powers of 2, i.e., it is A023359(k), k>0. (End)

			52 in binary is 110100. Placing the +'s before every 1, we get +1+10+100, which is 1+2+4 = 7 in decimal. So a(52) = 7.

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

Cf. A124771, A233249, A233312, A233416, A233420, A233564, A233569, A233655.

a:= proc(n) local l, s, i, j; l:= convert(n, base, 2); s:= 0; i:=1; for j from nops(l)-1 to 1 by -1 do if l[j]=0 then i:= i*2; else s:= s+i; i:= 1 fi od; s+i end: seq(a(n), n=1..150); # Alois P. Heinz, Jul 28 2009
Lton := proc(L) local i ; add(op(i,L)*2^(i-1),i=1..nops(L)) ; end: A162439 := proc(n) local a,lef,b2,ri ; a := 0 ; lef := 0; b2 := convert(n,base,2) ; for ri from lef+1 do if op(ri,b2) = 1 then a := a+Lton([op(lef+1..ri,b2)]) ; lef := ri ; fi; if ri =nops(b2) then break; fi; od: a ; end: seq(A162439(n),n=1..100) ; # R. J. Mathar, Jul 30 2009

a[n_] := FromDigits[#, 2]& /@ Split[IntegerDigits[n, 2] , #2==0&] // Total; Array[a, 100] (* Jean-François Alcover, Jan 07 2016 *)

Let, for k_1>k_2>...>k_r, n = 2^k_1 + 2^k_2 +...+ 2^k_r. Then a(n) = 2^(k_1-k_2-1) + 2^(k_2-k_3-1) + 2^(k_(r-1)-k_r-1) + 2^k_r. - Vladimir Shevelev, Dec 11 2013

More terms from Alois P. Heinz and R. J. Mathar, Jul 28 2009

A342252 Number of ways to write n as an ordered sum of nine powers of 2.

Original entry on oeis.org

1, 9, 36, 93, 198, 378, 624, 927, 1341, 1849, 2412, 3159, 4074, 4950, 5904, 7032, 8010, 9018, 10488, 11970, 13356, 15108, 16848, 18315, 20085, 22257, 24444, 26671, 28674, 30510, 32208, 33282, 34974, 37590, 39384, 40986, 43668, 45468, 46512, 49620, 53298, 55890, 59304, 62442

Offset: 9

Ilya Gutkovskiy, Mar 07 2021

nonn

Cf. A000079, A023359, A073267, A151759, A151760, A151761, A151762, A209229, A342249, A342250, A342251, A342254.

nmax = 52; CoefficientList[Series[Sum[x^(2^k), {k, 0, Floor[Log[2, nmax]] + 1}]^9, {x, 0, nmax}], x] // Drop[#, 9] &

G.f.: ( Sum_{k>=0} x^(2^k) )^9.

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

Original entry on oeis.org

1, 2, 4, 7, 13, 23, 41, 72, 128, 226, 400, 706, 1248, 2204, 3894, 6877, 12149, 21459, 37907, 66957, 118275, 208919, 369037, 651863, 1151453, 2033921, 3592719, 6346167, 11209863, 19801075, 34976589, 61782572, 109132628, 192771658, 340511506, 601478868, 1062451154, 1876711698, 3315020026

Offset: 0

Ilya Gutkovskiy, Apr 28 2018

nonn

Partial sums of A023359.

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Index entries for sequences related to compositions

Cf. A000079, A000123, A023359, A209229.

a:= proc(n) option remember; 1+
     `if`(n>0, add(a(n-2^i), i=0..ilog2(n)), 0)
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 28 2018

nmax = 38; CoefficientList[Series[1/((1 - x) (1 - Sum[x^2^k, {k, 0, nmax}])), {x, 0, nmax}], x]
a[0] = 1; a[n_] := a[n] = Sum[Boole[k == 2^IntegerExponent[k, 2]] a[n - k], {k, 1, n}]; Accumulate[Table[a[n], {n, 0, 38}]]

A323840 Irregular triangle read by rows: T(n,k) is the number of compositions of 2^n into k powers of 2.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 13, 15, 15, 7, 1, 1, 1, 3, 13, 75, 165, 357, 645, 927, 1095, 957, 627, 299, 91, 15, 1, 1, 1, 3, 13, 75, 525, 1827, 5965, 18315, 51885, 130977, 304953, 646373, 1238601, 2143065, 3331429, 4663967, 5867703

Offset: 0

N. J. A. Sloane, Feb 04 2019

			The first few rows are:
  1;
  1, 1;
  1, 1, 3,  1;
  1, 1, 3, 13, 15,  15,   7,   1;
  1, 1, 3, 13, 75, 165, 357, 645, 927, 1095, 957, 627, 299, 91, 15, 1;
  ...
The counts for row 3 arise as follows:
  8 (1)
  = 4+4 (1)
  = 4+2+2 (3)
  = 4+2+1+1 or 2+2+2+2 (12+1=13)
  = 4+1+1+1+1 or 2+2+2+1+1 (5+10=15)
  = 2+2+1+1+1+1 (15)
  = 2+1+1+1+1+1+1 (7)
  = 1+1+1+1+1+1+1+1 (1)

James Rayman, Rows n = 0..10, flattened
S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210. See Table 2.

The rows are a subset of the rows of A073266.
Row sums give A248377.
T(n,n) gives A007178 (for n>=1).
Cf. A023359.

b:= proc(n) option remember; expand(`if`(n=0, 1,
      add(x*b(n-2^j), j=0..ilog2(n))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..2^n))(b(2^n)):
seq(T(n), n=0..5);  # Alois P. Heinz, Mar 31 2021

b[n_] := b[n] = Expand[If[n == 0, 1,
     Sum[x*b[n - 2^j], {j, 0, Length@IntegerDigits[n, 2]-1}]]];
T[n_] := With[{p = b[2^n]}, Table[Coefficient[p, x, i], {i, 1, 2^n}]];
Table[T[n], {n, 0, 5}] // Flatten (* Jean-François Alcover, Jul 07 2021, after Alois P. Heinz *)

from functools import lru_cache
@lru_cache(maxsize=None)
def t(n, k):
    if n < k: return 0
    if k == 0: return 1 if n == 0 else 0
    r = 0
    i = 1
    while True:
        if i > n: break
        r += t(n - i, k-1)
        i *= 2
    return r
def T(n, k): return t(2**n, k) # James Rayman, Mar 30 2021

T(n, k) = A073266(2^n, k). - James Rayman, Mar 30 2021

More terms from James Rayman, Mar 30 2021

A339422 G.f.: 1 / (1 + Sum_{k>=0} x^(2^k)).

Original entry on oeis.org

1, -1, 0, 1, -2, 2, 0, -3, 4, -2, -2, 6, -6, 0, 8, -11, 4, 10, -20, 14, 10, -36, 38, -2, -54, 84, -46, -56, 152, -144, -8, 221, -316, 146, 244, -570, 482, 120, -876, 1110, -350, -1108, 2138, -1520, -896, 3548, -3914, 566, 4906, -8068, 4714, 4864, -14080, 13652, 466, -20656

Offset: 0

Ilya Gutkovskiy, Dec 03 2020

sign

The difference between the number of compositions (ordered partitions) of n into an even number of powers of 2 and the number of compositions (ordered partitions) of n into an odd number of powers of 2.

Alois P. Heinz, Table of n, a(n) for n = 0..5000
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.

Cf. A000079, A023359, A104977, A209229.

b:= proc(n, t) option remember; `if`(n=0, t,
      add(b(n-2^i, -t), i=0..ilog2(n)))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..60);  # Alois P. Heinz, Dec 03 2020

nmax = 55; CoefficientList[Series[1/(1 + Sum[x^(2^k), {k, 0, Floor[Log[2, nmax]] + 1}]), {x, 0, nmax}], x]
a[0] = 1; a[n_] := a[n] = -Sum[If[IntegerQ[Log[2, k]], 1, 0] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 55}]

G.f. A(x) satisfies: A(x) = A(x^2) / (1 + x * A(x^2)).

a(0) = 1; a(n) = -Sum_{k=1..n} A209229(k) * a(n-k).

A342254 Number of ways to write n as an ordered sum of ten powers of 2.

Original entry on oeis.org

1, 10, 45, 130, 300, 612, 1095, 1750, 2655, 3850, 5281, 7110, 9460, 12060, 14940, 18352, 21850, 25380, 29790, 34740, 39672, 45480, 51885, 57870, 64375, 72090, 80145, 88630, 97660, 106380, 114736, 122260, 130050, 139740, 148990, 157572, 168240, 178200, 185490, 196200, 210082

Offset: 10

Ilya Gutkovskiy, Mar 07 2021

nonn

Cf. A000079, A023359, A073267, A151759, A151760, A151761, A151762, A209229, A319922, A342250, A342251, A342252.

nmax = 50; CoefficientList[Series[Sum[x^(2^k), {k, 0, Floor[Log[2, nmax]] + 1}]^10, {x, 0, nmax}], x] // Drop[#, 10] &

G.f.: ( Sum_{k>=0} x^(2^k) )^10.

cp's OEIS Frontend

A073266 Triangle read by rows: T(n,k) is the number of compositions of n as the sum of k integral powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A248377 Number of compositions of 1 into parts 1/2^k with 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A342250 Number of ways to write n as an ordered sum of seven powers of 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A342251 Number of ways to write n as an ordered sum of eight powers of 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A162439 Write down the binary representation of n. Partition the string which is this binary representation by placing a '+' just left of every 1. Add the resulting base 2 numbers. a(n) = decimal equivalent of this sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A342252 Number of ways to write n as an ordered sum of nine powers of 2.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A323840 Irregular triangle read by rows: T(n,k) is the number of compositions of 2^n into k powers of 2.

Views

Author

Keywords