A117146 Number of parts in all s-partitions of n. An s-partition of n is a partition of n into parts of the form 2^j-1 (j=1,2,...).

0, 1, 2, 4, 6, 8, 12, 16, 20, 27, 34, 40, 50, 60, 70, 85, 100, 115, 136, 156, 176, 206, 234, 261, 300, 336, 370, 418, 466, 511, 572, 633, 690, 765, 840, 914, 1008, 1102, 1194, 1307, 1420, 1530, 1668, 1806, 1940, 2107, 2272, 2431, 2626, 2825, 3016, 3246, 3484

Offset

0,3

Links

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

P. C. P. Bhatt, An interesting way to partition a number, Inform. Process. Lett., 71, 1999, 141-148.

W. M. Y. Goh, P. Hitczenko and A. Shokoufandeh, s-partitions, Inform. Process. Lett., 82, 2002, 327-329.

Formula

a(n) = Sum_{k=1..n} k*A117145(n,k).

G.f.: sum(x^(2^k-1)/(1-x^(2^k-1)), k=1..infinity)/product(1-x^(2^k-1), k=1..infinity).

Example

a(7) = 16 because the s-partitions of 7 are [7],[3,3,1],[3,1,1,1,1] and [1,1,1,1,1,1,1], with a total of 1 + 3 + 5 + 7 = 16 parts.

Maple

g:=sum(x^(2^k-1)/(1-x^(2^k-1)), k=1..10)/product(1-x^(2^k-1), k=1..10): gser:=series(g, x, 60): seq(coeff(gser, x, n), n=0..56);
# Alternative:
b:= proc(n, i) option remember; `if`(n=0, [1, 0], `if`(i<1, 0,
      b(n, i-1)+(p-> `if`(p>n, 0, (f-> f+[0, f[1]])(b(n-p, i))))(2^i-1)))
    end:
a:= n-> b(n, 1+ilog2(n))[2]:
seq(a(n), n=0..52);  # Alois P. Heinz, Oct 01 2025

Mathematica

b[n_, i_] := b[n, i] = Which[n == 0, {1, 0}, i < 1, 0, True, b[n, i-1] + Function[p, If[p > n, 0, Function[f, f + {0, f[[1]]}][b[n-p, i]]]][2^i-1]];
a[n_] := b[n, Length[IntegerDigits[n, 2]]][[2]];
Table[a[n], {n, 0, 52}] (* Jean-François Alcover, Mar 03 2026, after Alois P. Heinz *)

Crossrefs

Cf. A117145.

Sequence in context: A346311 A097921 A185976 * A061553 A138934 A008764

Adjacent sequences: A117143 A117144 A117145 * A117147 A117148 A117149

Keyword

nonn

Author

Emeric Deutsch, Mar 06 2006

Extensions

Missing a(0)=0 inserted by Alois P. Heinz, Oct 01 2025

Status

approved