A326081 -id:A326081 - cp's OEIS frontend

A051026 Number of primitive subsequences of {1, 2, ..., n}.

1, 2, 3, 5, 7, 13, 17, 33, 45, 73, 103, 205, 253, 505, 733, 1133, 1529, 3057, 3897, 7793, 10241, 16513, 24593, 49185, 59265, 109297, 163369, 262489, 355729, 711457, 879937, 1759873, 2360641, 3908545, 5858113, 10534337, 12701537, 25403073, 38090337, 63299265, 81044097, 162088193, 205482593, 410965185, 570487233, 855676353

Offset: 0

Eric W. Weisstein

a(n) counts all subsequences of {1, ..., n} in which no term divides any other. If n is a prime a(n) = 2*a(n-1)-1 because for each subsequence s counted by a(n-1) two different subsequences are counted by a(n): s and s,n. There is only one exception: 1,n is not a primitive subsequence because 1 divides n. For all n>1: a(n) < 2*a(n-1). - Alois P. Heinz, Mar 07 2011

Maximal primitive subsets are counted by A326077. - Gus Wiseman, Jun 07 2019

			a(4) = 7, the primitive subsequences (including the empty sequence) are: (), (1), (2), (3), (4), (2,3), (3,4).
a(5) = 13 = 2*7-1, the primitive subsequences are: (), (5), (1), (2), (2,5), (3), (3,5), (4), (4,5), (2,3), (2,3,5), (3,4), (3,4,5).
From _Gus Wiseman_, Jun 07 2019: (Start)
The a(0) = 1 through a(5) = 13 primitive (pairwise indivisible) subsets:
  {}  {}   {}   {}     {}     {}
      {1}  {1}  {1}    {1}    {1}
           {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}
a(n) is also the number of subsets of {1..n} containing all of their pairwise products <= n as well as any quotients of divisible elements. For example, the a(0) = 1 through a(5) = 13 subsets are:
  {}  {}   {}     {}       {}         {}
      {1}  {1}    {1}      {1}        {1}
           {1,2}  {1,2}    {1,3}      {1,3}
                  {1,3}    {1,4}      {1,4}
                  {1,2,3}  {1,2,4}    {1,5}
                           {1,3,4}    {1,2,4}
                           {1,2,3,4}  {1,3,4}
                                      {1,3,5}
                                      {1,4,5}
                                      {1,2,3,4}
                                      {1,2,4,5}
                                      {1,3,4,5}
                                      {1,2,3,4,5}
Also the number of subsets of {1..n} containing all of their multiples <= n. For example, the a(0) = 1 through a(5) = 13 subsets are:
  {}  {}   {}     {}       {}         {}
      {1}  {2}    {2}      {3}        {3}
           {1,2}  {3}      {4}        {4}
                  {2,3}    {2,4}      {5}
                  {1,2,3}  {3,4}      {2,4}
                           {2,3,4}    {3,4}
                           {1,2,3,4}  {3,5}
                                      {4,5}
                                      {2,3,4}
                                      {2,4,5}
                                      {3,4,5}
                                      {2,3,4,5}
                                      {1,2,3,4,5}
(End)
From _Gus Wiseman_, Mar 12 2024: (Start)
Also the number of subsets of {1..n} containing all divisors of the elements. For example, the a(0) = 1 through a(6) = 17 subsets are:
  {}  {}   {}     {}       {}         {}
      {1}  {1}    {1}      {1}        {1}
           {1,2}  {1,2}    {1,2}      {1,2}
                  {1,3}    {1,3}      {1,3}
                  {1,2,3}  {1,2,3}    {1,5}
                           {1,2,4}    {1,2,3}
                           {1,2,3,4}  {1,2,4}
                                      {1,2,5}
                                      {1,3,5}
                                      {1,2,3,4}
                                      {1,2,3,5}
                                      {1,2,4,5}
                                      {1,2,3,4,5}
(End)

Blanchet-Sadri, Francine. Algorithmic combinatorics on partial words. Chapman & Hall/CRC, Boca Raton, FL, 2008. ii+385 pp. ISBN: 978-1-4200-6092-8; 1-4200-6092-9 MR2384993 (2009f:68142). See p. 320. - N. J. A. Sloane, Apr 06 2012

Juliana Couras, Ricardo Jesus, and Tomás Oliveira e Silva, Table of n, a(n) for n = 0..800 (terms up to n=80 from Alois P. Heinz)
Marcel K. Goh and Jonah Saks, Alternating-sum statistics for certain sets of integers, arXiv:2206.12535 [math.CO], 2022.
Nathan McNew, Counting primitive subsets and other statistics of the divisor graph of {1,2,..,n}, arXiv:1808.04923 [math.NT], 2018.
Richárd Palincza, Counting type and extremal problems from Arithmetic Combinatorics, Ph. D. Thesis, Budapest Univ. Tech. Econ. (Hungary, 2024).
Eric Weisstein's World of Mathematics, Primitive Sequence

Cf. A007865, A054519, A096827, A103580, A303362, A305148.
Cf. A326023, A326076, A326077, A326081, A326082, A326083, A326117.
Cf. A037031, A051026, A355740, A368110, A370585.

with(numtheory):
b:= proc(s) option remember; local n;
      n:= max(s[]);
      `if`(n<0, 1, b(s minus {n}) + b(s minus divisors(n)))
    end:
