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

1, 1, 2, 2, 3, 4, 4, 5, 6, 8, 8, 11, 11, 22, 22, 22, 22, 28, 28, 44, 44, 52, 52, 76, 76, 88, 88, 96, 96, 184, 184, 240, 240, 264, 264, 296, 296, 592, 592, 592, 592, 728, 728, 1456, 1456, 1456, 1456, 2912, 2912, 3168, 3168, 3168, 3168, 5568, 5568, 5568, 5568

Offset: 0

Author

Gus Wiseman, Mar 15 2019

Keywords

• nonn

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.

Examples

			The a(1) = 1 through a(8) = 6 maximal subsets:
  {1}  {1}  {2}    {1,3}  {1,3}    {1,3,6}    {3,4,6}    {1,3,6,7}
       {2}  {1,3}  {2,4}  {1,5}    {1,5,6}    {1,3,6,7}  {1,5,6,7}
                   {3,4}  {3,4}    {3,4,6}    {1,5,6,7}  {3,4,6,8}
                          {2,4,5}  {2,4,5,6}  {2,4,5,6}  {3,6,7,8}
                                              {2,5,6,7}  {2,4,5,6,8}
                                                         {2,5,6,7,8}
		

Links

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

Crossrefs

The non-maximal case is A324738. The case for subsets of {2...n} is A324762.

Cf. A000720, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A290822, A304360, A306844, A320426, A324764.

Cf. A324694, A324736, A324743, A324749, A324754, A324759.

Programs

Mathematica

maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]]],{n,0,10}]

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, if(k==1, 1, 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<#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<Andrew Howroyd, Aug 27 2019

Extensions

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