A326076 -id:A326076 - cp's OEIS frontend

A326495 Number of subsets of {1..n} containing no sums or products of pairs of elements.

1, 1, 2, 4, 6, 11, 17, 30, 45, 71, 101, 171, 258, 427, 606, 988, 1328, 2141, 3116, 4952, 6955, 11031, 15320, 23978, 33379, 48698, 66848, 104852, 144711, 220757, 304132, 461579, 636555, 973842, 1316512, 1958827, 2585432, 3882842, 5237092, 7884276, 10555738, 15729292

Offset: 0

Gus Wiseman, Jul 09 2019

nonn

The pairs are not required to be strict.

			The a(1) = 1 through a(6) = 17 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}
                         {3,4,5}  {3,5}
                                  {4,5}
                                  {4,6}
                                  {5,6}
                                  {2,5,6}
                                  {3,4,5}
                                  {4,5,6}

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

Subsets without sums are A007865.
Subsets without products are A326489.
Subsets without differences or quotients are A326490.
Maximal subsets without sums or products are A326497.
Subsets with sums (and products) are A326083.
Cf. A051026, A103580, A326020, A326076, A326117, A326491.

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

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

a(19)-a(41) from Andrew Howroyd, Aug 25 2019

A326497 Number of maximal sum-free and product-free subsets of {1..n}.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 6, 8, 9, 15, 21, 26, 38, 51, 69, 89, 119, 149, 197, 261, 356, 447, 601, 781, 1003, 1293, 1714, 2228, 2931, 3697, 4843, 6258, 8187, 10273, 13445, 16894, 21953, 27469, 35842, 45410, 58948, 73939, 95199, 120593, 154510, 192995, 247966, 312642

Offset: 0

Gus Wiseman, Jul 09 2019

nonn

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

			The a(2) = 1 through a(10) = 15 subsets (A = 10):
  {2}  {23}  {23}  {23}   {23}   {237}   {256}   {267}    {23A}
             {34}  {25}   {256}  {256}   {258}   {345}    {345}
                   {345}  {345}  {267}   {267}   {357}    {34A}
                          {456}  {345}   {345}   {2378}   {357}
                                 {357}   {357}   {2569}   {38A}
                                 {4567}  {2378}  {2589}   {2378}
                                         {4567}  {4567}   {2569}
                                         {5678}  {4679}   {2589}
                                                 {56789}  {267A}
                                                          {269A}
                                                          {4567}
                                                          {4679}
                                                          {479A}
                                                          {56789}
                                                          {6789A}

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..68
Andrew Howroyd, PARI Program

Sum-free and product-free subsets are A326495.
Sum-free subsets are A007865.
Maximal sum-free subsets are A121269.
Product-free subsets are A326489.
Maximal product-free subsets are A326496.
Subsets with sums (and products) are A326083.
Cf. A051026, A103580, A325710, A326076, A326117, A326491, A326492, A326498.

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

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

a(21)-a(40) from Andrew Howroyd, Aug 30 2019

a(41)-a(48) from Jinyuan Wang, Oct 11 2020

A326078 Number of subsets of {2..n} containing all of their integer quotients > 1.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 24, 48, 72, 144, 216, 432, 552, 1104, 1656, 2592, 3936, 7872, 10056, 20112, 26688, 42320, 63480, 126960, 154800, 309600, 464400, 737568, 992160, 1984320, 2450880, 4901760, 6292800, 10197312, 15295968, 26241696, 32947488, 65894976, 98842464, 161587872, 205842528

Offset: 0

Gus Wiseman, Jun 05 2019

nonn

These sets are closed under taking the quotient of two distinct divisible terms.

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

Cf. A007865, A051026, A054519, A067992, A103580, A325860, A325994, A326023, A326076, A326079, A326081.

