login
A324736
Number of subsets of {1...n} containing all prime indices of the elements.
21
1, 2, 3, 4, 7, 9, 15, 22, 43, 79, 127, 175, 343, 511, 851, 1571, 3141, 4397, 8765, 13147, 25243, 46843, 76795, 115171, 230299, 454939, 758203, 1516363, 2916079, 4356079, 8676079, 12132079, 24264157, 45000157, 73800253, 145685053, 291369853, 437054653, 728424421
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
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
The strict integer partition version is A324748. The integer partition version is A324753. The Heinz number version is A290822. An infinite version is A324698.
Sequence in context: A276846 A303665 A027947 * A293853 A067236 A320357
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 13 2019
EXTENSIONS
Terms a(21) and beyond from Andrew Howroyd, Aug 15 2019
STATUS
approved