|
|
A326077
|
|
Number of maximal primitive subsets of {1..n}.
|
|
11
|
|
|
1, 1, 2, 2, 3, 3, 4, 4, 6, 7, 11, 11, 13, 13, 23, 24, 36, 36, 48, 48, 64, 66, 126, 126, 150, 151, 295, 363, 507, 507, 595, 595, 895, 903, 1787, 1788, 2076, 2076, 4132, 4148, 5396, 5396, 6644, 6644, 9740, 11172, 22300, 22300, 26140, 26141, 40733, 40773, 60333, 60333, 80781, 80783
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) is the number of maximal primitive subsets of {1, ..., n}. Here primitive means that no element of the subset divides any other and maximal means that no element can be added to the subset while maintaining the property of being pairwise indivisible. - Nathan McNew, Aug 10 2020
|
|
LINKS
|
|
|
EXAMPLE
|
The a(0) = 1 through a(9) = 7 sets:
{} {1} {1} {1} {1} {1} {1} {1} {1} {1}
{2} {23} {23} {235} {235} {2357} {2357} {2357}
{34} {345} {345} {3457} {3457} {2579}
{456} {4567} {3578} {3457}
{4567} {3578}
{5678} {45679}
{56789}
|
|
MATHEMATICA
|
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]], stableQ[#, Divisible]&]]], {n, 0, 10}]
|
|
PROG
|
(PARI)
divset(n)={sumdiv(n, d, if(d<n, 1 << d))}
a(n)={my(p=vector(n, k, divset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=my(e=0); forstep(k=#p, 1, -1, if(bittest(b, k), e=bitor(e, p[k]), if(!bittest(e, k) && !bitand(p[k], b), return(0)) )); 1);
((k, b)->if(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<<k)))))(1, 0)} \\ Andrew Howroyd, Aug 30 2019
|
|
CROSSREFS
|
Cf. A001055, A051026 (all primitive subsets), A067992, A096827, A143824, A285572, A285573, A303362, A305148, A305149, A316476, A325861, A326023, A326082.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|