A326024 Number of subsets of {1..n} containing no sums or products of distinct elements.

1, 2, 3, 5, 9, 15, 25, 41, 68, 109, 179, 284, 443, 681, 1062, 1587, 2440, 3638, 5443, 8021, 11953, 17273, 25578, 37001, 53953, 77429, 113063, 160636, 232928, 330775, 475380, 672056, 967831, 1359743, 1952235, 2743363, 3918401, 5495993, 7856134, 10984547, 15669741

Offset

0,2

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..80

Example

The a(0) = 1 through a(5) = 15 subsets:
  {}  {}   {}   {}     {}       {}
      {1}  {1}  {1}    {1}      {1}
           {2}  {2}    {2}      {2}
                {3}    {3}      {3}
                {2,3}  {4}      {4}
                       {2,3}    {5}
                       {2,4}    {2,3}
                       {3,4}    {2,4}
                       {2,3,4}  {2,5}
                                {3,4}
                                {3,5}
                                {4,5}
                                {2,3,4}
                                {2,4,5}
                                {3,4,5}

Mathematica

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

Prog

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

Crossrefs

Subsets without sums of distinct elements are A151897.

Subsets without products of distinct elements are A326117.

Maximal subsets without sums or products of distinct elements are A326025.

Subsets with sums (and products) are A326083.

Sum-free and product-free subsets are A326495.

Cf. A007865, A051026, A121269, A325710, A326076, A326489, A326497, A326498.

Sequence in context: A323475 A097083 A268709 * A200047 A147877 A003476

Adjacent sequences: A326021 A326022 A326023 * A326025 A326026 A326027

Keyword

nonn

Author

Gus Wiseman, Jul 09 2019

Extensions

Terms a(16)-a(40) from Andrew Howroyd, Aug 25 2019

Status

approved