login
A324744
Number of maximal subsets of {1...n} containing no element whose prime indices all belong to the subset.
15
1, 1, 2, 2, 3, 4, 4, 5, 6, 8, 8, 11, 11, 22, 22, 22, 22, 28, 28, 44, 44, 52, 52, 76, 76, 88, 88, 96, 96, 184, 184, 240, 240, 264, 264, 296, 296, 592, 592, 592, 592, 728, 728, 1456, 1456, 1456, 1456, 2912, 2912, 3168, 3168, 3168, 3168, 5568, 5568, 5568, 5568
OFFSET
0,3
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.
LINKS
EXAMPLE
The a(1) = 1 through a(8) = 6 maximal subsets:
{1} {1} {2} {1,3} {1,3} {1,3,6} {3,4,6} {1,3,6,7}
{2} {1,3} {2,4} {1,5} {1,5,6} {1,3,6,7} {1,5,6,7}
{3,4} {3,4} {3,4,6} {1,5,6,7} {3,4,6,8}
{2,4,5} {2,4,5,6} {2,4,5,6} {3,6,7,8}
{2,5,6,7} {2,4,5,6,8}
{2,5,6,7,8}
MATHEMATICA
maxim[s_]:=Complement[s, Last/@Select[Tuples[s, 2], UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[n]], !MemberQ[#, k_/; SubsetQ[#, PrimePi/@First/@FactorInteger[k]]]&]]], {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, if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=for(k=1, #p, if(!bittest(b, k) && bitnegimply(p[k], b), my(e=bitor(b, 1<<k), f=0); for(j=k+1, #p, if(bittest(b, j) && !bitnegimply(p[j], e), f=1; break)); if(!f, return(0)) )); 1);
my(recurse(k, b)=if(k>#p, ismax(b), my(f=bitnegimply(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<<k)))));
recurse(1, 0)} \\ Andrew Howroyd, Aug 27 2019
CROSSREFS
The non-maximal case is A324738. The case for subsets of {2...n} is A324762.
Sequence in context: A296371 A337601 A340283 * A097920 A029042 A320470
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 15 2019
EXTENSIONS
Terms a(16) and beyond from Andrew Howroyd, Aug 27 2019
STATUS
approved