|
%I #9 Oct 18 2018 21:16:37
%S 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,
%T 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,
%U 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
%N Number of factorizations of n into factors > 1 such that every distinct subset of the factors has a different sum.
%C Also the number of factorizations of n into factors > 1 which form a knapsack partition.
%H Antti Karttunen, <a href="/A316365/b316365.txt">Table of n, a(n) for n = 1..10080</a>
%H Antti Karttunen, <a href="/A316365/a316365.txt">Data supplement: n, a(n) computed for n = 1..100000</a>
%e The a(24) = 7 factorizations are (2*2*2*3), (2*2*6), (2*3*4), (2*12), (3*8), (4*6), (24).
%e The a(54) = 6 factorizations are (2*3*3*3), (2*3*9), (2*27), (3*18), (6*9), (54).
%t facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
%t Table[Length[Select[facs[n],UnsameQ@@Total/@Union[Subsets[#]]&]],{n,100}]
%o (PARI)
%o primeprodbybits(v,b) = { my(m=1,i=1); while(b>0,if(b%2, m *= prime(v[i])); i++; b >>= 1); (m); };
%o sumbybits(v,b) = { my(s=0,i=1); while(b>0,s += (b%2)*v[i]; i++; b >>= 1); (s); };
%o 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); };
%o 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
%Y Cf. A001055, A108917, A275972, A292886, A293627, A294150, A299702, A316313, A316314, A316364.
%K nonn
%O 1,4
%A _Gus Wiseman_, Jun 30 2018
%E More terms from _Antti Karttunen_, Oct 08 2018
|
