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

Author

Gus Wiseman, Jan 04 2019

Keywords

• nonn

Comments

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

Examples

			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.
		

Crossrefs

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

Programs

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}]

Formula

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