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[#]]]!={}&]
A364915
Number of integer partitions of n such that no distinct part can be written as a nonnegative linear combination of other distinct parts.
Original entry on oeis.org
1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 12, 10, 16, 16, 19, 21, 29, 25, 37, 35, 44, 46, 60, 55, 75, 71, 90, 90, 114, 110, 140, 138, 167, 163, 217, 201, 248, 241, 298, 303, 359, 355, 425, 422, 520, 496, 594, 603, 715, 706, 834, 826, 968, 972, 1153, 1147, 1334, 1315, 1530
Offset: 0
The a(1) = 1 through a(10) = 8 partitions (A=10):
1 2 3 4 5 6 7 8 9 A
11 111 22 32 33 43 44 54 55
1111 11111 222 52 53 72 64
111111 322 332 333 73
1111111 2222 522 433
11111111 3222 3322
111111111 22222
1111111111
The partition (5,4,3) has no part that can be written as a nonnegative linear combination of the others, so is counted under a(12).
The partition (6,4,3,2) has 6=4+2, or 6=3+3, or 6=2+2+2, or 4=2+2, so is not counted under a(15).
For subsets instead of partitions we have
A326083, complement
A364914.
A007865 counts binary sum-free sets w/ re-usable parts, complement
A093971.
A364912 counts linear combinations of partitions of k.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[IntegerPartitions[n], Function[ptn,!Or@@Table[combs[ptn[[k]],Delete[ptn,k]]!={}, {k,Length[ptn]}]]@*Union]], {n,0,15}]
-
from sympy.utilities.iterables import partitions
def A364915(n):
if n <= 1: return 1
alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 1
for p in partitions(n,k=n-1):
s = set(p)
if not any(set(t).issubset(s-{q}) for q in s for t in alist[q]):
c += 1
return c # Chai Wah Wu, Sep 23 2023
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
A366320
Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} without a subset summing to k.
Original entry on oeis.org
1, 2, 2, 3, 4, 4, 3, 6, 6, 7, 8, 8, 6, 6, 9, 11, 11, 14, 14, 15, 16, 16, 12, 12, 9, 17, 17, 20, 20, 24, 27, 27, 30, 30, 31, 32, 32, 24, 24, 18, 17, 26, 31, 29, 35, 36, 43, 47, 50, 51, 56, 59, 59, 62, 62, 63
Offset: 1
Triangle begins:
1
2 2 3
4 4 3 6 6 7
8 8 6 6 9 11 11 14 14 15
16 16 12 12 9 17 17 20 20 24 27 27 30 30 31
32 32 24 24 18 17 26 31 29 35 36 43 47 50 51 56 59 59 62 62 63
Row n = 3 counts the following subsets:
{} {} {} {} {} {}
{2} {1} {1} {1} {1} {1}
{3} {3} {2} {2} {2} {2}
{2,3} {1,3} {3} {3} {3}
{1,2} {1,2} {1,2}
{2,3} {1,3} {1,3}
{2,3}
The complement is counted by
A365381.
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
-
Table[Length[Select[Subsets[Range[n]],FreeQ[Total/@Subsets[#],k]&]],{n,8},{k,n*(n+1)/2}]
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
A365312
Number of strict integer partitions with sum <= n that cannot be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 0, 0, 1, 1, 3, 2, 6, 4, 8, 7, 16, 6, 24, 17, 24, 20, 46, 22, 62, 31, 63, 57, 106, 35, 122, 90, 137, 88, 212, 74, 262, 134, 267, 206, 345, 121, 476, 294, 484, 232, 698, 242, 837, 389, 763, 571, 1185, 318, 1327, 634, 1392, 727, 1927, 640, 2056, 827, 2233, 1328
Offset: 0
The strict partition (7,3,2) has 19 = 1*7 + 2*3 + 3*2 so is not counted under a(19).
The strict partition (9,6,3) cannot be linearly combined to obtain 19, so is counted under a(19).
The a(0) = 0 through a(11) = 16 strict partitions:
. . . (2) (3) (2) (4) (2) (3) (2) (3) (2)
(3) (5) (3) (5) (4) (4) (3)
(4) (4) (6) (5) (6) (4)
(5) (7) (6) (7) (5)
(6) (7) (8) (6)
(4,2) (8) (9) (7)
(4,2) (6,3) (8)
(6,2) (9)
(10)
(4,2)
(5,4)
(6,2)
(6,3)
(6,4)
(7,3)
(8,2)
The complement for positive coefficients is counted by
A088314.
For positive coefficients we have
A088528.
The complement is counted by
A365311.
A364350 counts combination-free strict partitions, non-strict
A364915.
A364839 counts combination-full strict partitions, non-strict
A364913.
Cf.
A093971,
A237113,
A237668,
A326080,
A363225,
A364272,
A364534,
A364914,
A365043,
A365314,
A365320.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Select[Join@@Array[IntegerPartitions,n], UnsameQ@@#&],combs[n,#]=={}&]],{n,0,10}]
-
from math import isqrt
from sympy.utilities.iterables import partitions
def A365312(n):
a = {tuple(sorted(set(p))) for p in partitions(n)}
return sum(1 for m in range(1,n+1) for b in partitions(m,m=isqrt(1+(n<<3))>>1) if max(b.values()) == 1 and not any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023
A364348
Numbers with two possibly equal divisors prime(a) and prime(b) such that prime(a+b) is also a divisor.
Original entry on oeis.org
6, 12, 18, 21, 24, 30, 36, 42, 48, 54, 60, 63, 65, 66, 70, 72, 78, 84, 90, 96, 102, 105, 108, 114, 120, 126, 130, 132, 133, 138, 140, 144, 147, 150, 154, 156, 162, 165, 168, 174, 180, 186, 189, 192, 195, 198, 204, 210, 216, 222, 228, 231, 234, 240, 246, 252
Offset: 1
We have 6 because prime(1) and prime(1) are both divisors of 6, and prime(1+1) is also.
The terms together with their prime indices begin:
6: {1,2}
12: {1,1,2}
18: {1,2,2}
21: {2,4}
24: {1,1,1,2}
30: {1,2,3}
36: {1,1,2,2}
42: {1,2,4}
48: {1,1,1,1,2}
54: {1,2,2,2}
60: {1,1,2,3}
63: {2,2,4}
65: {3,6}
66: {1,2,5}
70: {1,3,4}
72: {1,1,1,2,2}
-
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Intersection[prix[#],Total/@Tuples[prix[#],2]]!={}&]
Comments