cp's OEIS Frontend

A324763 Number of maximal subsets of {2...n} containing no prime indices of the elements.

%I A324763 #7 Aug 26 2019 21:03:13
%S A324763 1,1,2,2,2,3,6,6,6,6,10,10,16,16,16,16,24,24,48,48,48,48,84,84,84,84,
%T A324763 84,84,144,144,228,228,228,228,228,228,420,420,420,420,648,648,1080,
%U A324763 1080,1080,1080,1800,1800,1800,1800,1800,1800,3600,3600,3600,3600,3600
%N A324763 Number of maximal subsets of {2...n} containing no prime indices of the elements.
%C A324763 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 A324763 Andrew Howroyd, <a href="/A324763/b324763.txt">Table of n, a(n) for n = 1..100</a>
%e A324763 The a(1) = 1 through a(9) = 6 subsets:
%e A324763   {}  {2}  {2}  {2,4}  {3,4}    {2,4,5}  {2,4,5}  {2,4,5,8}  {2,4,5,8}
%e A324763            {3}  {3,4}  {2,4,5}  {3,4,6}  {2,5,7}  {2,5,7,8}  {2,5,7,8}
%e A324763                                 {4,5,6}  {3,4,6}  {3,4,6,8}  {3,4,6,8,9}
%e A324763                                          {3,6,7}  {3,6,7,8}  {3,6,7,8,9}
%e A324763                                          {4,5,6}  {4,5,6,8}  {4,5,6,8,9}
%e A324763                                          {5,6,7}  {5,6,7,8}  {5,6,7,8,9}
%t A324763 maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
%t A324763 Table[Length[maxim[Select[Subsets[Range[2,n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]]],{n,10}]
%o A324763 (PARI)
%o A324763 pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
%o A324763 a(n)={my(p=vector(n-1, k, pset(k+1)>>1), d=0); for(i=1, #p, d=bitor(d, p[i]));
%o A324763 my(ismax(b)=my(e=0); forstep(k=#p, 1, -1, if(bittest(b,k), e=bitor(e,p[k]), if(!bittest(e,k) && !bitand(p[k], b), return(0)) )); 1);
%o A324763 ((k, b)->if(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<<k)))))(1, 0)} \\ _Andrew Howroyd_, Aug 26 2019
%Y A324763 The non-maximal version is A324742.
%Y A324763 The version for subsets of {1...n} is A324741.
%Y A324763 An infinite version is A304360.
%Y A324763 Cf. A076078, A084422, A085945, A112798, A276625, A306844, A324764.
%Y A324763 Cf. A324695, A324743, A324751, A324756, A324758, A324762.
%K A324763 nonn
%O A324763 1,3
%A A324763 _Gus Wiseman_, Mar 17 2019
%E A324763 Terms a(16) and beyond from _Andrew Howroyd_, Aug 26 2019