A367216
Number of subsets of {1..n} whose cardinality is equal to the sum of some subset.
Original entry on oeis.org
1, 2, 3, 5, 10, 20, 40, 82, 169, 348, 716, 1471, 3016, 6171, 12605, 25710, 52370, 106539, 216470, 439310, 890550, 1803415, 3648557, 7375141, 14896184, 30065129, 60639954, 122231740, 246239551, 495790161, 997747182, 2006969629, 4035274292, 8110185100, 16293958314, 32724456982
Offset: 0
The a(0) = 1 through a(4) = 10 subsets:
{} {} {} {} {}
{1} {1} {1} {1}
{1,2} {1,2} {1,2}
{2,3} {2,3}
{1,2,3} {2,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A240855 counts strict partitions whose length is a part, complement
A240861.
Triangles:
A365541 counts sets containing two distinct elements summing to k.
-
Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#], Length[#]]&]], {n,0,10}]
A367217
Number of subsets of {1..n} whose cardinality is not equal to the sum of any subset.
Original entry on oeis.org
0, 0, 1, 3, 6, 12, 24, 46, 87, 164, 308, 577, 1080, 2021, 3779, 7058, 13166, 24533, 45674, 84978, 158026, 293737, 545747, 1013467, 1881032, 3489303, 6468910, 11985988, 22195905, 41080751, 75994642, 140514019, 259693004, 479749492, 885910870, 1635281386
Offset: 0
The a(2) = 1 through a(5) = 12 subsets:
{2} {2} {2} {2}
{3} {3} {3}
{1,3} {4} {4}
{1,3} {5}
{1,4} {1,3}
{3,4} {1,4}
{1,5}
{3,4}
{3,5}
{4,5}
{1,4,5}
{2,4,5}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A229816 counts partitions whose length is not a part, complement
A002865.
A124506 appears to count combination-free subsets, differences of
A326083.
Triangles:
A046663 counts partitions of n without a subset-sum k, strict
A365663.
A365541 counts sets containing two distinct elements summing to k.
Cf.
A068911,
A103580,
A240861,
A288728,
A326080,
A326083,
A364346,
A364349,
A365046,
A365376,
A365377.
-
Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#], Length[#]]&]], {n,0,15}]
A367222
Number of subsets of {1..n} whose cardinality can be written as a nonnegative linear combination of the elements.
Original entry on oeis.org
1, 2, 3, 6, 12, 24, 49, 101, 207, 422, 859, 1747, 3548, 7194, 14565, 29452, 59496, 120086, 242185, 488035, 982672, 1977166, 3975508, 7989147, 16047464, 32221270, 64674453, 129775774, 260337978, 522124197, 1046911594, 2098709858, 4206361369, 8429033614, 16887728757, 33829251009, 67755866536, 135687781793, 271693909435
Offset: 0
The set {1,2,4} has 3 = (2)+(1) or 3 = (1+1+1) so is counted under a(4).
The a(0) = 1 through a(4) = 12 subsets:
{} {} {} {} {}
{1} {1} {1} {1}
{1,2} {1,2} {1,2}
{1,3} {1,3}
{2,3} {1,4}
{1,2,3} {2,3}
{2,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A124506 appears to count combination-free subsets, differences of
A326083.
Triangles:
A365541 counts subsets containing two distinct elements summing to k.
Cf.
A068911,
A088314,
A103580,
A116861,
A326080,
A364350,
A365073,
A365311,
A365376,
A365380,
A365544.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]], combs[Length[#], Union[#]]!={}&]], {n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A367222(n):
c, mlist = 1, []
for m in range(1,n+1):
t = set()
for p in partitions(m):
t.add(tuple(sorted(p.keys())))
mlist.append([set(d) for d in t])
for k in range(1,n+1):
for w in combinations(range(1,n+1),k):
ws = set(w)
for s in mlist[k-1]:
if s <= ws:
c += 1
break
return c # Chai Wah Wu, Nov 16 2023
A367223
Number of subsets of {1..n} whose cardinality cannot be written as a nonnegative linear combination of the elements.
Original entry on oeis.org
0, 0, 1, 2, 4, 8, 15, 27, 49, 90, 165, 301, 548, 998, 1819, 3316, 6040, 10986, 19959, 36253, 65904, 119986, 218796, 399461, 729752, 1333162, 2434411, 4441954, 8097478, 14746715, 26830230, 48773790, 88605927, 160900978, 292140427, 530487359, 963610200, 1751171679, 3183997509
Offset: 0
3 cannot be written as a nonnegative linear combination of 2, 4, and 5, so {2,4,5} is counted under a(6).
The a(2) = 1 through a(6) = 15 subsets:
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{4} {4} {4}
{3,4} {5} {5}
{3,4} {6}
{3,5} {3,4}
{4,5} {3,5}
{2,4,5} {3,6}
{4,5}
{4,6}
{5,6}
{2,4,5}
{2,4,6}
{2,5,6}
{4,5,6}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A124506 appears to count combination-free subsets, differences of
A326083.
Triangles:
A116861 counts positive linear combinations of strict partitions of k.
A364916 counts linear combinations of strict partitions of k.
Cf.
A068911,
A088314,
A103580,
A237667,
A326020,
A326080,
A364350,
A365073,
A365312,
A365377,
A365380.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]], combs[Length[#],Union[#]]=={}&]], {n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A367223(n):
c, mlist = 0, []
for m in range(1,n+1):
t = set()
for p in partitions(m):
t.add(tuple(sorted(p.keys())))
mlist.append([set(d) for d in t])
for k in range(1,n+1):
for w in combinations(range(1,n+1),k):
ws = set(w)
for s in mlist[k-1]:
if s <= ws:
break
else:
c += 1
return c # Chai Wah Wu, Nov 16 2023
A367226
Numbers m whose prime indices have a nonnegative linear combination equal to bigomega(m).
Original entry on oeis.org
1, 2, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 28, 30, 32, 33, 34, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 56, 57, 58, 60, 62, 64, 66, 68, 69, 70, 72, 74, 75, 76, 78, 80, 81, 82, 84, 86, 87, 88, 90, 92, 93, 94, 96, 98, 100, 102, 104
Offset: 1
The prime indices of 24 are {1,1,1,2} with (1+1+1+1) = 4 or (1+1)+(2) = 4 or (2+2) = 4, so 24 is in the sequence.
The terms together with their prime indices begin:
1: {}
2: {1}
4: {1,1}
6: {1,2}
8: {1,1,1}
9: {2,2}
10: {1,3}
12: {1,1,2}
14: {1,4}
15: {2,3}
16: {1,1,1,1}
18: {1,2,2}
20: {1,1,3}
21: {2,4}
22: {1,5}
24: {1,1,1,2}
26: {1,6}
28: {1,1,4}
30: {1,2,3}
32: {1,1,1,1,1}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A046663 counts partitions of n without a subset-sum k, strict
A365663.
-
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&]];
Select[Range[100], combs[PrimeOmega[#], Union[prix[#]]]!={}&]
A365376
Number of subsets of {1..n} with a subset summing to n.
Original entry on oeis.org
1, 1, 2, 5, 10, 23, 47, 102, 207, 440, 890, 1847, 3730, 7648, 15400, 31332, 62922, 127234, 255374, 514269, 1030809, 2071344, 4148707, 8321937, 16660755, 33384685, 66812942, 133789638, 267685113, 535784667, 1071878216, 2144762139, 4290261840, 8583175092, 17168208940, 34342860713
Offset: 0
The a(1) = 1 through a(4) = 10 sets:
{1} {2} {3} {4}
{1,2} {1,2} {1,3}
{1,3} {1,4}
{2,3} {2,4}
{1,2,3} {3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The case containing n is counted by
A131577.
The version with re-usable parts is
A365073.
The complement is counted by
A365377.
The complement w/ re-usable parts is
A365380.
A000124 counts distinct possible sums of subsets of {1..n}.
A124506 appears to count combination-free subsets, differences of
A326083.
A364350 counts combination-free strict partitions, complement
A364839.
-
Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],n]&]],{n,0,10}]
-
isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(1)));
a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ Michel Marcus, Sep 09 2023
-
from itertools import combinations, chain
from sympy.utilities.iterables import partitions
def A365376(n):
if n == 0: return 1
nset = set(range(1,n+1))
s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
if sum(a) >= n:
aset = set(a)
for p in s:
if p.issubset(aset):
c += 1
break
return c # Chai Wah Wu, Sep 09 2023
A364461
Positive integers such that if prime(a)*prime(b) is a divisor, prime(a+b) is not.
Original entry on oeis.org
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 76
Offset: 1
The prime indices of 198 are {1,2,2,5}, which is sum-free even though it is not knapsack (A299702, A299729), so 198 is in the sequence.
Subsets of this type are counted by
A085489, with re-usable parts
A007865.
Subsets not of this type are counted by
A093971, w/ re-usable parts
A088809.
Partitions of this type are counted by
A236912.
The complement allowing parts to be re-used is
A364348, counted by
A363225.
The non-binary version allowing re-used parts is counted by
A364350.
-
prix[n_]:=If[n==1,{}, Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Intersection[prix[#], Total/@Subsets[prix[#],{2}]]=={}&]
A364462
Positive integers having a divisor of the form prime(a)*prime(b) such that prime(a+b) is also a divisor.
Original entry on oeis.org
12, 24, 30, 36, 48, 60, 63, 70, 72, 84, 90, 96, 108, 120, 126, 132, 140, 144, 150, 154, 156, 165, 168, 180, 189, 192, 204, 210, 216, 228, 240, 252, 264, 270, 273, 276, 280, 286, 288, 300, 308, 312, 315, 324, 325, 330, 336, 348, 350, 360, 372, 378, 384, 390
Offset: 1
The terms together with their prime indices begin:
12: {1,1,2}
24: {1,1,1,2}
30: {1,2,3}
36: {1,1,2,2}
48: {1,1,1,1,2}
60: {1,1,2,3}
63: {2,2,4}
70: {1,3,4}
72: {1,1,1,2,2}
84: {1,1,2,4}
90: {1,2,2,3}
96: {1,1,1,1,1,2}
108: {1,1,2,2,2}
120: {1,1,1,2,3}
126: {1,2,2,4}
132: {1,1,2,5}
140: {1,1,3,4}
144: {1,1,1,1,2,2}
Subsets not of this type are counted by
A085489, w/ re-usable parts
A007865.
Subsets of this type are counted by
A088809, with re-usable parts
A093971.
Partitions not of this type are counted by
A236912.
Partitions of this type are counted by
A237113.
-
filter:= proc(n) local F, i,j,m;
F:= map(t -> `if`(t[2]>=2, numtheory:-pi(t[1])$2, numtheory:-pi(t[1])), ifactors(n)[2]);
for i from 1 to nops(F)-1 do for j from 1 to i-1 do
if member(F[i]+F[j],F) then return true fi
od od;
false
end proc:
select(filter, [$1..1000]); # Robert Israel, Aug 30 2023
-
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Intersection[prix[#], Total/@Subsets[prix[#],{2}]]!={}&]
A365043
Number of subsets of {1..n} whose greatest element can be written as a (strictly) positive linear combination of the others.
Original entry on oeis.org
0, 0, 1, 3, 7, 12, 21, 32, 49, 70, 99, 135, 185, 245, 323, 418, 541, 688, 873, 1094, 1368, 1693, 2092, 2564, 3138, 3810, 4620, 5565, 6696, 8012, 9569, 11381, 13518, 15980, 18872, 22194, 26075, 30535, 35711, 41627, 48473, 56290, 65283, 75533, 87298, 100631, 115911, 133219
Offset: 0
The subset S = {3,4,9} has 9 = 3*3 + 0*4, but this is not strictly positive, so S is not counted under a(9).
The subset S = {3,4,10} has 10 = 2*3 + 1*4, so S is counted under a(10).
The a(0) = 0 through a(5) = 12 subsets:
. . {1,2} {1,2} {1,2} {1,2}
{1,3} {1,3} {1,3}
{1,2,3} {1,4} {1,4}
{2,4} {1,5}
{1,2,3} {2,4}
{1,2,4} {1,2,3}
{1,3,4} {1,2,4}
{1,2,5}
{1,3,4}
{1,3,5}
{1,4,5}
{2,3,5}
A085489 and
A364755 count subsets with no sum of two distinct elements.
A088809 and
A364756 count subsets with some sum of two distinct elements.
A364350 counts combination-free strict partitions, complement
A364839.
A364913 counts combination-full partitions.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Rest[Subsets[Range[n]]],combp[Last[#],Union[Most[#]]]!={}&]],{n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A365043(n):
mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
return sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023
A364533
Number of strict integer partitions of n containing the sum of no pair of distinct parts. A variation of sum-free strict partitions.
Original entry on oeis.org
1, 1, 1, 2, 2, 3, 3, 5, 5, 8, 7, 11, 11, 15, 15, 21, 22, 28, 32, 38, 40, 51, 55, 65, 74, 83, 94, 111, 119, 136, 160, 174, 196, 222, 252, 273, 315, 341, 391, 425, 477, 518, 602, 636, 719, 782, 886, 944, 1073, 1140, 1302, 1380, 1553, 1651, 1888, 1995, 2224, 2370
Offset: 0
The a(1) = 1 through a(12) = 11 partitions (A..C = 10..12):
1 2 3 4 5 6 7 8 9 A B C
21 31 32 42 43 53 54 64 65 75
41 51 52 62 63 73 74 84
61 71 72 82 83 93
421 521 81 91 92 A2
432 631 A1 B1
531 721 542 543
621 632 732
641 741
731 831
821 921
Allowing re-used parts gives
A364346.
The linear combination-free version is
A364350.
The complement in strict partitions is
A364670, w/ re-used parts
A363226.
-
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&Intersection[#, Total/@Subsets[#,{2}]] == {}&]],{n,0,30}]
Comments