A292886 Number of knapsack factorizations of n.

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 6, 2, 2, 2, 8, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 11, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11, 1, 2, 4, 7, 2, 5, 1, 4, 2, 5, 1, 15, 1, 2, 4, 4, 2, 5, 1, 11, 4, 2, 1, 11, 2

Offset

1,4

Comments

A knapsack factorization is a finite multiset of positive integers greater than one such that every distinct submultiset has a different product.

The sequence giving the number of factorizations of n is described as "the multiplicative partition function" (see A001055), so knapsack factorizations are a multiplicative generalization of knapsack partitions. - Gus Wiseman, Oct 24 2017

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..2000

Example

The a(36) = 8 factorizations are 2*2*3*3, 2*2*9, 2*18, 3*3*4, 3*12, 4*9, 6*6, 36. The factorization 2*3*6 is not knapsack.

Mathematica

postfacs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[postfacs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
Table[Length[Select[postfacs[n], UnsameQ@@Times@@@Union[Subsets[#]]&]], {n, 100}]

Crossrefs

Cf. A001055, A045778, a(p^n) = A108917(n), A162247, A259936, A275972, A281116.

Sequence in context: A343652 A034836 A316365 * A317508 A323438 A317141

Adjacent sequences: A292883 A292884 A292885 * A292887 A292888 A292889

Keyword

nonn

Author

Gus Wiseman, Sep 26 2017

Status

approved