A319913 -id:A319913

A319910

Number of distinct pairs (m, y), where m >= 1 and y is an integer partition of n, such that m can be obtained by iteratively adding or multiplying together parts of y until only one part (equal to m) remains.

+10
16

1, 3, 6, 11, 23, 48, 85, 178, 331, 619, 1176, 2183, 3876, 7013, 12447, 21719, 37628, 64570, 109723, 185055

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..20.

EXAMPLE

The a(4) = 11 pairs:

4 <= (4)

3 <= (3,1)

4 <= (3,1)

4 <= (2,2)

2 <= (2,1,1)

3 <= (2,1,1)

4 <= (2,1,1)

1 <= (1,1,1,1)

2 <= (1,1,1,1)

3 <= (1,1,1,1)

4 <= (1,1,1,1)

MATHEMATICA

ReplaceListRepeated[forms_, rerules_]:=Union[Flatten[FixedPointList[Function[pre, Union[Flatten[ReplaceList[#, rerules]&/@pre, 1]]], forms], 1]];

nexos[ptn_]:=If[Length[ptn]==0, {0}, Union@@Select[ReplaceListRepeated[{Sort[ptn]}, {{foe___, x_, mie___, y_, afe___}:>Sort[Append[{foe, mie, afe}, x+y]], {foe___, x_, mie___, y_, afe___}:>Sort[Append[{foe, mie, afe}, x*y]]}], Length[#]==1&]];

Table[Total[Length/@nexos/@IntegerPartitions[n]], {n, 20}]

CROSSREFS

Cf. A000792, A001970, A005520, A048249, A066739, A066815, A275870, A319850, A318949, A319909, A319912, A319913.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Oct 01 2018

STATUS

approved

A267597

Number of sum-product knapsack partitions of n. Number of integer partitions y of n such that every sum of products of the parts of a multiset partition of any submultiset of y is distinct.

+10
8

1, 1, 1, 1, 1, 2, 3, 3, 4, 4, 6, 7, 8, 12, 12, 14, 18, 23, 23, 32, 30, 35, 50, 48, 47, 56, 80, 77, 87, 105, 100, 134, 139, 145, 194, 170, 192, 250

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

LINKS

Table of n, a(n) for n=0..37.

Sean A. Irvine, Java program (github)

EXAMPLE

The sequence of product-sum knapsack partitions begins:

0: ()

1: (1)

2: (2)

3: (3)

4: (4)

5: (5) (3,2)

6: (6) (4,2) (3,3)

7: (7) (5,2) (4,3)

8: (8) (6,2) (5,3) (4,4)

9: (9) (7,2) (6,3) (5,4)

10: (10) (8,2) (7,3) (6,4) (5,5) (4,3,3)

11: (11) (9,2) (8,3) (7,4) (6,5) (5,4,2) (5,3,3)

The partition (4,4,3) is not a sum-product knapsack partition of 11 because (4*4) = (4)+(4*3).

A complete list of all sums of products of multiset partitions of submultisets of (5,4,2) is:

0 = 0

(2) = 2

(4) = 4

(5) = 5

(2*4) = 8

(2*5) = 10

(4*5) = 20

(2*4*5) = 40

(2)+(4) = 6

(2)+(5) = 7

(2)+(4*5) = 22

(4)+(5) = 9

(4)+(2*5) = 14

(5)+(2*4) = 13

(2)+(4)+(5) = 11

These are all distinct, so (5,4,2) is a sum-product knapsack partition of 11.

MATHEMATICA

sps[{}]:={{}};

sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

rrtuks[n_]:=Select[IntegerPartitions[n], Function[q, UnsameQ@@Apply[Plus, Apply[Times, Union@@mps/@Union[Subsets[q]], {2}], {1}]]];

Table[Length[rrtuks[n]], {n, 12}]

CROSSREFS

Cf. A001970, A066739, A108917, A275972, A292886, A316313, A318949, A319318, A319320, A319910, A319913.

Cf. A320052, A320053, A320054, A320055, A320056, A320057, A320058.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Oct 04 2018

EXTENSIONS

a(13)-a(37) from Sean A. Irvine, Jul 13 2022

STATUS

approved

A319909

Number of distinct positive integers that can be obtained by iteratively adding any two or multiplying any two non-1 parts of an integer partition until only one part remains, starting with 1^n.

+10
8

0, 1, 1, 1, 1, 2, 4, 5, 10, 15, 21, 34, 49, 68, 101, 142, 197, 280, 387, 538, 751, 1045, 1442, 2010, 2772, 3865, 5339, 7396, 10273, 14201, 19693

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

LINKS

Table of n, a(n) for n=0..30.

EXAMPLE

We have

7 = 1+1+1+1+1+1+1,

8 = (1+1)*(1+1+1)+1+1,

9 = (1+1)*(1+1)*(1+1)+1,

10 = (1+1+1+1+1)*(1+1),

12 = (1+1+1)*(1+1+1+1),

so a(7) = 5.

MATHEMATICA

ReplaceListRepeated[forms_, rerules_]:=Union[Flatten[FixedPointList[Function[pre, Union[Flatten[ReplaceList[#, rerules]&/@pre, 1]]], forms], 1]];

mexos[ptn_]:=If[Length[ptn]==0, {0}, Union@@Select[ReplaceListRepeated[{Sort[ptn]}, {{foe___, x_, mie___, y_, afe___}:>Sort[Append[{foe, mie, afe}, x+y]], {foe___, x_?(#>1&), mie___, y_?(#>1&), afe___}:>Sort[Append[{foe, mie, afe}, x*y]]}], Length[#]==1&]];

Table[Length[mexos[Table[1, {n}]]], {n, 30}]

CROSSREFS

Cf. A000792, A001970, A005520, A048249, A066739, A066815, A070960, A201163, A275870, A319850, A318948, A318949, A319912, A319913.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Oct 01 2018

STATUS

approved

A320052

Number of product-sum knapsack partitions of n. Number of integer partitions y of n such that every product of sums of the parts of a multiset partition of any submultiset of y is distinct.

+10
7

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

LINKS

Table of n, a(n) for n=0..12.

EXAMPLE

The sequence of product-sum knapsack partitions begins:

0: ()

1:

2: (2)

3: (3)

4: (4)

5: (5) (3,2)

6: (6) (4,2) (3,3)

7: (7) (5,2) (4,3)

8: (8) (6,2) (5,3) (4,4)

9: (9) (7,2) (6,3) (5,4)

10: (10) (8,2) (7,3) (6,4) (5,5) (4,3,3)

11: (11) (9,2) (8,3) (7,4) (6,5) (5,4,2) (5,3,3) (4,4,3)

12: (12) (10,2) (9,3) (8,4) (7,5) (7,3,2) (6,6) (4,4,4)

A complete list of all products of sums of multiset partitions of submultisets of (4,3,3) is:

() = 1

(3) = 3

(4) = 4

(3+3) = 6

(3+4) = 7

(3+3+4) = 10

(3)*(3) = 9

(3)*(4) = 12

(3)*(3+4) = 21

(4)*(3+3) = 24

(3)*(3)*(4) = 36

These are all distinct, so (4,3,3) is a product-sum knapsack partition of 10.

MATHEMATICA

sps[{}]:={{}};

sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

rrsuks[n_]:=Select[IntegerPartitions[n], Function[q, UnsameQ@@Apply[Times, Apply[Plus, Union@@mps/@Union[Subsets[q]], {2}], {1}]]];

Table[Length[rrsuks[n]], {n, 12}]

CROSSREFS

Cf. A001970, A066739, A108917, A275972, A292886, A316313, A318949, A319318, A319320, A319910, A319913.

Cf. A267597, A320053, A320054, A320055, A320056, A320057, A320058.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Oct 04 2018

STATUS

approved

A320053

Number of spanning sum-product knapsack partitions of n. Number of integer partitions y of n such that every sum of products of the parts of a multiset partition of y is distinct.

+10
7

1, 1, 2, 3, 2, 3, 4, 5, 6, 8, 9, 12, 14

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

Table of n, a(n) for n=0..12.

EXAMPLE

The sequence of spanning sum-product knapsack partitions begins:

0: ()

1: (1)

2: (2) (1,1)

3: (3) (2,1) (1,1,1)

4: (4) (3,1)

5: (5) (4,1) (3,2)

6: (6) (5,1) (4,2) (3,3)

7: (7) (6,1) (5,2) (4,3) (3,3,1)

8: (8) (7,1) (6,2) (5,3) (4,4) (3,3,2)

9: (9) (8,1) (7,2) (6,3) (5,4) (4,4,1) (4,3,2) (3,3,3)

A complete list of all sums of products covering the parts of (3,3,3,2) is:

(2*3*3*3) = 54

(2)+(3*3*3) = 29

(3)+(2*3*3) = 21

(2*3)+(3*3) = 15

(2)+(3)+(3*3) = 14

(3)+(3)+(2*3) = 12

(2)+(3)+(3)+(3) = 11

These are all distinct, so (3,3,3,2) is a spanning sum-product knapsack partition of 11.

An example of a spanning sum-product knapsack partition that is not a spanning product-sum knapsack partition is (5,4,3,2).

MATHEMATICA

sps[{}]:={{}};

sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

rtuks[n_]:=Select[IntegerPartitions[n], Function[q, UnsameQ@@Apply[Plus, Apply[Times, mps[q], {2}], {1}]]];

Table[Length[rtuks[n]], {n, 8}]

CROSSREFS

Cf. A001970, A066739, A108917, A275972, A292886, A316313, A318949, A319318, A319320, A319910, A319913.

Cf. A267597, A320052, A320054, A320055, A320056, A320057, A320058.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Oct 04 2018

STATUS

approved

A320054

Number of spanning product-sum knapsack partitions of n. Number of integer partitions y of n such that every product of sums the parts of a multiset partition of y is distinct.

+10
7

1, 1, 2, 3, 2, 4, 5, 8, 10, 12, 16, 17, 25

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

Table of n, a(n) for n=0..12.

EXAMPLE

The sequence of spanning product-sum knapsack partitions begins

0: ()

1: (1)

2: (2) (1,1)

3: (3) (2,1) (1,1,1)

4: (4) (3,1)

5: (5) (4,1) (3,2) (3,1,1)

6: (6) (5,1) (4,2) (4,1,1) (3,3)

7: (7) (6,1) (5,2) (5,1,1) (4,3) (4,2,1) (4,1,1,1) (3,3,1)

8: (8) (7,1) (6,2) (6,1,1) (5,3) (5,2,1) (5,1,1,1) (4,4) (4,3,1) (3,3,2)

9: (9) (8,1) (7,2) (7,1,1) (6,3) (6,2,1) (6,1,1,1) (5,4) (5,3,1) (4,4,1) (4,3,2) (3,3,3)

A complete list of all products of sums covering the parts of (4,1,1,1) is:

(1+1+1+4) = 7

(1)*(1+1+4) = 6

(4)*(1+1+1) = 12

(1+1)*(1+4) = 10

(1)*(1)*(1+4) = 5

(1)*(4)*(1+1) = 8

(1)*(1)*(1)*(4) = 4

These are all distinct, so (4,1,1,1) is a spanning product-sum knapsack partition of 7.

A complete list of all products of sums covering the parts of (5,3,1,1) is:

(1+1+3+5) = 10

(1)*(1+3+5) = 9

(3)*(1+1+5) = 21

(5)*(1+1+3) = 25

(1+1)*(3+5) = 16

(1+3)*(1+5) = 24

(1)*(1)*(3+5) = 8

(1)*(3)*(1+5) = 18

(1)*(5)*(1+3) = 20

(3)*(5)*(1+1) = 30

(1)*(1)*(3)*(5) = 15

These are all distinct, so (5,3,1,1) is a spanning product-sum knapsack partition of 10.

An example of a spanning sum-product knapsack partition that is not a spanning product-sum knapsack partition is (5,4,3,2).

MATHEMATICA

sps[{}]:={{}};

sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

rsuks[n_]:=Select[IntegerPartitions[n], Function[q, UnsameQ@@Apply[Times, Apply[Plus, mps[q], {2}], {1}]]];

Table[Length[rsuks[n]], {n, 10}]

CROSSREFS

Cf. A001970, A066739, A108917, A275972, A292886, A316313, A318949, A319318, A319320, A319910, A319913.

Cf. A267597, A320052, A320053, A320055, A320056, A320057, A320058.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Oct 04 2018

STATUS

approved

A320055

Heinz numbers of sum-product knapsack partitions.

+10
7

1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 21, 23, 25, 29, 31, 33, 35, 37, 39, 41, 43, 47, 49, 51, 53, 55, 57, 59, 61, 65, 67, 69, 71, 73, 77, 79, 83, 85, 87, 89, 91, 93, 95, 97, 101, 103, 107, 109, 111, 113, 115, 119, 121, 123, 127, 129, 131, 133, 137, 139, 141, 143

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A sum-product knapsack partition is a finite multiset m of positive integers such that every sum of products of parts of any multiset partition of any submultiset of m is distinct.

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

Differs from A320056 in having 2, 845, ... and lacking 245, 455, 847, ....

LINKS

Table of n, a(n) for n=1..62.

EXAMPLE

A complete list of sums of products of multiset partitions of submultisets of the partition (6,6,3) is:

0 = 0

(3) = 3

(6) = 6

(3*6) = 18

(6*6) = 36

(3*6*6) = 108

(3)+(6) = 9

(3)+(6*6) = 39

(6)+(6) = 12

(6)+(3*6) = 24

(3)+(6)+(6) = 15

These are all distinct, and the Heinz number of (6,6,3) is 845, so 845 belongs to the sequence.

MATHEMATICA

multWt[n_]:=If[n==1, 1, Times@@Cases[FactorInteger[n], {p_, k_}:>PrimePi[p]^k]];

facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];

Select[Range[100], UnsameQ@@Table[Plus@@multWt/@f, {f, Join@@facs/@Divisors[#]}]&]

CROSSREFS

Cf. A001970, A056239, A066739, A108917, A112798, A292886, A299702, A301899, A318949, A319318, A319913.

Cf. A267597, A320052, A320053, A320054, A320056, A320057, A320058.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Oct 04 2018

STATUS

approved

A320056

Heinz numbers of product-sum knapsack partitions.

+10
7

1, 3, 5, 7, 11, 13, 15, 17, 19, 21, 23, 25, 29, 31, 33, 35, 37, 39, 41, 43, 47, 49, 51, 53, 55, 57, 59, 61, 65, 67, 69, 71, 73, 77, 79, 83, 85, 87, 89, 91, 93, 95, 97, 101, 103, 107, 109, 111, 113, 115, 119, 121, 123, 127, 129, 131, 133, 137, 139, 141, 143

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A product-sum knapsack partition is a finite multiset m of positive integers such that every product of sums of parts of a multiset partition of any submultiset of m is distinct.

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

Differs from A320055 in having 245, 455, 847, ... and lacking 2, 845, ....

LINKS

Table of n, a(n) for n=1..61.

EXAMPLE

A complete list of products of sums of multiset partitions of submultisets of the partition (5,5,4) is:

() = 1

(4) = 4

(5) = 5

(4+5) = 9

(5+5) = 10

(4+5+5) = 14

(4)*(5) = 20

(4)*(5+5) = 40

(5)*(5) = 25

(5)*(4+5) = 45

(4)*(5)*(5) = 100

These are all distinct, and the Heinz number of (5,5,4) is 847, so 847 belongs to the sequence.

MATHEMATICA

heinzWt[n_]:=If[n==1, 0, Total[Cases[FactorInteger[n], {p_, k_}:>k*PrimePi[p]]]];

facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];

Select[Range[100], UnsameQ@@Table[Times@@heinzWt/@f, {f, Join@@facs/@Divisors[#]}]&]

CROSSREFS

Cf. A001970, A056239, A066739, A108917, A112798, A292886, A299702, A301899, A318949, A319318, A319913.

Cf. A267597, A320052, A320053, A320054, A320055, A320057, A320058.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Oct 04 2018

STATUS

approved

A320057

Heinz numbers of spanning sum-product knapsack partitions.

+10
7

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, 50, 51, 53, 55, 57, 58, 59, 61, 62, 65, 67, 69, 71, 73, 74, 75, 77, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 98, 101, 103, 105

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A spanning sum-product knapsack partition is a finite multiset m of positive integers such that every sum of products of parts of any multiset partition of m is distinct.

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

Differs from A320058 in having 1155, 1625, 1815, 1875, 1911, ... and lacking 20, 28, 42, 44, 52, ...

LINKS

Table of n, a(n) for n=1..66.

EXAMPLE

The sequence of all spanning sum-product knapsack partitions begins: (), (1), (2), (1,1), (3), (2,1), (4), (1,1,1), (3,1), (5), (6), (4,1), (3,2), (7), (8), (4,2), (5,1), (9), (3,3), (6,1).

A complete list of sums of products of multiset partitions of the partition (5,4,3,2) is:

(2*3*4*5) = 120

(2)+(3*4*5) = 62

(3)+(2*4*5) = 43

(4)+(2*3*5) = 34

(5)+(2*3*4) = 29

(2*3)+(4*5) = 26

(2*4)+(3*5) = 23

(2*5)+(3*4) = 22

(2)+(3)+(4*5) = 25

(2)+(4)+(3*5) = 21

(2)+(5)+(3*4) = 19

(3)+(4)+(2*5) = 17

(3)+(5)+(2*4) = 16

(4)+(5)+(2*3) = 15

(2)+(3)+(4)+(5) = 14

These are all distinct, and the Heinz number of (5,4,3,2) is 1155, so 1155 belongs to the sequence.

MATHEMATICA

multWt[n_]:=If[n==1, 1, Times@@Cases[FactorInteger[n], {p_, k_}:>PrimePi[p]^k]];

facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];

Select[Range[100], UnsameQ@@Table[Plus@@multWt/@f, {f, facs[#]}]&]

CROSSREFS

Cf. A001970, A056239, A066739, A108917, A112798, A292886, A299702, A301899, A318949, A319318, A319913.

Cf. A267597, A320052, A320053, A320054, A320055, A320056, A320058.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Oct 04 2018

STATUS

approved

A320058

Heinz numbers of spanning product-sum knapsack partitions.

+10
7

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 25, 26, 28, 29, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82, 83, 85, 86, 87

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

A spanning product-sum knapsack partition is a finite multiset m of positive integers such that every product of sums of parts of any multiset partition of m is distinct.

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

Differs from A320057 in having 20, 28, 42, 44, 52, ... and lacking 1155, 1625, 1815, 1875, 1911, ....

LINKS

Table of n, a(n) for n=1..67.

EXAMPLE

The sequence of all spanning product-sum knapsack partitions begins: (), (1), (2), (1,1), (3), (2,1), (4), (1,1,1), (3,1), (5), (6), (4,1), (3,2), (7), (8), (3,1,1), (4,2), (5,1), (9), (3,3), (6,1), (4,1,1).

A complete list of products of sums of multiset partitions of the partition (3,1,1) is:

(1+1+3) = 5

(1)*(1+3) = 4

(3)*(1+1) = 6

(1)*(1)*(3) = 3

These are all distinct, and the Heinz number of (3,1,1) is 20, so 20 belongs to the sequence.

MATHEMATICA

heinzWt[n_]:=If[n==1, 0, Total[Cases[FactorInteger[n], {p_, k_}:>k*PrimePi[p]]]];

facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];

Select[Range[100], UnsameQ@@Table[Times@@heinzWt/@f, {f, facs[#]}]&]

CROSSREFS

Cf. A001970, A056239, A066739, A108917, A112798, A292886, A299702, A301899, A318949, A319318, A319913.

Cf. A267597, A320052, A320053, A320054, A320055, A320056, A320057.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Oct 04 2018

STATUS

approved