A324744 - OEIS

%I #9 Aug 27 2019 15:20:17

%S 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,

%T 88,96,96,184,184,240,240,264,264,296,296,592,592,592,592,728,728,

%U 1456,1456,1456,1456,2912,2912,3168,3168,3168,3168,5568,5568,5568,5568

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

%C 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.

%H Andrew Howroyd, <a href="/A324744/b324744.txt">Table of n, a(n) for n = 0..100</a>

%e The a(1) = 1 through a(8) = 6 maximal subsets:

%e   {1}  {1}  {2}    {1,3}  {1,3}    {1,3,6}    {3,4,6}    {1,3,6,7}

%e        {2}  {1,3}  {2,4}  {1,5}    {1,5,6}    {1,3,6,7}  {1,5,6,7}

%e                    {3,4}  {3,4}    {3,4,6}    {1,5,6,7}  {3,4,6,8}

%e                           {2,4,5}  {2,4,5,6}  {2,4,5,6}  {3,6,7,8}

%e                                               {2,5,6,7}  {2,4,5,6,8}

%e                                                          {2,5,6,7,8}

%t maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];

%t Table[Length[maxim[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]]],{n,0,10}]

%o (PARI)

%o pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}

%o a(n)={my(p=vector(n, k, if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));

%o 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);

%o 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)))));

%o recurse(1, 0)} \\ _Andrew Howroyd_, Aug 27 2019

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

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

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

%K nonn

%O 0,3

%A _Gus Wiseman_, Mar 15 2019

%E Terms a(16) and beyond from _Andrew Howroyd_, Aug 27 2019