cp's OEIS Frontend

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

%I A305611 #18 Aug 23 2021 13:06:36
%S A305611 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 A305611 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 A305611 3,6,1,10,1,3,5,5,3,7,1,9,4,3,1,10,3,3
%N A305611 Number of distinct positive subset-sums of the multiset of prime factors of n.
%C A305611 An integer n is a positive subset-sum of a multiset y if there exists a nonempty submultiset of y with sum n.
%C A305611 One less than the number of distinct values obtained when A001414 is applied to all divisors of n. - _Antti Karttunen_, Jun 13 2018
%H A305611 Antti Karttunen, <a href="/A305611/b305611.txt">Table of n, a(n) for n = 1..65537</a>
%e A305611 The a(12) = 5 positive subset-sums of {2, 2, 3} are 2, 3, 4, 5, and 7.
%t A305611 Table[Length[Union[Total/@Rest[Subsets[Join@@Cases[FactorInteger[n],{p_,k_}:>Table[p,{k}]]]]]],{n,100}]
%o A305611 (PARI)
%o A305611 up_to = 65537;
%o A305611 A001414(n) = ((n=factor(n))[, 1]~*n[, 2]); \\ From A001414.
%o A305611 v001414 = vector(up_to,n,A001414(n));
%o A305611 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 A305611 (Python)
%o A305611 from sympy import factorint
%o A305611 from sympy.utilities.iterables import multiset_combinations
%o A305611 def A305611(n):
%o A305611     fs = factorint(n)
%o A305611     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 A305611 Cf. A001414, A027746, A056239, A122768, A276024, A284640, A299701, A299702, A301855, A301935, A301957, A304792, A304793, A305613.
%K A305611 nonn
%O A305611 1,4
%A A305611 _Gus Wiseman_, Jun 06 2018