cp's OEIS Frontend

A324743 Number of maximal subsets of {1...n} containing no prime indices of the elements.

%I A324743 #10 Aug 26 2019 21:05:06
%S A324743 1,1,2,2,3,4,5,8,8,8,8,12,12,18,18,19,19,30,30,54,54,54,54,96,96,96,
%T A324743 96,96,96,156,156,244,244,248,248,248,248,440,440,440,440,688,688,
%U A324743 1120,1120,1120,1120,1864,1864,1864,1864,1864,1864,3664,3664,3664,3664,3664
%N A324743 Number of maximal subsets of {1...n} containing no prime indices of the elements.
%C A324743 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 A324743 Andrew Howroyd, <a href="/A324743/b324743.txt">Table of n, a(n) for n = 0..100</a>
%e A324743 The a(0) = 1 through a(8) = 8 maximal subsets:
%e A324743   {}  {1}  {1}  {2}    {1,3}  {1,3}    {1,3}    {1,3,7}  {1,3,7}
%e A324743            {2}  {1,3}  {2,4}  {1,5}    {1,5}    {1,5,7}  {1,5,7}
%e A324743                        {3,4}  {3,4}    {2,4,5}  {2,4,5}  {2,4,5,8}
%e A324743                               {2,4,5}  {3,4,6}  {2,5,7}  {2,5,7,8}
%e A324743                                        {4,5,6}  {3,4,6}  {3,4,6,8}
%e A324743                                                 {3,6,7}  {3,6,7,8}
%e A324743                                                 {4,5,6}  {4,5,6,8}
%e A324743                                                 {5,6,7}  {5,6,7,8}
%e A324743 An example for n = 15 is {1,5,7,9,13,15}, with prime indices:
%e A324743   1: {}
%e A324743   5: {3}
%e A324743   7: {4}
%e A324743   9: {2,2}
%e A324743   13: {6}
%e A324743   15: {2,3}
%e A324743 None of these prime indices {2,3,4,6} belong to the subset, as required.
%t A324743 maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
%t A324743 Table[Length[maxim[Select[Subsets[Range[n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]]],{n,0,10}]
%o A324743 (PARI)
%o A324743 pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
%o A324743 a(n)={my(p=vector(n, k, pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
%o A324743 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 A324743 ((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 A324743 The non-maximal case is A324741. The case for subsets of {2...n} is A324763.
%Y A324743 Cf. A000720, A001462, A007097, A084422, A085945, A112798, A276625, A290689, A290822, A304360, A306844, A320426, A324764.
%Y A324743 Cf. A324695, A324736, A324742, A324744, A324751, A324756, A324758.
%K A324743 nonn
%O A324743 0,3
%A A324743 _Gus Wiseman_, Mar 15 2019
%E A324743 Terms a(16) and beyond from _Andrew Howroyd_, Aug 26 2019