cp's OEIS Frontend

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

%I A324742 #12 Aug 22 2019 08:24:11
%S A324742 1,2,3,6,10,16,24,48,84,144,228,420,648,1080,1800,3600,5760,11136,
%T A324742 16704,31104,53568,90624,136896,269952,515712,862080,1708800,3171840,
%U A324742 4832640,9325440,14890752,29781504,52245504,88418304,166017024,331628544,497645568,829409280
%N A324742 Number of subsets of {2...n} containing no prime indices of the elements.
%C A324742 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 A324742 Andrew Howroyd, <a href="/A324742/b324742.txt">Table of n, a(n) for n = 1..100</a>
%e A324742 The a(1) = 1 through a(6) = 16 subsets:
%e A324742   {}  {}   {}   {}     {}       {}
%e A324742       {2}  {2}  {2}    {2}      {2}
%e A324742            {3}  {3}    {3}      {3}
%e A324742                 {4}    {4}      {4}
%e A324742                 {2,4}  {5}      {5}
%e A324742                 {3,4}  {2,4}    {6}
%e A324742                        {2,5}    {2,4}
%e A324742                        {3,4}    {2,5}
%e A324742                        {4,5}    {3,4}
%e A324742                        {2,4,5}  {3,6}
%e A324742                                 {4,5}
%e A324742                                 {4,6}
%e A324742                                 {5,6}
%e A324742                                 {2,4,5}
%e A324742                                 {3,4,6}
%e A324742                                 {4,5,6}
%e A324742 An example for n = 20 is {4,5,6,12,17,18,19}, with prime indices:
%e A324742    4: {1,1}
%e A324742    5: {3}
%e A324742    6: {1,2}
%e A324742   12: {1,1,2}
%e A324742   17: {7}
%e A324742   18: {1,2,2}
%e A324742   19: {8}
%e A324742 None of these prime indices {1,2,3,7,8} belong to the set, as required.
%t A324742 Table[Length[Select[Subsets[Range[2,n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]],{n,10}]
%o A324742 (PARI)
%o A324742 pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
%o A324742 a(n)={my(p=vector(n-1,k,pset(k+1)>>1), d=0); for(i=1, #p, d=bitor(d, p[i]));
%o A324742 ((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(!bitand(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<<k)), t)); t))(1,0)} \\ _Andrew Howroyd_, Aug 16 2019
%Y A324742 The maximal case is A324763. The version for subsets of {1...n} is A324741. The strict integer partition version is A324752. The integer partition version is A324757. The Heinz number version is A324761. An infinite version is A304360.
%Y A324742 Cf. A000720, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A290689, A290822, A306844, A324764.
%Y A324742 Cf. A324695, A324737, A324743, A324751, A324756, A324758.
%K A324742 nonn
%O A324742 1,2
%A A324742 _Gus Wiseman_, Mar 15 2019
%E A324742 Terms a(21) and beyond from _Andrew Howroyd_, Aug 16 2019