login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

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

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.

Cf. A000720, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A290822, A304360, A306844, A320426, A324764.

Cf. A324694, A324736, A324743, A324749, A324754, A324759.

Sequence in context: A296371 A337601 A340283 * A097920 A029042 A320470

Adjacent sequences:  A324741 A324742 A324743 * A324745 A324746 A324747

KEYWORD

nonn

AUTHOR

Gus Wiseman, Mar 15 2019

EXTENSIONS

Terms a(16) and beyond from Andrew Howroyd, Aug 27 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 29 06:21 EDT 2021. Contains 346340 sequences. (Running on oeis4.)