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[#]]]!={}&]
A367227
Numbers m whose prime indices have no nonnegative linear combination equal to bigomega(m).
Original entry on oeis.org
3, 5, 7, 11, 13, 17, 19, 23, 25, 27, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 63, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 99, 101, 103, 107, 109, 113, 115, 117, 119, 121, 127, 131, 133, 137, 139, 143, 145, 147, 149, 151, 153, 155, 157, 161, 163
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 not in the sequence.
The terms together with their prime indices begin:
3: {2} 43: {14} 85: {3,7}
5: {3} 47: {15} 89: {24}
7: {4} 49: {4,4} 91: {4,6}
11: {5} 53: {16} 95: {3,8}
13: {6} 55: {3,5} 97: {25}
17: {7} 59: {17} 99: {2,2,5}
19: {8} 61: {18} 101: {26}
23: {9} 63: {2,2,4} 103: {27}
25: {3,3} 65: {3,6} 107: {28}
27: {2,2,2} 67: {19} 109: {29}
29: {10} 71: {20} 113: {30}
31: {11} 73: {21} 115: {3,9}
35: {3,4} 77: {4,5} 117: {2,2,6}
37: {12} 79: {22} 119: {4,7}
41: {13} 83: {23} 121: {5,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
-------------------------------------------
A124506 appears to count combination-free subsets, differences of
A326083.
Cf.
A000720,
A046663,
A088314,
A106529,
A116861,
A236912,
A364345,
A364346,
A364347,
A364350,
A365073,
A365312.
-
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[#]]]=={}&]
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
A365311
Number of strict integer partitions with sum <= n that can be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 1, 2, 3, 5, 6, 11, 12, 20, 24, 35, 38, 63, 63, 92, 112, 148, 160, 230, 244, 339, 383, 478, 533, 726, 781, 978, 1123, 1394, 1526, 1960, 2112, 2630, 2945, 3518, 3964, 4856, 5261, 6307, 7099, 8464, 9258, 11140, 12155, 14419, 16093, 18589, 20565, 24342, 26597, 30948
Offset: 0
The strict partition (6,3) cannot be linearly combined to obtain 10, so is not counted under a(10).
The strict partition (4,2) has 6 = 1*4 + 1*2 so is counted under a(6), but (4,2) cannot be linearly combined to obtain 7 so is not counted under a(7).
The a(1) = 1 through a(7) = 12 strict partitions:
(1) (1) (1) (1) (1) (1) (1)
(2) (3) (2) (5) (2) (7)
(2,1) (4) (2,1) (3) (2,1)
(2,1) (3,1) (6) (3,1)
(3,1) (3,2) (2,1) (3,2)
(4,1) (3,1) (4,1)
(3,2) (4,3)
(4,1) (5,1)
(4,2) (5,2)
(5,1) (6,1)
(3,2,1) (3,2,1)
(4,2,1)
For positive coefficients we have
A088314.
The positive complement is counted by
A088528.
The version for subsets is
A365073.
The complement is counted by
A365312.
For non-strict partitions we have
A365379.
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,10}]
-
from math import isqrt
from sympy.utilities.iterables import partitions
def A365311(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 any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023
A365320
Number of pairs of distinct positive integers <= n that cannot be linearly combined with nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 0, 0, 0, 0, 2, 1, 7, 5, 12, 12, 27, 14, 42, 36, 47, 47, 83, 58, 109, 80, 116, 126, 172, 111, 195, 192, 219, 202, 294, 210, 342, 286, 354, 369, 409, 324, 509, 480, 523, 452, 640, 507, 711, 622, 675, 747, 865, 654, 916, 842, 964, 922, 1124, 940, 1147, 1029
Offset: 0
The pair p = (3,6) cannot be linearly combined to obtain 8 or 10, so p is counted under a(8) and a(10), but we have 9 = 1*3 + 1*6 or 9 = 3*3 + 0*6, so p not counted under a(9).
The a(5) = 2 through a(10) = 12 pairs:
(2,4) (4,5) (2,4) (3,6) (2,4) (3,6)
(3,4) (2,6) (3,7) (2,6) (3,8)
(3,5) (5,6) (2,8) (3,9)
(3,6) (5,7) (4,6) (4,7)
(4,5) (6,7) (4,7) (4,8)
(4,6) (4,8) (4,9)
(5,6) (5,6) (6,7)
(5,7) (6,8)
(5,8) (6,9)
(6,7) (7,8)
(6,8) (7,9)
(7,8) (8,9)
The case of positive coefficients is
A365321, for all subsets
A365322.
For all subsets instead of just pairs we have
A365380, complement
A365073.
A004526 counts partitions of length 2, shift right for strict.
A364350 counts combination-free strict partitions.
-
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],{2}],combs[n,#]=={}&]],{n,0,30}]
-
from itertools import count
from sympy import divisors
def A365320(n):
a = set()
for i in range(1,n+1):
if not n%i:
a.update(tuple(sorted((i,j))) for j in range(1,n+1) if j!=i)
else:
for j in count(0,i):
if j > n:
break
k = n-j
for d in divisors(k):
if d>=i:
break
a.add((d,i))
return (n*(n-1)>>1)-len(a) # Chai Wah Wu, Sep 13 2023
A088528
Let m = number of ways of partitioning n into parts using all the parts of a subset of {1, 2, ..., n-1} whose sum of all parts of a subset is less than n; a(n) gives number of different subsets of {1, 2, ..., n-1} whose m is 0.
Original entry on oeis.org
0, 0, 1, 1, 3, 3, 6, 6, 10, 12, 17, 18, 26, 30, 40, 44, 58, 66, 84, 95, 120, 135, 166, 186, 230, 257, 314, 350, 421, 476, 561, 626, 749, 831, 986, 1095, 1276, 1424, 1666, 1849, 2138, 2388, 2741, 3042, 3522, 3879, 4441, 4928, 5617, 6222, 7084, 7802, 8852, 9800
Offset: 1
a(5)=3 because there are three different subsets, {2}, {3} & {4}; a(6)=3 because there are three different subsets, {4}, {5} & {2,3}.
From _Gus Wiseman_, Sep 10 2023: (Start)
The set {3,5} is not counted under a(8) because 1*3 + 1*5 = 8, but it is counted under a(9) and a(10), and it is not counted under a(11) because 2*3 + 1*5 = 11.
The a(3) = 1 through a(11) = 17 subsets:
{2} {3} {2} {4} {2} {3} {2} {3} {2}
{3} {5} {3} {5} {4} {4} {3}
{4} {2,3} {4} {6} {5} {6} {4}
{5} {7} {6} {7} {5}
{6} {2,5} {7} {8} {6}
{2,4} {3,4} {8} {9} {7}
{2,4} {2,5} {8}
{2,6} {2,7} {9}
{3,4} {3,5} {10}
{3,5} {3,6} {2,4}
{4,5} {2,6}
{2,3,4} {2,8}
{3,6}
{3,7}
{4,5}
{4,6}
{2,3,5}
(End)
For sets with max < n instead of sum < n we have
A365045, nonempty
A070880.
For sets with max <= n we have
A365322.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Select[Subsets[Range[n]],0Gus Wiseman, Sep 12 2023 *)
A365322
Number of subsets of {1..n} that cannot be linearly combined using positive coefficients to obtain n.
Original entry on oeis.org
0, 1, 2, 5, 11, 26, 54, 116, 238, 490, 994, 2011, 4045, 8131, 16305, 32672, 65412, 130924, 261958, 524066, 1048301, 2096826, 4193904, 8388135, 16776641, 33553759, 67108053, 134216782, 268434324, 536869595, 1073740266, 2147481835, 4294965158, 8589932129
Offset: 0
The set {1,3} has 4 = 1 + 3 so is not counted under a(4). However, 3 cannot be written as a linear combination of {1,3} using all positive coefficients, so it is counted under a(3).
The a(1) = 1 through a(4) = 11 subsets:
{} {} {} {}
{1,2} {2} {3}
{1,3} {1,4}
{2,3} {2,3}
{1,2,3} {2,4}
{3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The complement is counted by
A088314.
The version for strict partitions is
A088528.
For nonnegative coefficients we have
A365380.
A085489 and
A364755 count subsets without the sum of two distinct elements.
A124506 appears to count combination-free subsets, differences of
A326083.
A364350 counts combination-free strict partitions, non-strict
A364915.
A365046 counts combination-full subsets, first differences of
A364914.
-
b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},
{b(n, i-1)[], seq(map(x->{x[], i}, b(n-i*j, i-1))[], j=1..n/i)}))
end:
a:= n-> 2^n-nops(b(n$2)):
seq(a(n), n=0..33); # Alois P. Heinz, Sep 04 2023
-
cpu[n_,y_]:=With[{s=Table[{k,i},{k,Union[y]},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],cpu[n,#]=={}&]],{n,0,10}]
-
from sympy.utilities.iterables import partitions
def A365322(n): return (1<Chai Wah Wu, Sep 14 2023
A088880
Number of different values of A000005(m) when A056239(m) is equal to n.
Original entry on oeis.org
1, 1, 2, 2, 5, 4, 8, 6, 12, 10, 16, 13, 25, 18, 28, 25, 40, 32, 51, 40, 62, 51, 76, 62, 99, 77, 112, 92, 138, 109, 165, 130, 189, 153, 220, 178, 267, 208, 292, 240, 347, 274, 397, 315, 445, 361, 512, 407, 591, 464, 647, 524, 746, 588, 830, 664, 928, 746, 1034
Offset: 0
-
multipl := proc(P,p)
local a;
a := 0 ;
for el in P do
if el = p then
a := a+1 ;
end if;
end do;
a ;
end proc:
A088880 := proc(n)
local pro,pa,m,p;
pro := {} ;
for pa in combinat[partition](n) do
m := 1 ;
for p from 1 to n do
m := m*(1+multipl(pa,p)) ;
end do:
pro := pro union {m} ;
end do:
nops(pro) ;
end proc: # R. J. Mathar, Sep 27 2011
# second Maple program
b:= proc(n, i) option remember; `if`(n=0 or i<2, {n+1},
{seq(map(p->p*(j+1), b(n-i*j, i-1))[], j=0..n/i)})
end:
a:= n-> nops(b(n, n)):
seq(a(n), n=0..50); # Alois P. Heinz, Aug 09 2012
-
b[n_, i_] := b[n, i] = If[n==0 || i<2, {n+1}, Table[b[n-i*j, i-1]*(j+1), {j, 0, n/i}] // Flatten // Union]; a[n_] := Length[b[n, n]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jan 08 2016, after Alois P. Heinz *)
A365314
Number of unordered pairs of distinct positive integers <= n that can be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 0, 1, 3, 6, 8, 14, 14, 23, 24, 33, 28, 52, 36, 55, 58, 73, 53, 95, 62, 110, 94, 105, 81, 165, 105, 133, 132, 176, 112, 225, 123, 210, 174, 192, 186, 306, 157, 223, 218, 328, 180, 354, 192, 324, 315, 288, 216, 474, 260, 383, 311, 404, 254, 491, 338, 511, 360
Offset: 0
We have 19 = 4*3 + 1*7, so the pair (3,7) is counted under a(19).
The a(2) = 1 through a(7) = 14 pairs:
(1,2) (1,2) (1,2) (1,2) (1,2) (1,2)
(1,3) (1,3) (1,3) (1,3) (1,3)
(2,3) (1,4) (1,4) (1,4) (1,4)
(2,3) (1,5) (1,5) (1,5)
(2,4) (2,3) (1,6) (1,6)
(3,4) (2,5) (2,3) (1,7)
(3,5) (2,4) (2,3)
(4,5) (2,5) (2,5)
(2,6) (2,7)
(3,4) (3,4)
(3,5) (3,7)
(3,6) (4,7)
(4,6) (5,7)
(5,6) (6,7)
For all subsets instead of just pairs we have
A365073, complement
A365380.
The case of positive coefficients is
A365315, for all subsets
A088314.
A004526 counts partitions of length 2, shift right for strict.
A364350 counts combination-free strict partitions.
-
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],{2}], combs[n,#]!={}&]],{n,0,30}]
-
from itertools import count
from sympy import divisors
def A365314(n):
a = set()
for i in range(1,n+1):
if not n%i:
a.update(tuple(sorted((i,j))) for j in range(1,n+1) if j!=i)
else:
for j in count(0,i):
if j > n:
break
k = n-j
for d in divisors(k):
if d>=i:
break
a.add((d,i))
return len(a) # Chai Wah Wu, Sep 12 2023
A365378
Number of integer partitions with sum < n whose distinct parts cannot be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 0, 0, 1, 1, 4, 2, 9, 5, 13, 10, 28, 7, 45, 25, 51, 32, 101, 31, 148, 50, 166, 106, 291, 47, 374, 176, 450, 179, 721, 121, 963, 285, 1080, 474, 1534, 200, 2140, 712, 2407, 599, 3539, 481, 4546, 1014, 4885
Offset: 0
The partition (5,2,2) has distinct parts {2,5} and has 11 = 3*2 + 1*5, so is not counted under a(11).
The partition (4,2,2) cannot be linearly combined to obtain 9, so is counted under a(9).
The partition (4,2,2) has distinct parts {2,4} and has 10 = 5*2 + 0*4, so is not counted under a(10).
The a(3) = 1 through a(10) = 10 partitions:
(2) (3) (2) (4) (2) (3) (2) (3)
(3) (5) (3) (5) (4) (4)
(4) (4) (6) (5) (6)
(22) (5) (7) (6) (7)
(6) (33) (7) (8)
(22) (8) (9)
(33) (22) (33)
(42) (42) (44)
(222) (44) (63)
(62) (333)
(222)
(422)
(2222)
For positive coefficients we have
A365323.
The complement is counted by
A365379.
The relatively prime case is
A365382.
A364350 counts combination-free strict partitions, non-strict
A364915.
A364839 counts combination-full strict partitions, non-strict
A364913.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Join@@IntegerPartitions/@Range[n-1],combs[n,Union[#]]=={}&]],{n,0,10}]
-
from sympy.utilities.iterables import partitions
def A365378(n):
a = {tuple(sorted(set(p))) for p in partitions(n)}
return sum(1 for m in range(1,n) for b in partitions(m) if not any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023
Comments