Table[Length[Select[Subsets[Range[2,n]],SubsetQ[#,Divide@@@Select[Tuples[#,2],UnsameQ@@#&&Divisible@@#&]]&]],{n,0,10}]

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) + if(accept(b, k), self()(k, b + (1<Andrew Howroyd, Aug 30 2019

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

For n > 0, a(n) = A326079(n)/2.

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

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

Original entry on oeis.org

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

Gus Wiseman, Jun 06 2019

nonn

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

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

			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}

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..47
P. J. Cameron and P. Erdős, On the number of integers with various properties, in R. A. Mullin, ed., Number Theory: Proc. First Conf. of Canad. Number Theory Assoc. Conf., Banff, De Gruyter, Berlin, 1990, pp. 61-79.

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

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

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

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

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

A325710 Number of maximal subsets of {1..n} containing no products of distinct elements.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 24, 28, 32, 32, 62, 62, 92, 102, 184, 184, 254, 254, 474, 506, 686, 686, 1172, 1172, 1792, 1906, 3568, 3794, 5326, 5326, 10282, 10618, 14822, 14822, 25564, 25564, 35304, 39432, 76888, 76888, 100574, 100574, 197870, 201622, 282014

Offset: 0

Gus Wiseman, Jul 09 2019

nonn

			The a(1) = 1 through a(9) = 6 maximal subsets:
  {1}  {1}  {1}   {1}    {1}     {1}     {1}      {1}       {1}
       {2}  {23}  {234}  {2345}  {2345}  {23457}  {23457}   {234579}
                                 {2456}  {24567}  {23578}   {235789}
                                 {3456}  {34567}  {24567}   {245679}
                                                  {25678}   {256789}
                                                  {345678}  {3456789}

Andrew Howroyd, PARI Program

Subsets without products of distinct elements are A326117.
Maximal product-free subsets are A326496.
Subsets with products are A326076.
Maximal subsets without sums of distinct elements are A326498.
Maximal subsets without quotients are A326492.
Maximal subsets without sums or products of distinct elements are A326025.
Cf. A121269, A151897, A326116, A326489, A326497, A326024.

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

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

Terms a(16) and beyond from Andrew Howroyd, Aug 29 2019

A326114 Number of subsets of {2..n} containing no product of two or more (not necessarily distinct) elements.

Original entry on oeis.org

1, 1, 2, 4, 6, 12, 22, 44, 76, 116, 222, 444, 788, 1576, 3068, 5740, 8556, 17112, 31752, 63504, 116176, 221104, 438472, 876944, 1569424, 2447664, 4869576, 9070920, 17022360, 34044720, 61923312, 123846624, 234698720, 462007072, 922838192, 1734564112, 2591355792, 5182711584

Offset: 0

Gus Wiseman, Jun 06 2019

nonn

The strict case is A326117.
Also the number of subsets of {2..n} containing all of their integer products <= n. For example, the a(1) = 1 through a(5) = 12 subsets are:
  {}  {}  {}   {}     {}       {}
          {2}  {2}    {3}      {3}
               {3}    {4}      {4}
               {2,3}  {2,4}    {5}
                      {3,4}    {2,4}
                      {2,3,4}  {3,4}
                               {3,5}
                               {4,5}
                               {2,3,4}
                               {2,4,5}
                               {3,4,5}
                               {2,3,4,5}

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

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

a(n > 0) = A326076(n)/2.

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

A308542 Number of subsets of {2..n} containing the product of any set of distinct elements whose product is <= n.

Original entry on oeis.org

1, 2, 4, 8, 16, 28, 56, 100, 200, 364, 728, 1184, 2368, 4448, 8056, 15008, 30016, 52736, 105472, 183424, 339840, 663616, 1327232, 2217088, 4434176, 8744320, 16559168, 30034624, 60069248, 103402112, 206804224, 379941440, 730800064, 1454649248, 2659869664, 4786282208

Offset: 1

Gus Wiseman, Jun 06 2019

nonn

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

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

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

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

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

For n > 0, a(n) = A326081(n)/2.

Terms a(21) and beyond from Andrew Howroyd, Aug 24 2019

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

Original entry on oeis.org

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

Gus Wiseman, Jul 09 2019

nonn

			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}

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

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.

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

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<Andrew Howroyd, Aug 25 2019

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

A326494 Number of subsets of {1..n} containing all differences and quotients of pairs of distinct elements.

Original entry on oeis.org

1, 2, 4, 6, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127

Offset: 0

Gus Wiseman, Jul 09 2019

nonn

The only allowed sets are the empty set, any singleton, any initial interval of positive integers and {2,4}. This can be shown by induction. - Andrew Howroyd, Aug 25 2019

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

Subsets with difference are A054519.
Subsets with quotients are A326023.
Subsets with quotients > 1 are A326079.
Subsets without differences or quotients are A326490.
Cf. A005408, A007865, A051026, A325849, A326076, A326491.

Table[Length[Select[Subsets[Range[n]],SubsetQ[#,Union[Divide@@@Select[Tuples[#,2],UnsameQ@@#&&Divisible@@#&],Subtract@@@Select[Tuples[#,2],Greater@@#&]]]&]],{n,0,10}]

a(n) = 2*n + 1 = A005408(n) for n > 3. - Andrew Howroyd, Aug 25 2019

Terms a(20) and beyond from Andrew Howroyd, Aug 25 2019

A358392 Number of nonempty subsets of {1, 2, ..., n} with GCD equal to 1 and containing the sum of any two elements whenever it is at most n.

Original entry on oeis.org

1, 1, 2, 3, 7, 9, 19, 27, 46, 63, 113, 148, 253, 345, 539, 734, 1198, 1580, 2540, 3417, 5233, 7095, 11190, 14720, 22988, 31057, 47168, 63331, 98233, 129836, 200689, 269165, 406504, 546700, 838766, 1108583, 1700025, 2281517, 3437422, 4597833, 7023543, 9308824, 14198257, 18982014, 28556962

Offset: 1

Max Alekseyev, Nov 13 2022

nonn

Also, the number of distinct numerical semigroups that are generated by some subset of {1, 2, ..., n} and have a finite complement in the positive integers.

Max Alekseyev, Table of n, a(n) for n = 1..100
Marcel K. Goh et al., Counting numerical semigroups by largest element of minimal generating set, MathOverflow, 2022.

Inverse Moebius transform of A103580.

Cf. A007865, A050291, A051026, A085489, A139384, A151897, A308546, A326020, A326076, A326080, A326083, A326114.

a(n) = Sum_{k=1..n} moebius(k) * A103580(floor(n/k)).

cp's OEIS Frontend

A326495 Number of subsets of {1..n} containing no sums or products of pairs of elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326497 Number of maximal sum-free and product-free subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A326078 Number of subsets of {2..n} containing all of their integer quotients > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A325710 Number of maximal subsets of {1..n} containing no products of distinct elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A326114 Number of subsets of {2..n} containing no product of two or more (not necessarily distinct) elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A308542 Number of subsets of {2..n} containing the product of any set of distinct elements whose product is <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula