A326496 Number of maximal product-free subsets of {1..n}.

1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 6, 6, 9, 9, 15, 17, 30, 30, 46, 46, 51, 61, 103, 103, 129, 158, 282, 282, 322, 322, 553, 553, 615, 689, 1247, 1365, 1870, 1870, 3566, 3758, 5244, 5244, 8677, 8677, 9807, 12147, 23351, 23351, 27469, 31694, 45718, 47186, 54594, 54594, 95382, 108198

Offset

0,5

Comments

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

Also the number of maximal quotient-free subsets of {1..n}.

Links

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

Andrew Howroyd, PARI Program

Example

The a(2) = 1 through a(10) = 6 subsets (A = 10):
  {2}  {23}  {23}  {235}  {235}   {2357}   {23578}   {23578}   {23578}
             {34}  {345}  {256}   {2567}   {25678}   {256789}  {2378A}
                          {3456}  {34567}  {345678}  {345678}  {256789}
                                                     {456789}  {26789A}
                                                               {345678A}
                                                               {456789A}

Mathematica

fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]], Intersection[#, Times@@@Tuples[#, 2]]=={}&]]], {n, 0, 10}]

Prog

(PARI) \\ See link for program file.
for(n=0, 30, print1(A326496(n), ", ")) \\ Andrew Howroyd, Aug 30 2019

Crossrefs

Product-free subsets are A326489.

Subsets without products of distinct elements are A326117.

Maximal sum-free subsets are A121269.

Maximal sum-free and product-free subsets are A326497.

Maximal subsets without products of distinct elements are A325710.

Cf. A007865, A051026, A326076, A326491, A326492, A326495, A327591.

Sequence in context: A036846 A227396 A331590 * A058740 A160642 A110868

Adjacent sequences: A326493 A326494 A326495 * A326497 A326498 A326499

Keyword

nonn

Author

Gus Wiseman, Jul 09 2019

Extensions

a(18)-a(55) from Andrew Howroyd, Aug 30 2019

Status

approved