cp's OEIS Frontend

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

%I A324762 #8 Aug 27 2019 15:20:31
%S A324762 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,
%T A324762 72,144,144,176,176,200,200,232,232,464,464,464,464,536,536,1072,1072,
%U A324762 1072,1072,2144,2144,2400,2400,2400,2400,4800,4800,4800,4800,4800
%N A324762 Number of maximal subsets of {2...n} containing no element whose prime indices all belong to the subset.
%C A324762 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 A324762 Andrew Howroyd, <a href="/A324762/b324762.txt">Table of n, a(n) for n = 1..100</a>
%e A324762 The a(2) = 1 through a(9) = 6 maximal subsets:
%e A324762   {2}  {2}  {2,4}  {3,4}    {3,4,6}    {3,4,6}    {3,4,6,8}    {2,4,5,6,8}
%e A324762        {3}  {3,4}  {2,4,5}  {2,4,5,6}  {3,6,7}    {3,6,7,8}    {2,5,6,7,8}
%e A324762                                        {2,4,5,6}  {2,4,5,6,8}  {3,4,6,8,9}
%e A324762                                        {2,5,6,7}  {2,5,6,7,8}  {3,6,7,8,9}
%e A324762                                                                {4,5,6,8,9}
%e A324762                                                                {5,6,7,8,9}
%t A324762 maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
%t A324762 Table[Length[maxim[Select[Subsets[Range[2,n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]]],{n,10}]
%o A324762 (PARI)
%o A324762 pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
%o A324762 a(n)={my(p=vector(n, k, pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
%o A324762 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 A324762 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 A324762 recurse(1, 0)} \\ _Andrew Howroyd_, Aug 27 2019
%Y A324762 The non-maximal version is A324739.
%Y A324762 The version for subsets of {1...n} is A324744.
%Y A324762 An infinite version is A324694.
%Y A324762 Cf. A076078, A084422, A085945, A112798, A276625, A304360, A306844.
%Y A324762 Cf. A324695, A324738, A324742, A324743, A324763, A324750, A324754, A324755, A324760.
%K A324762 nonn
%O A324762 1,3
%A A324762 _Gus Wiseman_, Mar 17 2019
%E A324762 Terms a(16) and beyond from _Andrew Howroyd_, Aug 27 2019