login
Number of distinct positive subset-sums of the multiset of prime factors of n.
11

%I #18 Aug 23 2021 13:06:36

%S 0,1,1,2,1,3,1,3,2,3,1,5,1,3,3,4,1,5,1,5,3,3,1,7,2,3,3,5,1,6,1,5,3,3,

%T 3,8,1,3,3,7,1,7,1,5,5,3,1,9,2,5,3,5,1,7,3,7,3,3,1,9,1,3,5,6,3,7,1,5,

%U 3,6,1,10,1,3,5,5,3,7,1,9,4,3,1,10,3,3

%N Number of distinct positive subset-sums of the multiset of prime factors of n.

%C An integer n is a positive subset-sum of a multiset y if there exists a nonempty submultiset of y with sum n.

%C One less than the number of distinct values obtained when A001414 is applied to all divisors of n. - _Antti Karttunen_, Jun 13 2018

%H Antti Karttunen, <a href="/A305611/b305611.txt">Table of n, a(n) for n = 1..65537</a>

%e The a(12) = 5 positive subset-sums of {2, 2, 3} are 2, 3, 4, 5, and 7.

%t Table[Length[Union[Total/@Rest[Subsets[Join@@Cases[FactorInteger[n],{p_,k_}:>Table[p,{k}]]]]]],{n,100}]

%o (PARI)

%o up_to = 65537;

%o A001414(n) = ((n=factor(n))[, 1]~*n[, 2]); \\ From A001414.

%o v001414 = vector(up_to,n,A001414(n));

%o A305611(n) = { my(m=Map(),s,k=0); fordiv(n,d,if(!mapisdefined(m,s = v001414[d]), mapput(m,s,s); k++)); (k-1); }; \\ _Antti Karttunen_, Jun 13 2018

%o (Python)

%o from sympy import factorint

%o from sympy.utilities.iterables import multiset_combinations

%o def A305611(n):

%o fs = factorint(n)

%o return len(set(sum(d) for i in range(1,sum(fs.values())+1) for d in multiset_combinations(fs,i))) # _Chai Wah Wu_, Aug 23 2021

%Y Cf. A001414, A027746, A056239, A122768, A276024, A284640, A299701, A299702, A301855, A301935, A301957, A304792, A304793, A305613.

%K nonn

%O 1,4

%A _Gus Wiseman_, Jun 06 2018