cp's OEIS Frontend

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

%I A324741 #9 Aug 16 2019 14:48:51
%S A324741 1,2,3,5,8,13,19,30,54,96,156,248,440,688,1120,1864,3664,5856,11232,
%T A324741 16896,31296,53952,91008,137472,270528,516720,863088,1710816,3173856,
%U A324741 4836672,9329472,14897376,29788128,52256448,88429248,166037184,331648704,497685888,829449600
%N A324741 Number of subsets of {1...n} containing no prime indices of the elements.
%C A324741 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 A324741 Andrew Howroyd, <a href="/A324741/b324741.txt">Table of n, a(n) for n = 0..100</a>
%e A324741 The a(0) = 1 through a(6) = 19 subsets:
%e A324741   {}  {}   {}   {}     {}     {}       {}
%e A324741       {1}  {1}  {1}    {1}    {1}      {1}
%e A324741            {2}  {2}    {2}    {2}      {2}
%e A324741                 {3}    {3}    {3}      {3}
%e A324741                 {1,3}  {4}    {4}      {4}
%e A324741                        {1,3}  {5}      {5}
%e A324741                        {2,4}  {1,3}    {6}
%e A324741                        {3,4}  {1,5}    {1,3}
%e A324741                               {2,4}    {1,5}
%e A324741                               {2,5}    {2,4}
%e A324741                               {3,4}    {2,5}
%e A324741                               {4,5}    {3,4}
%e A324741                               {2,4,5}  {3,6}
%e A324741                                        {4,5}
%e A324741                                        {4,6}
%e A324741                                        {5,6}
%e A324741                                        {2,4,5}
%e A324741                                        {3,4,6}
%e A324741                                        {4,5,6}
%e A324741 An example for n = 20 is {5,6,7,9,10,12,14,15,16,19,20}, with prime indices:
%e A324741    5: {3}
%e A324741    6: {1,2}
%e A324741    7: {4}
%e A324741    9: {2,2}
%e A324741   10: {1,3}
%e A324741   12: {1,1,2}
%e A324741   14: {1,4}
%e A324741   15: {2,3}
%e A324741   16: {1,1,1,1}
%e A324741   19: {8}
%e A324741   20: {1,1,3}
%e A324741 None of these prime indices {1,2,3,4,8} belong to the subset, as required.
%t A324741 Table[Length[Select[Subsets[Range[n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]],{n,0,10}]
%o A324741 (PARI)
%o A324741 pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
%o A324741 a(n)={my(p=vector(n,k,pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
%o A324741 ((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 A324741 The maximal case is A324743. The strict integer partition version is A324751. The integer partition version is A324756. The Heinz number version is A324758. An infinite version is A304360.
%Y A324741 Cf. A000720, A001462, A007097, A076078, A084422, A112798, A276625, A279861, A290689, A290822, A304360, A306844.
%Y A324741 Cf. A324695, A324736, A324742.
%K A324741 nonn
%O A324741 0,2
%A A324741 _Gus Wiseman_, Mar 15 2019
%E A324741 Terms a(21) and beyond from _Andrew Howroyd_, Aug 16 2019