A323091 Number of strict knapsack factorizations of n.

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 3, 1, 3, 2, 2, 1, 5, 1, 2, 2, 3, 1, 5, 1, 3, 2, 2, 2, 4, 1, 2, 2, 5, 1, 5, 1, 3, 3, 2, 1, 7, 1, 3, 2, 3, 1, 5, 2, 5, 2, 2, 1, 9, 1, 2, 3, 3, 2, 5, 1, 3, 2, 5, 1, 9, 1, 2, 3, 3, 2, 5, 1, 7, 2, 2, 1, 9, 2, 2, 2

Offset

1,6

Comments

A strict knapsack factorization is a finite set of positive integers > 1 such that every subset has a different product.

Links

Table of n, a(n) for n=1..87.

Formula

a(prime^n) = A275972(n).

Example

The a(144) = 11 factorizations:
  (144),
  (2*72), (3*48), (4*36),(6*24), (8*18), (9*16),
  (2*3*24), (2*4*18), (2*8*9), (3*6*8).
Missing from this list are (2*6*12), (3*4*12), (2*3*4*6), which are not knapsack.

Mathematica

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

Crossrefs

Cf. A001055, A045778, A108917, A120641, A275972, A292886, A305150, A323087.

Sequence in context: A342083 A316364 A318357 * A045778 A320889 A296133

Adjacent sequences: A323088 A323089 A323090 * A323092 A323093 A323094

Keyword

nonn

Author

Gus Wiseman, Jan 04 2019

Status

approved