A275972 -id:A275972 - cp's OEIS frontend

A364906 Number of ways to write A056239(n) as a nonnegative linear combination of the multiset of prime indices of n.

1, 1, 1, 3, 1, 2, 1, 10, 3, 2, 1, 9, 1, 2, 1, 35, 1, 6, 1, 9, 2, 2, 1, 34, 3, 2, 10, 10, 1, 7, 1, 126, 1, 2, 1, 30, 1, 2, 2, 39, 1, 6, 1, 11, 3, 2, 1, 130, 3, 6, 1, 12, 1, 20, 1, 46, 2, 2, 1, 31, 1, 2, 9, 462, 2, 7, 1, 13, 1, 6, 1, 120, 1, 2, 4, 14, 1, 7, 1

Offset: 1

Gus Wiseman, Aug 22 2023

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
A way of writing n as a (nonnegative) linear combination of a finite sequence y is any sequence of pairs (k_i,y_i) such that k_i >= 0 and Sum k_i*y_i = n. For example, the pairs ((3,1),(1,1),(1,1),(0,2)) are a way of writing 5 as a linear combination of (1,1,1,2), namely 5 = 3*1 + 1*1 + 1*1 + 0*2. Of course, there are A000041(n) ways to write n as a linear combination of (1..n).
Conjecture: Positions of 1's are numbers whose distinct divisors all have different GCDs of prime indices, listed by A319319, counted by A319318.

			The a(2) = 1 through a(10) = 2 ways:
  1*1  1*2  0*1+2*1  1*3  1*1+1*2  1*4  0*1+0*1+3*1  0*2+2*2  1*1+1*3
            1*1+1*1       3*1+0*2       0*1+1*1+2*1  1*2+1*2  4*1+0*3
            2*1+0*1                     0*1+2*1+1*1  2*2+0*2
                                        0*1+3*1+0*1
                                        1*1+0*1+2*1
                                        1*1+1*1+1*1
                                        1*1+2*1+0*1
                                        2*1+0*1+1*1
                                        2*1+1*1+0*1
                                        3*1+0*1+0*1

The case with no zero coefficients is A000012.
Positions of 1's appear to be A319319.
A001222 counts prime indices, distinct A001221.
A112798 lists prime indices, sum A056239.
A364910 counts nonnegative linear combinations of strict partitions.
Cf. A116861, A275972, A320340, A364350, A364839, A364912, A364914, A364916, A365002, A365003, A365004.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[combs[Total[prix[n]],prix[n]]],{n,100}]

A365071 Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.

Original entry on oeis.org

0, 1, 2, 3, 6, 9, 15, 23, 40, 55, 94, 132, 210, 298, 476, 644, 1038, 1406, 2149, 2965, 4584, 6077, 9426, 12648, 19067, 25739, 38958, 51514, 78459, 104265, 155436, 208329, 312791, 411886, 620780, 823785, 1224414, 1631815, 2437015, 3217077, 4822991

Offset: 0

Gus Wiseman, Aug 26 2023

nonn

The complement is counted by A365069. The binary version is A364755, complement A364756. For re-usable parts we have A288728, complement A365070.

			The subset {1,3,4,6} has 4 = 1 + 3 so is not counted under a(6).
The subset {2,3,4,5,6} has 6 = 2 + 4 and 4 = 1 + 3 so is not counted under a(6).
The a(0) = 0 through a(6) = 15 subsets:
  .  {1}  {2}    {3}    {4}      {5}      {6}
          {1,2}  {1,3}  {1,4}    {1,5}    {1,6}
                 {2,3}  {2,4}    {2,5}    {2,6}
                        {3,4}    {3,5}    {3,6}
                        {1,2,4}  {4,5}    {4,6}
                        {2,3,4}  {1,2,5}  {5,6}
                                 {1,3,5}  {1,2,6}
                                 {2,4,5}  {1,3,6}
                                 {3,4,5}  {1,4,6}
                                          {2,3,6}
                                          {2,5,6}
                                          {3,4,6}
                                          {3,5,6}
                                          {4,5,6}
                                          {3,4,5,6}

Andrew Howroyd, Table of n, a(n) for n = 0..85
Steven R. Finch, Monoids of natural numbers, March 17, 2009.

First differences of A151897.
The version with re-usable parts is A288728 first differences of A007865.
The binary version is A364755, first differences of A085489.
The binary complement is A364756, first differences of A088809.
The complement is counted by A365069, first differences of A364534.
The complement w/ re-usable parts is A365070, first differences of A093971.
A108917 counts knapsack partitions, strict A275972.
A124506 counts combination-free subsets, differences of A326083.
A364350 counts combination-free strict partitions, complement A364839.
A365046 counts combination-full subsets, differences of A364914.
Partitions: A236912, A237113, A237668, A364532, A364272, A364349, A364913.
Cf. A050291, A095944, A103580, A324741, A326080, A326117, A341507, A364533.

