A324762 Number of maximal subsets of {2...n} containing no element whose prime indices all belong to the subset.

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

Andrew Howroyd, Table of n, a(n) for n = 1..100

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.

Cf. A076078, A084422, A085945, A112798, A276625, A304360, A306844.

Cf. A324695, A324738, A324742, A324743, A324763, A324750, A324754, A324755, A324760.

Sequence in context: A347663 A071809 A347325 * A104976 A325710 A214927

Adjacent sequences: A324759 A324760 A324761 * A324763 A324764 A324765

Keyword

nonn

Author

Gus Wiseman, Mar 17 2019

Extensions

Terms a(16) and beyond from Andrew Howroyd, Aug 27 2019

Status

approved