OFFSET
0,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 {1...n} containing no prime indices of the non-elements up to n.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..100
EXAMPLE
The a(0) = 1 through a(6) = 15 subsets:
{} {} {} {} {} {} {}
{1} {1} {1} {1} {1} {1}
{1,2} {1,2} {1,2} {1,2} {1,2}
{1,2,3} {1,4} {1,4} {1,4}
{1,2,3} {1,2,3} {1,2,3}
{1,2,4} {1,2,4} {1,2,4}
{1,2,3,4} {1,2,3,4} {1,2,6}
{1,2,3,5} {1,2,3,4}
{1,2,3,4,5} {1,2,3,5}
{1,2,3,6}
{1,2,4,6}
{1,2,3,4,5}
{1,2,3,4,6}
{1,2,3,5,6}
{1,2,3,4,5,6}
An example for n = 18 is {1,2,4,7,8,9,12,16,17,18}, whose elements have the following prime indices:
1: {}
2: {1}
4: {1,1}
7: {4}
8: {1,1,1}
9: {2,2}
12: {1,1,2}
16: {1,1,1,1}
17: {7}
18: {1,2,2}
All of these prime indices {1,2,4,7} belong to the subset, as required.
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], SubsetQ[#, PrimePi/@First/@Join@@FactorInteger/@DeleteCases[#, 1]]&]], {n, 0, 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, k, pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k, b)->if(k>#p, 1, my(t=self()(k+1, b)); if(!bitnegimply(p[k], b), t+=if(bittest(d, k), self()(k+1, b+(1<<k)), t)); t))(1, 0)} \\ Andrew Howroyd, Aug 15 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 13 2019
EXTENSIONS
Terms a(21) and beyond from Andrew Howroyd, Aug 15 2019
STATUS
approved