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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 13 2019
EXTENSIONS
Terms a(21) and beyond from Andrew Howroyd, Aug 24 2019
STATUS
approved