A326489 Number of product-free subsets of {1..n}.

1, 1, 2, 4, 6, 12, 22, 44, 88, 136, 252, 504, 896, 1792, 3392, 6352, 9720, 19440, 35664, 71328, 129952, 247232, 477664, 955328, 1700416, 2657280, 5184000, 10368000, 19407360, 38814720, 68868352, 137736704, 260693504, 505830400, 999641600, 1882820608, 2807196672

Offset

0,3

Comments

A set is product-free if it contains no product of two (not necessarily distinct) elements.

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..167, (terms up to a(100) from Andrew Howroyd)

Marcel K. Goh and Jonah Saks, Alternating-sum statistics for certain sets of integers, arXiv:2206.12535 [math.CO], 2022.

Andrew Howroyd, PARI Program

Example

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

Mathematica

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

Crossrefs

Product-closed subsets are A326076.

Subsets containing no products are A326114.

Subsets containing no products of distinct elements are A326117.

Subsets containing no quotients are A327591.

Maximal product-free subsets are A326496.

Cf. A007865, A051026, A326023, A326081, A326116, A326495.

Sequence in context: A370648 A326114 A135231 * A217356 A030793 A085988

Adjacent sequences: A326486 A326487 A326488 * A326490 A326491 A326492

Keyword

nonn

Author

Gus Wiseman, Jul 09 2019

Extensions

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

a(0)=1 prepended to data, example and b-file by Peter Kagey, Sep 18 2019

Status

approved