Table[Length[Select[Subsets[Range[n]], MemberQ[#,n]&&Intersection[#, Total/@Subsets[#,{2,Length[#]}]]=={}&]], {n,0,10}]

a(n) + A365069(n) = 2^(n-1).

First differences of A151897.

a(14) onwards added (using A151897) by Andrew Howroyd, Jan 13 2024

A201052 a(n) is the maximal number c of integers that can be chosen from {1,2,...,n} so that all 2^c subsets have distinct sums.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Nov 26 2011

In the count 2^c of the cardinality of subsets of a set with cardinality c, the empty set - with sum 0 - is included; 2^c is just the row sum of the c-th row in the Pascal triangle.
Conjecture (confirmed through k=7): a(n)=k for all n in the interval A005318(k) <= n < A005318(k+1). - Jon E. Schoenfield, Nov 28 2013 [Note: This conjecture is false; see A276661 for a counterexample (n=34808712605260918463) in which n is in the interval A005318(66) <= n < A005318(67), yet a(n)=67, not 66. - Jon E. Schoenfield, Nov 05 2016]
A276661 is the main entry for the distinct subset sums problem. - N. J. A. Sloane, Apr 24 2024

			Numbers n and an example of a subset of {1..n} exhibiting the maximum cardinality c=a(n):
1, {1}
2, {1, 2}
3, {1, 2}
4, {1, 2, 4}
5, {1, 2, 4}
6, {1, 2, 4}
7, {3, 5, 6, 7}
8, {1, 2, 4, 8}
9, {1, 2, 4, 8}
10, {1, 2, 4, 8}
11, {1, 2, 4, 8}
12, {1, 2, 4, 8}
13, {3, 6, 11, 12, 13}
14, {1, 6, 10, 12, 14}
15, {1, 6, 10, 12, 14}
16, {1, 2, 4, 8, 16}
17, {1, 2, 4, 8, 16}
18, {1, 2, 4, 8, 16}
For examples of maximum-cardinality subsets at values of n where a(n) > a(n-1), see A096858. - _Jon E. Schoenfield_, Nov 28 2013

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..220 (terms 1..120 from Jon E. Schoenfield)
T. Khovanova, The weight puzzle sequence, SeqFan Mailing list Aug 24 2010
T. Khovanova et al., The weights puzzle
Jon E. Schoenfield, Excel/VBA macro

Cf. A005318, A096858, A275972, A276661.

# is any subset of L uniquely determined by its total weight?
iswts := proc(L)
    local wtset,s,c,subL,thiswt ;
    # the weight sums are to be unique, so sufficient to remember the set
    wtset := {} ;
    # loop over all subsets of weights generated by L
    for s from 1 to nops(L) do
        c := combinat[choose](L,s) ;
        for subL in c do
            # compute the weight sum in this subset
            thiswt := add(i,i=subL) ;
            # if this weight sum already appeared: not a candidate
            if thiswt in wtset then
                return false;
            else
                wtset := wtset union {thiswt} ;
            end if;
        end do:
    end do:
    # All different subset weights were different: success
    return true;
end proc:
# main sequence: given grams 1 to n, determine a subset L
# such that each subset of this subset has a different sum.
wts := proc(n)
    local s,c,L ;
    # select sizes from n (largest size first) down to 1,
    # so the largest is detected first as required by the puzzle.
    for s from n to 1 by -1 do
        # all combinations of subsets of s different grams
        c := combinat[choose]([seq(i,i=1..n)],s) ;
        for L in c do
            # check if any of these meets the requir, print if yes
            # and return
            if iswts(L) then
                print(n,L) ;
                return nops(L) ;
            end if;
        end do:
    end do:
    print(n,"-") ;
end proc:
# loop for weights with maximum n
for n from 1 do
    wts(n) ;
end do: # R. J. Mathar, Aug 24 2010

More terms from Alois P. Heinz, Nov 27 2011

More terms from Jon E. Schoenfield, Nov 28 2013

A301934 Number of positive subset-sum trees of weight n.

Original entry on oeis.org

1, 3, 14, 85, 586, 4331, 33545, 268521, 2204249

Offset: 1

Gus Wiseman, Mar 28 2018

A positive subset-sum tree with root x is either the symbol x itself, or is obtained by first choosing a positive subset-sum x <= (y_1,...,y_k) with k > 1 and then choosing a positive subset-sum tree with root y_i for each i = 1...k. The weight is the sum of the leaves. We write positive subset-sum trees in the form rootsum(branch,...,branch). For example, 4(1(1,3),2,2(1,1)) is a positive subset-sum tree with composite 4(1,1,1,2,3) and weight 8.

			The a(3) = 14 positive subset-sum trees:
3           3(1,2)       3(1,1,1)     3(1,2(1,1))
2(1,2)      2(1,1,1)     2(1,1(1,1))  2(1(1,1),1)  2(1,2(1,1))
1(1,2)      1(1,1,1)     1(1,1(1,1))  1(1(1,1),1)  1(1,2(1,1))

Cf. A000108, A000712, A108917, A122768, A262671, A262673, A275972, A276024, A284640, A299701, A301854, A301855, A301856, A301935.

A319319 Heinz numbers of integer partitions such that every distinct submultiset has a different GCD.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 33, 35, 37, 41, 43, 47, 51, 53, 55, 59, 61, 67, 69, 71, 73, 77, 79, 83, 85, 89, 91, 93, 95, 97, 101, 103, 107, 109, 113, 119, 123, 127, 131, 137, 139, 141, 143, 145, 149, 151, 155, 157, 161, 163, 167, 173, 177

Offset: 1

Gus Wiseman, Sep 17 2018

nonn

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

First differs from A304713 (Heinz numbers of pairwise indivisible partitions) at A304713(58) = 165, which is absent from this sequence because its prime indices are {2,3,5} and GCD(2,3) = GCD(2,3,5) = 1. The first term with more than two prime factors is 17719, which has prime indices {6,10,15}. The first term with more than two prime factors that is absent from A318716 is 296851, which has prime indices {12,20,30}.

			The sequence of partitions whose Heinz numbers are in the sequence begins: (), (1), (2), (3), (4), (5), (6), (3,2), (7), (8), (9), (10), (11), (5,2), (4,3), (12), (13), (14), (15), (7,2), (16), (5,3).

Cf. A056239, A108917, A122768, A275972, A299702, A301899, A301900, A304713, A316313, A319315, A319318, A319327.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],UnsameQ@@GCD@@@Union[Subsets[primeMS[#]]]&]

A323087 Number of strict factorizations of n into factors > 1 such that no factor is a power of any other factor.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 2, 2, 2, 2, 5, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 1, 2, 5, 1, 3, 2, 5, 1, 8, 1, 2, 3, 3, 2, 5, 1, 5, 1, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Jan 04 2019

nonn

			The a(60) = 9 factorizations:
  (2*3*10), (2*5*6), (3*4*5),
  (2*30), (3*20), (4*15), (5*12), (6*10),
  (60).

Cf. A001597, A007916, A025147, A045778, A052410, A087897, A275972, A305150, A323054, A323086, A323090, A323091.

strfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strfacs[n/d],Min@@#>d&]],{d,Rest[Divisors[n]]}]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[strfacs[n],stableQ[#,IntegerQ[Log[#1,#2]]&]&]],{n,100}]

A326035 Number of uniform knapsack partitions of n.

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 6, 6, 9, 10, 12, 12, 17, 16, 20, 25, 27, 29, 35, 39, 44, 57, 53, 66, 75, 84, 84, 114, 112, 131, 133, 162, 167, 209, 192, 242, 250, 289, 279, 363, 348, 417, 404, 502, 487, 608, 557, 706, 682, 835, 773, 1004, 922, 1149, 1059, 1344, 1257, 1595

Offset: 0

Gus Wiseman, Jun 04 2019

nonn

An integer partition is uniform if all parts appear with the same multiplicity, and knapsack if every distinct submultiset has a different sum.

			The a(1) = 1 through a(8) = 9 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (32)     (33)      (43)       (44)
             (111)  (31)    (41)     (42)      (52)       (53)
                    (1111)  (11111)  (51)      (61)       (62)
                                     (222)     (421)      (71)
                                     (111111)  (1111111)  (521)
                                                          (2222)
                                                          (3311)
                                                          (11111111)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..650

Cf. A002033, A047966, A072774, A108917, A275972, A276024, A299702.

Cf. A325592, A325858, A326015, A326016, A326017, A326036, A326037.

sums[ptn_]:=sums[ptn]=If[Length[ptn]==1,ptn,Union@@(Join[sums[#],sums[#]+Total[ptn]-Total[#]]&/@Union[Table[Delete[ptn,i],{i,Length[ptn]}]])];
ks[n_]:=Select[IntegerPartitions[n],Length[sums[Sort[#]]]==Times@@(Length/@Split[#]+1)-1&];
Table[Length[Select[ks[n],SameQ@@Length/@Split[#]&]],{n,30}]

A344412 Number of knapsack partitions of n with largest part 7.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 6, 7, 1, 6, 5, 8, 7, 10, 8, 8, 9, 11, 8, 13, 11, 13, 5, 14, 8, 13, 10, 17, 12, 8, 10, 14, 13, 14, 12, 18, 3, 15, 11, 15, 14, 17, 12, 8, 12, 15, 13, 20, 12, 14, 5, 17, 15, 17, 10, 18, 14, 9, 13, 18, 13, 15, 15, 18, 5, 18, 11

Offset: 0

Fausto A. C. Cariboni, May 17 2021

nonn

An integer partition is knapsack if every distinct submultiset has a different sum.

I computed terms a(n) for n = 0..25000 and the subsequence a(72)-a(491) of length 420 is repeated continuously.

			The initial nonzero values count the following partitions:
   7: (7)
   8: (7,1)
   9: (7,1,1), (7,2)
  10: (7,1,1,1), (7,2,1), (7,3)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..1000

Cf. A108917, A275972, A326017, A326034, A343321, A344310, A344340.

A294150 Number of knapsack partitions of n that are also knapsack factorizations.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 4, 6, 8, 10, 12, 13, 20, 20, 29, 30, 41, 41, 56, 53, 81, 75

Offset: 1

Gus Wiseman, Oct 23 2017

a(n) is the number of finite multisets of positive integers summing to n such that every distinct submultiset has a different sum, and also every distinct submultiset has a different product.

			The a(12) = 13 partitions are:
(12),
(10 2), (9 3), (8 4), (7 5), (6 6),
(8 2 2), (7 3 2), (5 5 2), (5 4 3), (4 4 4),
(3 3 3 3),
(2 2 2 2 2 2).

R. Ehrenborg and M. Readdy, The Mobius function of partitions with restricted block sizes, Advances in Applied Mathematics, Volume 39, Issue 3, September 2007, Pages 283-292.

Cf. A000041, A001055, A108917, A275972, A292886, A293627.

nn=22;
dubQ[y_]:=And[UnsameQ@@Times@@@Union[Rest@Subsets[y]],UnsameQ@@Plus@@@Union[Rest@Subsets[y]]];
Table[Length@Select[IntegerPartitions[n],dubQ],{n,nn}]

A304796 Number of special sums of integer partitions of n.

Original entry on oeis.org

1, 2, 5, 10, 18, 32, 51, 82, 122, 188, 262, 392, 529, 750, 997, 1404, 1784, 2452, 3123, 4164, 5239, 6916, 8499, 11112, 13693, 17482, 21257, 27162, 32581, 41114, 49606, 61418, 73474, 91086, 107780, 132874, 157359, 191026, 225159, 274110, 320691, 386722, 453875

Offset: 0

Gus Wiseman, May 18 2018

nonn

A special sum of an integer partition y is a number n >= 0 such that exactly one submultiset of y sums to n.

			The a(4) = 18 special positive subset-sums:
0<=(4), 4<=(4),
0<=(22), 2<=(22), 4<=(22),
0<=(31), 1<=(31), 3<=(31), 4<=(31),
0<=(211), 1<=(211), 3<=(211), 4<=(211),
0<=(1111), 1<=(1111), 2<=(1111), 3<=(1111), 4<=(1111).

Cf. A000712, A108917, A122768, A275972, A276024, A284640, A299701, A299702, A299729, A301829, A301830, A301854.

uqsubs[y_]:=Join@@Select[GatherBy[Union[Subsets[y]],Total],Length[#]===1&];
Table[Total[Length/@uqsubs/@IntegerPartitions[n]],{n,25}]

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

More terms from Alois P. Heinz, May 18 2018

a(36)-a(42) from Chai Wah Wu, Sep 26 2023

cp's OEIS Frontend

A364906 Number of ways to write A056239(n) as a nonnegative linear combination of the multiset of prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A365071 Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A201052 a(n) is the maximal number c of integers that can be chosen from {1,2,...,n} so that all 2^c subsets have distinct sums.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A301934 Number of positive subset-sum trees of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A319319 Heinz numbers of integer partitions such that every distinct submultiset has a different GCD.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A323087 Number of strict factorizations of n into factors > 1 such that no factor is a power of any other factor.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A326035 Number of uniform knapsack partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A344412 Number of knapsack partitions of n with largest part 7.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A294150 Number of knapsack partitions of n that are also knapsack factorizations.

Views

Author

Keywords

Comments