bb:= n-> b({$2..n} minus divisors(n)):
sb:= proc(n) option remember; `if`(n<2, 0, bb(n) + sb(n-1)) end:
a:= n-> `if`(n=0, 1, `if`(isprime(n), 2*a(n-1)-1, 2+sb(n))):
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 07 2011

b[s_] := b[s] = With[{n=Max[s]}, If[n < 0, 1, b[Complement[s, {n}]] + b[Complement[s, Divisors[n]]]]];
bb[n_] := b[Complement[Range[2, n], Divisors[n]]];
sb[n_] := sb[n] = If[n < 2, 0, bb[n] + sb[n-1]];
a[n_] := If[n == 0, 1, If[PrimeQ[n], 2a[n-1] - 1, 2 + sb[n]]]; Table[a[n], {n, 0, 37}]
(* Jean-François Alcover, Jul 27 2011, converted from Maple *)
Table[Length[Select[Subsets[Range[n]], SubsetQ[#,Select[Union@@Table[#*i,{i,n}],#<=n&]]&]],{n,10}] (* Gus Wiseman, Jun 07 2019 *)
Table[Length[Select[Subsets[Range[n]], #==Union@@Divisors/@#&]],{n,0,10}] (* Gus Wiseman, Mar 12 2024 *)

More terms from David Wasserman, May 02 2002

a(32)-a(37) from Donovan Johnson, Aug 11 2010

A326076 Number of subsets of {1..n} containing all of their integer products <= n.

Original entry on oeis.org

1, 2, 4, 8, 12, 24, 44, 88, 152, 232, 444, 888, 1576, 3152, 6136, 11480, 17112, 34224, 63504, 127008, 232352, 442208, 876944, 1753888, 3138848, 4895328, 9739152, 18141840, 34044720, 68089440, 123846624, 247693248, 469397440, 924014144, 1845676384, 3469128224, 5182711584

Offset: 0

Gus Wiseman, Jun 05 2019

nonn

The strict case is A326081.

			The a(0) = 1 through a(4) = 12 sets:
  {}  {}   {}     {}       {}
      {1}  {1}    {1}      {1}
           {2}    {2}      {3}
           {1,2}  {3}      {4}
                  {1,2}    {1,3}
                  {1,3}    {1,4}
                  {2,3}    {2,4}
                  {1,2,3}  {3,4}
                           {1,2,4}
                           {1,3,4}
                           {2,3,4}
                           {1,2,3,4}
The a(6) = 44 sets:
  {}  {1}  {1,3}  {1,2,4}  {1,2,4,5}  {1,2,3,4,6}  {1,2,3,4,5,6}
      {3}  {1,4}  {1,3,4}  {1,2,4,6}  {1,2,4,5,6}
      {4}  {1,5}  {1,3,5}  {1,3,4,5}  {1,3,4,5,6}
      {5}  {1,6}  {1,3,6}  {1,3,4,6}  {2,3,4,5,6}
      {6}  {2,4}  {1,4,5}  {1,3,5,6}
           {3,4}  {1,4,6}  {1,4,5,6}
           {3,5}  {1,5,6}  {2,3,4,6}
           {3,6}  {2,4,5}  {2,4,5,6}
           {4,5}  {2,4,6}  {3,4,5,6}
           {4,6}  {3,4,5}
           {5,6}  {3,4,6}
                  {3,5,6}
                  {4,5,6}

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

Table[Length[Select[Subsets[Range[n]],SubsetQ[#,Select[Times@@@Tuples[#,2],#<=n&]]&]],{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 + (1<Andrew Howroyd, Aug 30 2019

a(n) = 2*A326114(n) for n > 0. - Andrew Howroyd, Aug 30 2019

a(16)-a(30) from Andrew Howroyd, Aug 16 2019

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

A326117 Number of subsets of {1..n} containing no products of two or more distinct elements.

Original entry on oeis.org

1, 2, 3, 5, 9, 17, 29, 57, 101, 201, 365, 729, 1233, 2465, 4593, 8297, 15921, 31841, 55953, 111905, 195713, 362337, 697361, 1394721, 2334113, 4668225, 9095393, 17225313, 31242785, 62485569, 106668609, 213337217, 392606529, 755131841, 1491146913, 2727555425, 4947175713

Offset: 0

Gus Wiseman, Jun 06 2019

nonn

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

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

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

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

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

For n > 0, a(n) = A326116(n) + 1.

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

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

Original entry on oeis.org

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

Gus Wiseman, Jul 09 2019

nonn

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

			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}

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

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.

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

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

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

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 48, 96, 144, 288, 432, 864, 1104, 2208, 3312, 5184, 7872, 15744, 20112, 40224, 53376, 84640, 126960, 253920, 309600, 619200, 928800, 1475136, 1984320, 3968640, 4901760, 9803520, 12585600, 20394624, 30591936, 52483392, 65894976, 131789952, 197684928, 323175744, 411685056

Offset: 0

Gus Wiseman, Jun 05 2019

nonn

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

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

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

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

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

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

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

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

cp's OEIS Frontend

A051026 Number of primitive subsequences of {1, 2, ..., n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A326076 Number of subsets of {1..n} containing all of their integer products <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326117 Number of subsets of {1..n} containing no products of two or more distinct elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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