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!)
A324741 Number of subsets of {1...n} containing no prime indices of the elements. 19
1, 2, 3, 5, 8, 13, 19, 30, 54, 96, 156, 248, 440, 688, 1120, 1864, 3664, 5856, 11232, 16896, 31296, 53952, 91008, 137472, 270528, 516720, 863088, 1710816, 3173856, 4836672, 9329472, 14897376, 29788128, 52256448, 88429248, 166037184, 331648704, 497685888, 829449600 (list; graph; refs; listen; history; text; internal format)
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.

LINKS

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

EXAMPLE

The a(0) = 1 through a(6) = 19 subsets:

  {}  {}   {}   {}     {}     {}       {}

      {1}  {1}  {1}    {1}    {1}      {1}

           {2}  {2}    {2}    {2}      {2}

                {3}    {3}    {3}      {3}

                {1,3}  {4}    {4}      {4}

                       {1,3}  {5}      {5}

                       {2,4}  {1,3}    {6}

                       {3,4}  {1,5}    {1,3}

                              {2,4}    {1,5}

                              {2,5}    {2,4}

                              {3,4}    {2,5}

                              {4,5}    {3,4}

                              {2,4,5}  {3,6}

                                       {4,5}

                                       {4,6}

                                       {5,6}

                                       {2,4,5}

                                       {3,4,6}

                                       {4,5,6}

An example for n = 20 is {5,6,7,9,10,12,14,15,16,19,20}, with prime indices:

   5: {3}

   6: {1,2}

   7: {4}

   9: {2,2}

  10: {1,3}

  12: {1,1,2}

  14: {1,4}

  15: {2,3}

  16: {1,1,1,1}

  19: {8}

  20: {1,1,3}

None of these prime indices {1,2,3,4,8} belong to the subset, as required.

MATHEMATICA

Table[Length[Select[Subsets[Range[n]], Intersection[#, PrimePi/@First/@Join@@FactorInteger/@#]=={}&]], {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(!bitand(p[k], b), t+=if(bittest(d, k), self()(k+1, b+(1<<k)), t)); t))(1, 0)} \\ Andrew Howroyd, Aug 16 2019

CROSSREFS

The maximal case is A324743. The strict integer partition version is A324751. The integer partition version is A324756. The Heinz number version is A324758. An infinite version is A304360.

Cf. A000720, A001462, A007097, A076078, A084422, A112798, A276625, A279861, A290689, A290822, A304360, A306844.

Cf. A324695, A324736, A324742.

Sequence in context: A326469 A326594 A045842 * A200462 A088795 A156145

Adjacent sequences:  A324738 A324739 A324740 * A324742 A324743 A324744

KEYWORD

nonn

AUTHOR

Gus Wiseman, Mar 15 2019

EXTENSIONS

Terms a(21) and beyond from Andrew Howroyd, Aug 16 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 8 04:16 EDT 2020. Contains 335504 sequences. (Running on oeis4.)