login
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
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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 05 2019
EXTENSIONS
Terms a(19) to a(55) from Andrew Howroyd, Aug 30 2019
Name edited by Nathan McNew, Aug 10 2020
STATUS
approved