A326116 Number of subsets of {2..n} containing no products of two or more distinct elements.

1, 2, 4, 8, 16, 28, 56, 100, 200, 364, 728, 1232, 2464, 4592, 8296, 15920, 31840, 55952, 111904, 195712, 362336, 697360, 1394720, 2334112, 4668224, 9095392, 17225312, 31242784, 62485568, 106668608, 213337216, 392606528, 755131840, 1491146912, 2727555424, 4947175712

Offset

1,2

Comments

First differs from A308542 at a(12) = 1232, A308542(12) = 1184.

If this sequence counts product-free sets, A308542 counts product-closed sets.

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..47

Formula

For n > 0, a(n) = A326117(n) - 1.

Example

The a(6) = 28 subsets:
  {}  {2}  {2,3}  {2,3,4}  {2,3,4,5}
      {3}  {2,4}  {2,3,5}  {2,4,5,6}
      {4}  {2,5}  {2,4,5}  {3,4,5,6}
      {5}  {2,6}  {2,4,6}
      {6}  {3,4}  {2,5,6}
           {3,5}  {3,4,5}
           {3,6}  {3,4,6}
           {4,5}  {3,5,6}
           {4,6}  {4,5,6}
           {5,6}

Mathematica

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

Prog

(PARI)
a(n)={
   my(recurse(k, ep)=
    if(k > n, 1,
      my(t = self()(k + 1, ep));
      if(!bittest(ep, k),
         forstep(i=n\k, 1, -1, if(bittest(ep, i), ep=bitor(ep, 1<<(k*i))));
         t += self()(k + 1, ep);
      );
      t);
   );
   recurse(2, 2);
} \\ Andrew Howroyd, Aug 25 2019

Crossrefs

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

Sequence in context: A349052 A355969 A308542 * A054189 A127195 A255937

Adjacent sequences: A326113 A326114 A326115 * A326117 A326118 A326119

Keyword

nonn

Author

Gus Wiseman, Jun 06 2019

Extensions

Terms a(21)-a(36) from Andrew Howroyd, Aug 25 2019

Status

approved