A324737 Number of subsets of {2...n} containing every element of {2...n} whose prime indices all belong to the subset.

1, 2, 3, 6, 8, 16, 24, 48, 84, 168, 216, 432, 648, 1296, 2448, 4896, 6528, 13056, 19584, 39168, 77760, 155520, 229248, 458496, 790272, 1580544, 3128832, 6257664, 9386496, 18772992, 24081408, 48162816, 95938560, 191877120, 378335232, 756670464, 1135005696, 2270011392

Offset

1,2

Comments

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.

Also the number of subsets of {2...n} with complement containing no term whose prime indices all belong to the subset.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100

Example

The a(1) = 1 through a(6) = 16 subsets:
  {}  {}   {}     {}       {}         {}
      {2}  {3}    {3}      {4}        {4}
           {2,3}  {4}      {5}        {5}
                  {2,3}    {3,5}      {6}
                  {3,4}    {4,5}      {3,5}
                  {2,3,4}  {2,3,5}    {4,5}
                           {3,4,5}    {4,6}
                           {2,3,4,5}  {5,6}
                                      {2,3,5}
                                      {3,4,5}
                                      {3,5,6}
                                      {4,5,6}
                                      {2,3,4,5}
                                      {2,3,5,6}
                                      {3,4,5,6}
                                      {2,3,4,5,6}
An example for n = 15 is {2, 3, 5, 8, 9, 10, 11, 15}. The numbers from 2 to 15 with all prime indices in the subset are {3, 5, 9, 11, 15}, which all belong to the subset, as required.

Mathematica

Table[Length[Select[Subsets[Range[2, n]], Function[set, SubsetQ[set, Select[Range[2, n], SubsetQ[set, PrimePi/@First/@FactorInteger[#]]&]]]]], {n, 10}]

Prog

(PARI)
pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n-1, k, pset(k+1)>>1), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k, b)->if(k>#p, 1, my(t=self()(k+1, b+(1<<k))); if(bitnegimply(p[k], b), t+=if(bittest(d, k), self()(k+1, b), t)); t))(1, 0)} \\ Andrew Howroyd, Aug 24 2019

Crossrefs

Cf. A000720, A001221, A001462, A007097, A084422, A085945, A112798, A276625, A290689, A290822, A304360, A306844.

Cf. A324697, A324698, A324736, A324738, A324748, A324753, A324755.

Sequence in context: A029867 A056348 A308546 * A057574 A198296 A276033

Adjacent sequences: A324734 A324735 A324736 * A324738 A324739 A324740

Keyword

nonn

Author

Gus Wiseman, Mar 13 2019

Extensions

Terms a(21) and beyond from Andrew Howroyd, Aug 24 2019

Status

approved