A324738
Number of subsets of {1...n} containing no element > 1 whose prime indices all belong to the subset.
Original entry on oeis.org
1, 2, 3, 5, 8, 13, 26, 42, 72, 120, 232, 376, 752, 1128, 2256, 4512, 8256, 13632, 27264, 42048, 82944, 158976, 313344, 497664, 995328, 1700352, 3350016, 5815296, 11630592, 17491968, 34983936, 56954880, 108933120, 210788352, 418258944, 804667392, 1609334784
Offset: 0
The a(0) = 1 through a(6) = 26 subsets:
{} {} {} {} {} {} {}
{1} {1} {1} {1} {1} {1}
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{1,3} {4} {4} {4}
{1,3} {5} {5}
{2,4} {1,3} {6}
{3,4} {1,5} {1,3}
{2,4} {1,5}
{2,5} {1,6}
{3,4} {2,4}
{4,5} {2,5}
{2,4,5} {2,6}
{3,4}
{3,6}
{4,5}
{4,6}
{5,6}
{1,3,6}
{1,5,6}
{2,4,5}
{2,4,6}
{2,5,6}
{3,4,6}
{4,5,6}
{2,4,5,6}
The maximal case is
A324744. The case of subsets of {2...n} is
A324739. The strict integer partition version is
A324749. The integer partition version is
A324754. The Heinz number version is
A324759. An infinite version is
A324694.
Cf.
A000720,
A001221,
A001462,
A007097,
A076078,
A084422,
A085945,
A112798,
A276625,
A279861,
A290689,
A290822,
A304360,
A306844.
-
Table[Length[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]],{n,0,10}]
-
pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019
A324843
Number of unlabeled rooted trees with n nodes where the branches of any branch of any terminal subtree form a submultiset of the branches of the same subtree.
Original entry on oeis.org
1, 1, 1, 2, 2, 4, 4, 8, 9, 15, 17, 31, 35, 57, 70, 111, 136, 213, 265, 405, 517, 763, 987, 1458, 1893, 2736, 3611, 5161, 6836, 9702
Offset: 1
The a(1) = 1 through a(8) = 8 rooted trees:
o (o) (oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
(o(o)) (oo(o)) (oo(oo)) (ooo(oo)) (ooo(ooo))
(ooo(o)) (oooo(o)) (oooo(oo))
(o(o)(o)) (oo(o)(o)) (ooooo(o))
(oo(o)(oo))
(ooo(o)(o))
(o(o)(o)(o))
(o(o)(o(o)))
The Matula-Goebel numbers of these trees are given by
A324842.
-
submultQ[cap_,fat_]:=And@@Function[i,Count[fat,i]>=Count[cap,i]]/@Union[List@@cap];
rallt[n_]:=Select[Union[Sort/@Join@@(Tuples[rallt/@#]&/@IntegerPartitions[n-1])],And@@Table[submultQ[b,#],{b,#}]&];
Table[Length[rallt[n]],{n,10}]
A365045
Number of subsets of {1..n} containing n such that no element can be written as a positive linear combination of the others.
Original entry on oeis.org
0, 1, 1, 2, 4, 11, 23, 53, 111, 235, 483, 988, 1998, 4036, 8114, 16289, 32645, 65389, 130887, 261923, 524014, 1048251, 2096753, 4193832, 8388034, 16776544, 33553622, 67107919, 134216597, 268434140, 536869355, 1073740012, 2147481511, 4294964834, 8589931700
Offset: 0
The subset {3,4,10} has 10 = 2*3 + 1*4 so is not counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
. {1} {2} {3} {4} {5}
{2,3} {3,4} {2,5}
{2,3,4} {3,5}
{1,2,3,4} {4,5}
{2,4,5}
{3,4,5}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
Without re-usable parts we have
A365071, first differences of
A151897.
A085489 and
A364755 count subsets w/o the sum of two distinct elements.
A088809 and
A364756 count subsets with the 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[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[combp[#[[k]],Union[Delete[#,k]]]=={},{k,Length[#]}]&]],{n,0,10}]
A324748
Number of strict integer partitions of n containing all prime indices of the parts.
Original entry on oeis.org
1, 1, 0, 1, 0, 1, 1, 1, 0, 2, 1, 2, 3, 2, 2, 4, 3, 4, 3, 5, 6, 9, 8, 7, 8, 11, 12, 13, 15, 17, 22, 22, 20, 28, 31, 32, 36, 41, 43, 53, 53, 59, 70, 76, 77, 89, 99, 108, 124, 135, 139, 160, 172, 188, 209, 229, 243, 274, 298, 315, 353, 391, 417, 457, 496, 538, 588
Offset: 0
The first 15 terms count the following integer partitions.
1: (1)
3: (2,1)
5: (4,1)
6: (3,2,1)
7: (4,2,1)
9: (8,1)
9: (6,2,1)
10: (4,3,2,1)
11: (8,2,1)
11: (5,3,2,1)
12: (9,2,1)
12: (7,4,1)
12: (6,3,2,1)
13: (8,4,1)
13: (6,4,2,1)
14: (8,3,2,1)
14: (7,4,2,1)
15: (12,2,1)
15: (9,3,2,1)
15: (8,4,2,1)
15: (5,4,3,2,1)
An example for n = 6 is (20,18,11,5,3,2,1), with prime indices:
20: {1,1,3}
18: {1,2,2}
11: {5}
5: {3}
3: {2}
2: {1}
1: {}
All of these prime indices {1,2,3,5} belong to the partition, as required.
Cf.
A000720,
A001462,
A007097,
A074971,
A078374,
A112798,
A276625,
A279861,
A290689,
A290760,
A305713.
-
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&SubsetQ[#,PrimePi/@First/@Join@@FactorInteger/@DeleteCases[#,1]]&]],{n,0,30}]
A365044
Number of subsets of {1..n} whose greatest element cannot be written as a (strictly) positive linear combination of the others.
Original entry on oeis.org
1, 2, 3, 5, 9, 20, 43, 96, 207, 442, 925, 1913, 3911, 7947, 16061, 32350, 64995, 130384, 261271, 523194, 1047208, 2095459, 4192212, 8386044, 16774078, 33550622, 67104244, 134212163, 268428760, 536862900, 1073732255, 2147472267, 4294953778, 8589918612, 17179850312
Offset: 0
The subset S = {3,5,6,8} has 6 = 2*3 + 0*5 + 0*8 and 8 = 1*3 + 1*5 + 0*6 but neither of these is strictly positive, so S is counted under a(8).
The a(0) = 1 through a(5) = 20 subsets:
{} {} {} {} {} {}
{1} {1} {1} {1} {1}
{2} {2} {2} {2}
{3} {3} {3}
{2,3} {4} {4}
{2,3} {5}
{3,4} {2,3}
{2,3,4} {2,5}
{1,2,3,4} {3,4}
{3,5}
{4,5}
{2,3,4}
{2,4,5}
{3,4,5}
{1,2,3,4}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
A085489 and
A364755 count subsets w/o the sum of two distinct elements.
A088809 and
A364756 count subsets with the sum of two distinct elements.
A364350 counts combination-free strict partitions, complement
A364839.
A364913 counts combination-full partitions.
Cf.
A006951,
A237113,
A237668,
A308546,
A324736,
A326020,
A326080,
A364272,
A364349,
A364534,
A365069.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],And@@Table[combp[Last[#],Union[Most[#]]]=={},{k,Length[#]}]&]],{n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A365044(n):
mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
return n+1+sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] not in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023
A324737
Number of subsets of {2...n} containing every element of {2...n} whose prime indices all belong to the subset.
Original entry on oeis.org
1, 2, 3, 6, 8, 16, 24, 48, 84, 168, 216, 432, 648, 1296, 2448, 4896, 6528, 13056, 19584, 39168, 77760, 155520, 229248, 458496, 790272, 1580544, 3128832, 6257664, 9386496, 18772992, 24081408, 48162816, 95938560, 191877120, 378335232, 756670464, 1135005696, 2270011392
Offset: 1
The a(1) = 1 through a(6) = 16 subsets:
{} {} {} {} {} {}
{2} {3} {3} {4} {4}
{2,3} {4} {5} {5}
{2,3} {3,5} {6}
{3,4} {4,5} {3,5}
{2,3,4} {2,3,5} {4,5}
{3,4,5} {4,6}
{2,3,4,5} {5,6}
{2,3,5}
{3,4,5}
{3,5,6}
{4,5,6}
{2,3,4,5}
{2,3,5,6}
{3,4,5,6}
{2,3,4,5,6}
An example for n = 15 is {2, 3, 5, 8, 9, 10, 11, 15}. The numbers from 2 to 15 with all prime indices in the subset are {3, 5, 9, 11, 15}, which all belong to the subset, as required.
Cf.
A000720,
A001221,
A001462,
A007097,
A084422,
A085945,
A112798,
A276625,
A290689,
A290822,
A304360,
A306844.
-
Table[Length[Select[Subsets[Range[2,n]],Function[set,SubsetQ[set,Select[Range[2,n],SubsetQ[set,PrimePi/@First/@FactorInteger[#]]&]]]]],{n,10}]
-
pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n-1, k, pset(k+1)>>1), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k, b)->if(k>#p, 1, my(t=self()(k+1, b+(1<Andrew Howroyd, Aug 24 2019
A365042
Number of subsets of {1..n} containing n such that some element can be written as a positive linear combination of the others.
Original entry on oeis.org
0, 0, 1, 2, 4, 5, 9, 11, 17, 21, 29, 36, 50, 60, 78, 95, 123, 147, 185, 221, 274, 325, 399, 472, 574, 672, 810, 945, 1131, 1316, 1557, 1812, 2137, 2462, 2892, 3322, 3881, 4460, 5176, 5916, 6846, 7817, 8993, 10250, 11765, 13333, 15280, 17308, 19731, 22306
Offset: 0
The subset {3,4,10} has 10 = 2*3 + 1*4 so is counted under a(10).
The a(0) = 0 through a(7) = 11 subsets:
. . {1,2} {1,3} {1,4} {1,5} {1,6} {1,7}
{1,2,3} {2,4} {1,2,5} {2,6} {1,2,7}
{1,2,4} {1,3,5} {3,6} {1,3,7}
{1,3,4} {1,4,5} {1,2,6} {1,4,7}
{2,3,5} {1,3,6} {1,5,7}
{1,4,6} {1,6,7}
{1,5,6} {2,3,7}
{2,4,6} {2,5,7}
{1,2,3,6} {3,4,7}
{1,2,3,7}
{1,2,4,7}
Without re-usable parts we have
A365069, first differences of
A364534.
A085489 and
A364755 count subsets with no sum of two distinct elements.
A088314 counts sets that can be linearly combined to obtain n.
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[Subsets[Range[n]],MemberQ[#,n]&&Or@@Table[combp[#[[k]],Union[Delete[#,k]]]!={},{k,Length[#]}]&]],{n,0,10}]
A324739
Number of subsets of {2...n} containing no element whose prime indices all belong to the subset.
Original entry on oeis.org
1, 2, 3, 6, 10, 20, 30, 60, 96, 192, 312, 624, 936, 1872, 3744, 7488, 12480, 24960, 37440, 74880, 142848, 285696, 456192, 912384, 1548288, 3096576, 5308416, 10616832, 15925248, 31850496, 51978240, 103956480, 200835072, 401670144, 771489792, 1542979584, 2314469376
Offset: 1
The a(1) = 1 through a(6) = 20 subsets:
{} {} {} {} {} {}
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{4} {4} {4}
{2,4} {5} {5}
{3,4} {2,4} {6}
{2,5} {2,4}
{3,4} {2,5}
{4,5} {2,6}
{2,4,5} {3,4}
{3,6}
{4,5}
{4,6}
{5,6}
{2,4,5}
{2,4,6}
{2,5,6}
{3,4,6}
{4,5,6}
{2,4,5,6}
The maximal case is
A324762. The case of subsets of {1...n} is
A324738. The strict integer partition version is
A324750. The integer partition version is
A324755. The Heinz number version is
A324760. An infinite version is
A324694.
Cf.
A000720,
A001221,
A001462,
A007097,
A084422,
A085945,
A112798,
A276625,
A279861,
A290689,
A290822,
A304360,
A306844.
-
Table[Length[Select[Subsets[Range[2,n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]],{n,10}]
-
pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019
A324854
Lexicographically earliest sequence containing 1 and all positive integers > 2 whose prime indices already belong to the sequence.
Original entry on oeis.org
1, 4, 7, 8, 14, 16, 17, 19, 28, 32, 34, 38, 43, 49, 53, 56, 59, 64, 67, 68, 76, 86, 98, 106, 107, 112, 118, 119, 128, 131, 133, 134, 136, 139, 152, 163, 172, 191, 196, 212, 214, 224, 227, 236, 238, 241, 256, 262, 263, 266, 268, 272, 277, 278, 289, 301, 304
Offset: 1
The sequence of terms together with their prime indices begins:
1: {}
4: {1,1}
7: {4}
8: {1,1,1}
14: {1,4}
16: {1,1,1,1}
17: {7}
19: {8}
28: {1,1,4}
32: {1,1,1,1,1}
34: {1,7}
38: {1,8}
43: {14}
49: {4,4}
53: {16}
56: {1,1,1,4}
59: {17}
64: {1,1,1,1,1,1}
67: {19}
68: {1,1,7}
-
S:= {1}:
for n from 3 to 400 do
if map(numtheory:-pi, numtheory:-factorset(n)) subset S then
S:= S union {n}
fi
od:
sort(convert(S,list)); # Robert Israel, Mar 19 2019
-
aQ[n_]:=Switch[n,1,True,2,False,,And@@Cases[FactorInteger[n],{p,k_}:>aQ[PrimePi[p]]]];
Select[Range[100],aQ]
A324842
Matula-Goebel numbers of rooted trees where the branches of any branch of any terminal subtree form a submultiset of the branches of the same subtree.
Original entry on oeis.org
1, 2, 4, 6, 8, 12, 16, 18, 24, 28, 32, 36, 48, 54, 56, 64, 72, 78, 84, 96, 108, 112, 128, 144, 152, 156, 162, 168, 192, 196, 216, 224, 234, 252, 256, 288, 304, 312, 324, 336, 384, 392, 432, 444, 448, 456, 468, 486, 504, 512, 576, 588, 608, 624, 648, 672, 702
Offset: 1
The sequence of rooted trees together with their Matula-Goebel numbers begins:
1: o
2: (o)
4: (oo)
6: (o(o))
8: (ooo)
12: (oo(o))
16: (oooo)
18: (o(o)(o))
24: (ooo(o))
28: (oo(oo))
32: (ooooo)
36: (oo(o)(o))
48: (oooo(o))
54: (o(o)(o)(o))
56: (ooo(oo))
64: (oooooo)
72: (ooo(o)(o))
78: (o(o)(o(o)))
84: (oo(o)(oo))
96: (ooooo(o))
-
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
qaQ[n_]:=And[And@@Table[Divisible[n,x],{x,primeMS[n]}],And@@qaQ/@primeMS[n]];
Select[Range[1000],qaQ]
Comments