A304793 Number of distinct positive subset-sums of the integer partition with Heinz number n.

0, 1, 1, 2, 1, 3, 1, 3, 2, 3, 1, 4, 1, 3, 3, 4, 1, 5, 1, 5, 3, 3, 1, 5, 2, 3, 3, 5, 1, 6, 1, 5, 3, 3, 3, 6, 1, 3, 3, 6, 1, 7, 1, 5, 5, 3, 1, 6, 2, 5, 3, 5, 1, 7, 3, 7, 3, 3, 1, 7, 1, 3, 4, 6, 3, 7, 1, 5, 3, 6, 1, 7, 1, 3, 5, 5, 3, 7, 1, 7, 4, 3, 1, 8, 3, 3, 3, 7, 1, 8, 3, 5, 3, 3, 3, 7, 1, 5, 5, 8, 1, 7, 1, 7, 7

Offset: 1

Author

Gus Wiseman, May 18 2018

Keywords

• nonn

Comments

A positive integer n is a positive subset-sum of an integer partition y if there exists a submultiset of y with sum n. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

a(n) <= A000005(n).

One less than the number of distinct values obtained when A056239 is applied to all divisors of n. - Antti Karttunen, Jul 01 2018

Examples

			The positive subset-sums of (4,3,1) are {1, 3, 4, 5, 7, 8} so a(70) = 6.
The positive subset-sums of (5,1,1,1) are {1, 2, 3, 5, 6, 7, 8} so a(88) = 7.
		

Links

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

Crossrefs

Cf. A056239, A122768, A276024, A284640, A296150, A299701, A299702, A301855, A301935, A301957, A304792, A304795, A305611.

Programs

Mathematica

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

PARI

up_to = 65537;
A056239(n) = { my(f); if(1==n, 0, f=factor(n); sum(i=1, #f~, f[i,2] * primepi(f[i,1]))); }
v056239 = vector(up_to,n,A056239(n));
A304793(n) = { my(m=Map(),s,k=0); fordiv(n,d,if(!mapisdefined(m,s = v056239[d]), mapput(m,s,s); k++)); (k-1); }; \\ Antti Karttunen, Jul 01 2018

Extensions

More terms from Antti Karttunen, Jul 01 2018