A316365 Number of factorizations of n into factors > 1 such that every distinct subset of the factors has a different sum.

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, 4, 1, 6, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 9, 2, 4, 2, 4, 1, 6, 2, 7, 2, 2, 1, 10, 1, 2, 4, 9, 2, 5, 1, 4, 2, 4, 1, 14, 1, 2, 4, 4, 2, 5, 1, 11, 5, 2, 1, 9, 2, 2, 2, 7, 1, 10, 2, 4, 2, 2, 2, 15, 1, 4, 4, 9, 1, 5, 1, 7, 5

Offset

1,4

Comments

Also the number of factorizations of n into factors > 1 which form a knapsack partition.

Links

Antti Karttunen, Table of n, a(n) for n = 1..10080

Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Example

The a(24) = 7 factorizations are (2*2*2*3), (2*2*6), (2*3*4), (2*12), (3*8), (4*6), (24).
The a(54) = 6 factorizations are (2*3*3*3), (2*3*9), (2*27), (3*18), (6*9), (54).

Mathematica

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

Prog

(PARI)
primeprodbybits(v, b) = { my(m=1, i=1); while(b>0, if(b%2, m *= prime(v[i])); i++; b >>= 1); (m); };
sumbybits(v, b) = { my(s=0, i=1); while(b>0, s += (b%2)*v[i]; i++; b >>= 1); (s); };
all_distinct_subsets_have_different_sums(v) = { my(m=Map(), s, pp); for(i=0, (2^#v)-1, pp = primeprodbybits(v, i); s = sumbybits(v, i); if(mapisdefined(m, s), if(mapget(m, s)!=pp, return(0)), mapput(m, s, pp))); (1); };
A316365(n, m=n, facs=List([])) = if(1==n, all_distinct_subsets_have_different_sums(Vec(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs, d); s += A316365(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Oct 08 2018

Crossrefs

Cf. A001055, A108917, A275972, A292886, A293627, A294150, A299702, A316313, A316314, A316364.

Sequence in context: A319685 A343652 A034836 * A292886 A317508 A323438

Adjacent sequences: A316362 A316363 A316364 * A316366 A316367 A316368

Keyword

nonn

Author

Gus Wiseman, Jun 30 2018

Extensions

More terms from Antti Karttunen, Oct 08 2018

Status

approved