A301979 -id:A301979 - cp's OEIS frontend

A304792 Number of subset-sums of integer partitions of n.

1, 2, 5, 10, 19, 34, 58, 96, 152, 240, 361, 548, 795, 1164, 1647, 2354, 3243, 4534, 6150, 8420, 11240, 15156, 19938, 26514, 34513, 45260, 58298, 75704, 96515, 124064, 157072, 199894, 251097, 317278, 395625, 496184, 615229, 765836, 944045, 1168792, 1432439

Offset: 0

Gus Wiseman, May 18 2018

nonn

For a multiset p of positive integers summing to n, a pair (t,p) is defined to be a subset sum if there exists a submultiset of p summing to t. This sequence is dominated by A122768 + A000041 (number of submultisets of integer partitions of n).

			The a(4)=19 subset sums are (0,4), (4,4), (0,31), (1,31), (3,31), (4,31), (0,22), (2,22), (4,22), (0,211), (1,211), (2,211), (3,211), (4,211), (0,1111), (1,1111), (2,1111), (3,1111), (4,1111).

Robert Price, Table of n, a(n) for n = 0..70

Cf. A000041, A108917, A122768, A276024, A284640, A299701, A301856, A301934, A301979, A304793.

b:= proc(n, i, s) option remember; `if`(n=0, nops(s),
     `if`(i<1, 0, b(n, i-1, s)+b(n-i, min(n-i, i),
      map(x-> [x, x+i][], s))))
    end:
a:= n-> b(n$2, {0}):
seq(a(n), n=0..40);  # Alois P. Heinz, May 18 2018

Table[Total[Length[Union[Total/@Subsets[#]]]&/@IntegerPartitions[n]],{n,15}]
(* Second program: *)
b[n_, i_, s_] := b[n, i, s] = If[n == 0, Length[s],
     If[i < 1, 0, b[n, i - 1, s] + b[n - i, Min[n - i, i],
     {#, # + i}& /@ s // Flatten // Union]]];
a[n_] := b[n, n, {0}];
a /@ Range[0, 40] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

from functools import lru_cache
@lru_cache(maxsize=None)
def A304792_T(n,i,s,l):
    if n==0: return l
    if i<1: return 0
    return A304792_T(n,i-1,s,l)+A304792_T(n-i,min(n-i,i),(t:=tuple(sorted(set(s+tuple(x+i for x in s))))),len(t))
def A304792(n): return A304792_T(n,n,(0,),1) # Chai Wah Wu, Sep 25 2023, after Alois P. Heinz

a(n) = A276024(n) + A000041(n).

A301957 Number of distinct subset-products of the integer partition with Heinz number n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Mar 29 2018

nonn

A subset-product of an integer partition y is a product of some submultiset of y. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

Number of distinct values obtained when A003963 is applied to all divisors of n. - Antti Karttunen, Sep 05 2018

			The distinct subset-products of (4,2,1,1) are 1, 2, 4, and 8, so a(84) = 4.
The distinct subset-products of (6,3,2) are 1, 2, 3, 6, 12, 18, and 36, so a(195) = 7.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from indices in prime factorization

Cf. A000712, A001055, A001227, A002865, A003963, A108917, A162247, A276024, A292886, A301854, A301855, A301856, A301970, A301979, A304793.

Table[If[n===1,1,Length[Union[Times@@@Subsets[Join@@Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]]],{n,100}]

up_to = 65537;
A003963(n) = { n=factor(n); n[, 1]=apply(primepi, n[, 1]); factorback(n) }; \\ From A003963
v003963 = vector(up_to,n,A003963(n));
A301957(n) = { my(m=Map(),s,k=0,c); fordiv(n,d,if(!mapisdefined(m,s = v003963[d],&c), mapput(m,s,s); k++)); (k); }; \\ Antti Karttunen, Sep 05 2018

More terms from Antti Karttunen, Sep 05 2018

A301970 Heinz numbers of integer partitions with more subset-products than subset-sums.

Original entry on oeis.org

165, 273, 325, 351, 495, 525, 561, 595, 675, 741, 765, 819, 825, 931, 1045, 1053, 1155, 1173, 1425, 1485, 1495, 1575, 1625, 1653, 1683, 1771, 1785, 1815, 1911, 2025, 2139, 2145, 2223, 2275, 2277, 2295, 2310, 2415, 2457, 2465, 2475, 2625, 2639, 2695, 2805, 2945

Offset: 1

Gus Wiseman, Mar 29 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). A subset-sum (or subset-product) of a multiset y is any number equal to the sum (or product) of some submultiset of y.

Numbers n such that A301957(n) > A299701(n).

			Sequence of partitions begins: (532), (642), (633), (6222), (5322), (4332), (752), (743), (33222), (862), (7322), (6422), (5332), (844), (853), (62222), (5432), (972), (8332), (53222), (963), (43322), (6333).

Cf. A000712, A003963, A056239, A108917, A276024, A284640, A292886, A296150, A299701, A299702, A299729, A301854, A301855, A301856, A301957, A301979.

Select[Range[1000],With[{ptn=If[#===1,{},Join@@Cases[FactorInteger[#],{p_,k_}:>Table[PrimePi[p],{k}]]]},Length[Union[Times@@@Subsets[ptn]]]>Length[Union[Plus@@@Subsets[ptn]]]]&]

A299764 Number of special products of factorizations of n into factors > 1.

Original entry on oeis.org

1, 2, 2, 5, 2, 6, 2, 10, 5, 6, 2, 16, 2, 6, 6, 18, 2, 16, 2, 16, 6, 6, 2, 36, 5, 6, 10, 16, 2, 22, 2, 32, 6, 6, 6, 44, 2, 6, 6, 36, 2, 22, 2, 16, 16, 6, 2, 72, 5, 16, 6, 16, 2, 36, 6, 36, 6, 6, 2, 64, 2, 6, 16, 51, 6, 22, 2, 16, 6, 22, 2, 104, 2, 6, 16, 16, 6

Offset: 1

Gus Wiseman, Jun 08 2018

nonn

A special product of a factorization f is a number n > 0 such that exactly one submultiset of f has product n.

			The a(12) = 16 special subset-products:
1<=(12), 12<=(12),
1<=(2*6), 2<=(2*6), 6<=(2*6), 12<=(2*6),
1<=(3*4), 3<=(3*4), 4<=(3*4), 12<=(3*4),
1<=(2*2*3), 2<=(2*2*3), 3<=(2*2*3), 4<=(2*2*3), 6<=(2*2*3), 12<=(2*2*3).
The a(16) = 18 special subset-products:
1<=(16), 16<=(16),
1<=(4*4), 4<=(4*4), 16<=(4*4),
1<=(2*8), 2<=(2*8), 8<=(2*8), 16<=(2*8),
1<=(2*2*4), 2<=(2*2*4), 8<=(2*2*4), 16<=(2*2*4),
1<=(2*2*2*2), 2<=(2*2*2*2), 4<=(2*2*2*2), 8<=(2*2*2*2), 16<=(2*2*2*2).

Cf. A001055, A292886, A299701, A301829, A301830, A301854, A301957, A301979, A304796.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
sppr[y_]:=Join@@Select[GatherBy[Union[Subsets[y]],Times@@#&],Length[#]===1&];
Table[Length[Join@@sppr/@facs[n]],{n,30}]

cp's OEIS Frontend

A304792 Number of subset-sums of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A301957 Number of distinct subset-products of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A301970 Heinz numbers of integer partitions with more subset-products than subset-sums.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A299764 Number of special products of factorizations of n into factors > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica