login
A324762
Number of maximal subsets of {2...n} containing no element whose prime indices all belong to the subset.
8
1, 1, 2, 2, 2, 2, 4, 4, 6, 6, 8, 8, 16, 16, 16, 16, 16, 16, 32, 32, 40, 40, 52, 52, 64, 64, 72, 72, 144, 144, 176, 176, 200, 200, 232, 232, 464, 464, 464, 464, 536, 536, 1072, 1072, 1072, 1072, 2144, 2144, 2400, 2400, 2400, 2400, 4800, 4800, 4800, 4800, 4800
OFFSET
1,3
COMMENTS
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
LINKS
EXAMPLE
The a(2) = 1 through a(9) = 6 maximal subsets:
{2} {2} {2,4} {3,4} {3,4,6} {3,4,6} {3,4,6,8} {2,4,5,6,8}
{3} {3,4} {2,4,5} {2,4,5,6} {3,6,7} {3,6,7,8} {2,5,6,7,8}
{2,4,5,6} {2,4,5,6,8} {3,4,6,8,9}
{2,5,6,7} {2,5,6,7,8} {3,6,7,8,9}
{4,5,6,8,9}
{5,6,7,8,9}
MATHEMATICA
maxim[s_]:=Complement[s, Last/@Select[Tuples[s, 2], UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[2, n]], !MemberQ[#, k_/; SubsetQ[#, PrimePi/@First/@FactorInteger[k]]]&]]], {n, 10}]
PROG
(PARI)
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]));
my(ismax(b)=for(k=1, #p, if(!bittest(b, k) && bitnegimply(p[k], b), my(e=bitor(b, 1<<k), f=0); for(j=k+1, #p, if(bittest(b, j) && !bitnegimply(p[j], e), f=1; break)); if(!f, return(0)) )); 1);
my(recurse(k, b)=if(k>#p, ismax(b), my(f=bitnegimply(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<<k)))));
recurse(1, 0)} \\ Andrew Howroyd, Aug 27 2019
CROSSREFS
The non-maximal version is A324739.
The version for subsets of {1...n} is A324744.
An infinite version is A324694.
Sequence in context: A347663 A071809 A347325 * A104976 A325710 A214927
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 17 2019
EXTENSIONS
Terms a(16) and beyond from Andrew Howroyd, Aug 27 2019
STATUS
approved