A326076 Number of subsets of {1..n} containing all of their integer products <= n.

1, 2, 4, 8, 12, 24, 44, 88, 152, 232, 444, 888, 1576, 3152, 6136, 11480, 17112, 34224, 63504, 127008, 232352, 442208, 876944, 1753888, 3138848, 4895328, 9739152, 18141840, 34044720, 68089440, 123846624, 247693248, 469397440, 924014144, 1845676384, 3469128224, 5182711584

Offset

0,2

Comments

The strict case is A326081.

Links

Table of n, a(n) for n=0..36.

Formula

a(n) = 2*A326114(n) for n > 0. - Andrew Howroyd, Aug 30 2019

Example

The a(0) = 1 through a(4) = 12 sets:
  {}  {}   {}     {}       {}
      {1}  {1}    {1}      {1}
           {2}    {2}      {3}
           {1,2}  {3}      {4}
                  {1,2}    {1,3}
                  {1,3}    {1,4}
                  {2,3}    {2,4}
                  {1,2,3}  {3,4}
                           {1,2,4}
                           {1,3,4}
                           {2,3,4}
                           {1,2,3,4}
The a(6) = 44 sets:
  {}  {1}  {1,3}  {1,2,4}  {1,2,4,5}  {1,2,3,4,6}  {1,2,3,4,5,6}
      {3}  {1,4}  {1,3,4}  {1,2,4,6}  {1,2,4,5,6}
      {4}  {1,5}  {1,3,5}  {1,3,4,5}  {1,3,4,5,6}
      {5}  {1,6}  {1,3,6}  {1,3,4,6}  {2,3,4,5,6}
      {6}  {2,4}  {1,4,5}  {1,3,5,6}
           {3,4}  {1,4,6}  {1,4,5,6}
           {3,5}  {1,5,6}  {2,3,4,6}
           {3,6}  {2,4,5}  {2,4,5,6}
           {4,5}  {2,4,6}  {3,4,5,6}
           {4,6}  {3,4,5}
           {5,6}  {3,4,6}
                  {3,5,6}
                  {4,5,6}

Mathematica

Table[Length[Select[Subsets[Range[n]], SubsetQ[#, Select[Times@@@Tuples[#, 2], #<=n&]]&]], {n, 0, 10}]

Prog

(PARI)
a(n)={
    my(lim=vector(n, k, sqrtint(k)));
    my(accept(b, k)=for(i=2, lim[k], if(k%i ==0 && bittest(b, i) && bittest(b, k/i), return(0))); 1);
    my(recurse(k, b)=
      my(m=1);
      for(j=max(2*k, n\2+1), min(2*k+1, n), if(accept(b, j), m*=2));
      k++;
      m*if(k > n\2, 1, self()(k, b + (1<<k)) + if(accept(b, k), self()(k, b)))
   );
   recurse(0, 0);
} \\ Andrew Howroyd, Aug 30 2019

Crossrefs

Cf. A007865, A051026, A103580, A196724, A326020, A326023, A326078, A326079, A326081.

Sequence in context: A353796 A294067 A279312 * A181808 A343014 A097942

Adjacent sequences: A326073 A326074 A326075 * A326077 A326078 A326079

Keyword

nonn

Author

Gus Wiseman, Jun 05 2019

Extensions

a(16)-a(30) from Andrew Howroyd, Aug 16 2019

Terms a(31) and beyond from Andrew Howroyd, Aug 30 2019

Status

approved