A084422 -id:A084422 - cp's OEIS frontend

A343654 Number of pairwise coprime sets of divisors > 1 of n.

1, 2, 2, 3, 2, 5, 2, 4, 3, 5, 2, 8, 2, 5, 5, 5, 2, 8, 2, 8, 5, 5, 2, 11, 3, 5, 4, 8, 2, 15, 2, 6, 5, 5, 5, 13, 2, 5, 5, 11, 2, 15, 2, 8, 8, 5, 2, 14, 3, 8, 5, 8, 2, 11, 5, 11, 5, 5, 2, 25, 2, 5, 8, 7, 5, 15, 2, 8, 5, 15, 2, 18, 2, 5, 8, 8, 5, 15, 2, 14, 5, 5

Offset: 1

Gus Wiseman, Apr 26 2021

nonn

First differs from A100565 at a(210) = 52, A100565(210) = 51.

			The a(n) sets for n = 1, 2, 4, 6, 8, 12, 24, 30, 32, 36, 48:
  {}  {}   {}   {}     {}   {}     {}     {}       {}    {}     {}
      {2}  {2}  {2}    {2}  {2}    {2}    {2}      {2}   {2}    {2}
           {4}  {3}    {4}  {3}    {3}    {3}      {4}   {3}    {3}
                {6}    {8}  {4}    {4}    {5}      {8}   {4}    {4}
                {2,3}       {6}    {6}    {6}      {16}  {6}    {6}
                            {12}   {8}    {10}     {32}  {9}    {8}
                            {2,3}  {12}   {15}           {12}   {12}
                            {3,4}  {24}   {30}           {18}   {16}
                                   {2,3}  {2,3}          {36}   {24}
                                   {3,4}  {2,5}          {2,3}  {48}
                                   {3,8}  {3,5}          {2,9}  {2,3}
                                          {5,6}          {3,4}  {3,4}
                                          {2,15}         {4,9}  {3,8}
                                          {3,10}                {3,16}
                                          {2,3,5}

The version for partitions is A007359.
The version for subsets of {1..n} is A084422.
The case of pairs is A089233.
The version with 1's is A225520.
The maximal case is A343652.
The case without empty sets or singletons is A343653.
The maximal case without singletons is A343660.
A018892 counts pairwise coprime unordered pairs of divisors.
A051026 counts pairwise indivisible subsets of {1..n}.
A100565 counts pairwise coprime unordered triples of divisors.
A187106, A276187, and A320426 count other types of pairwise coprime sets.
A326077 counts maximal pairwise indivisible sets.
Cf. A007360, A051026, A062319, A074206, A087087, A101268, A285572, A305713, A320423, A326675, A337485, A343655.

pwcop[y_]:=And@@(GCD@@#1==1&)/@Subsets[y,{2}];
Table[Length[Select[Subsets[Rest[Divisors[n]]],pwcop]],{n,100}]

A343659 Number of maximal pairwise coprime subsets of {1..n}.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 7, 9, 9, 10, 10, 12, 16, 19, 19, 20, 20, 22, 28, 32, 32, 33, 54, 61, 77, 84, 84, 85, 85, 94, 112, 123, 158, 161, 161, 176, 206, 212, 212, 214, 214, 229, 241, 260, 260, 263, 417, 428, 490, 521, 521, 526, 655, 674, 764, 818, 818, 820, 820, 874, 918, 975, 1182, 1189, 1189

Offset: 1

Gus Wiseman, Apr 26 2021

nonn

For this sequence, it does not matter whether singletons are considered pairwise coprime.
For n > 2, also the number of maximal pairwise coprime subsets of {2..n}.
For each prime p <= n, p divides exactly one element of each maximal subset. - Bert Dobbelaere, May 04 2021

			The a(1) = 1 through a(9) = 7 subsets:
  {1}  {12}  {123}  {123}  {1235}  {156}   {1567}   {1567}   {1567}
                    {134}  {1345}  {1235}  {12357}  {12357}  {12357}
                                   {1345}  {13457}  {13457}  {12579}
                                                    {13578}  {13457}
                                                             {13578}
                                                             {14579}
                                                             {15789}

Bert Dobbelaere, Table of n, a(n) for n = 1..500
Bert Dobbelaere, Python program

The case of pairs is A015614.
The case of triples is A015617.
The non-maximal version counting empty sets and singletons is A084422.
The non-maximal version counting singletons is A187106.
The non-maximal version is A320426(n) = A276187(n) + 1.
The version for indivisibility instead of coprimality is A326077.
The version for sets of divisors is A343652.
The version for sets of divisors > 1 is A343660.
A018892 counts coprime unordered pairs of divisors.
A051026 counts pairwise indivisible subsets of {1..n}.
A100565 counts pairwise coprime unordered triples of divisors.
Cf. A007360, A067824, A087087, A225520, A324837, A325683, A325859, A326358, A326496, A326675, A333227, A343653, A343655.

fasmax[y_]:=Complement[y,Union@@Most@*Subsets/@y];
Table[Length[fasmax[Select[Subsets[Range[n]],CoprimeQ@@#&]]],{n,15}]

More terms from Bert Dobbelaere, May 04 2021

A196720 Number of subsets of {1..n} (including empty set) such that the pairwise GCDs of elements are not distinct.

Original entry on oeis.org

1, 2, 4, 8, 13, 25, 33, 61, 81, 116, 140, 256, 282, 530, 606, 692, 823, 1551, 1653, 3173, 3391, 3805, 4177, 8049, 8345, 11524, 12508, 15294, 16204, 31692, 32048, 63280, 70834, 77224, 82048, 91686, 93597, 185245, 196109, 212359, 218223, 432495, 436031, 867647

Offset: 0

Alois P. Heinz, Oct 05 2011

nonn

All pairwise GCDs of each subset are equal if there are any.

a(n) >= A084422(n).

			a(5) = 25: {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}, {1,2,3}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,5}, {3,4,5}, {1,2,3,5}, {1,3,4,5}.

Alois P. Heinz, Table of n, a(n) for n = 0..60

Cf. A143823, A196719, A196721, A196722, A196723, A196724.

b:= proc(n, s) local sn, m;
      m:= nops(s);
      sn:= [s[], n];
      `if`(n<1, 1, b(n-1, s) +`if`(1 >= nops(({seq(seq(
           igcd(sn[i], sn[j]), j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))
    end:
a:= proc(n) option remember;
      b(n-1, [n]) +`if`(n=0, 0, a(n-1))
    end:
seq(a(n), n=0..20);

b[n_, s_] := b[n, s] = With[{m = Length[s], sn = Append[s, n]}, If[n<1, 1, b[n-1, s] + If[1 >= Length[ Union @ Flatten @ Table[ Table[ GCD[ sn[[i]], sn[[j]]], {j, i+1, m+1}], {i, 1, m}]], b[n-1, sn], 0]]];
a[n_] := a[n] = b[n-1, {n}] + If[n == 0, 0, a[n-1]];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Apr 06 2017, translated from Maple *)

A320436 Irregular triangle read by rows where T(n,k) is the number of pairwise coprime k-subsets of {1,...,n}, 1 <= k <= A036234(n), where a single number is not considered to be pairwise coprime unless it is equal to 1.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 2, 1, 9, 7, 2, 1, 11, 8, 2, 1, 17, 19, 10, 2, 1, 21, 25, 14, 3, 1, 27, 37, 24, 6, 1, 31, 42, 26, 6, 1, 41, 73, 68, 32, 6, 1, 45, 79, 72, 33, 6, 1, 57, 124, 151, 105, 39, 6, 1, 63, 138, 167, 114, 41, 6, 1, 71, 159, 192, 128, 44, 6, 1, 79

Offset: 1

Gus Wiseman, Jan 08 2019

			Triangle begins:
   1
   1   1
   1   3   1
   1   5   2
   1   9   7   2
   1  11   8   2
   1  17  19  10   2
   1  21  25  14   3
   1  27  37  24   6
   1  31  42  26   6
   1  41  73  68  32   6
   1  45  79  72  33   6
   1  57 124 151 105  39   6
   1  63 138 167 114  41   6
   1  71 159 192 128  44   6
   1  79 183 228 157  56   8

Except for the k = 1 column, same as A186974.
Row sums are A320426.
Second column is A015614.
Cf. A051424, A084422, A085945, A187106, A276187, A320423, A320430, A320435.

Table[Length[Select[Subsets[Range[n],{k}],CoprimeQ@@#&]],{n,16},{k,PrimePi[n]+1}]

A324739 Number of subsets of {2...n} containing no element whose prime indices all belong to the subset.

Original entry on oeis.org

1, 2, 3, 6, 10, 20, 30, 60, 96, 192, 312, 624, 936, 1872, 3744, 7488, 12480, 24960, 37440, 74880, 142848, 285696, 456192, 912384, 1548288, 3096576, 5308416, 10616832, 15925248, 31850496, 51978240, 103956480, 200835072, 401670144, 771489792, 1542979584, 2314469376

Offset: 1

Gus Wiseman, Mar 14 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

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

Andrew Howroyd, Table of n, a(n) for n = 1..100

The maximal case is A324762. The case of subsets of {1...n} is A324738. The strict integer partition version is A324750. The integer partition version is A324755. The Heinz number version is A324760. An infinite version is A324694.
Cf. A000720, A001221, A001462, A007097, A084422, A085945, A112798, A276625, A279861, A290689, A290822, A304360, A306844.
Cf. A324695, A324696, A324736, A324737, A324741, A324742, A324744, A324764.

Table[Length[Select[Subsets[Range[2,n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]],{n,10}]

pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019

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

A343653 Number of non-singleton pairwise coprime nonempty sets of divisors > 1 of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 1, 0, 0, 2, 0, 2, 1, 1, 0, 3, 0, 1, 0, 2, 0, 7, 0, 0, 1, 1, 1, 4, 0, 1, 1, 3, 0, 7, 0, 2, 2, 1, 0, 4, 0, 2, 1, 2, 0, 3, 1, 3, 1, 1, 0, 13, 0, 1, 2, 0, 1, 7, 0, 2, 1, 7, 0, 6, 0, 1, 2, 2, 1, 7, 0, 4, 0, 1, 0, 13, 1, 1

Offset: 1

Gus Wiseman, Apr 25 2021

nonn

First differs from A066620 at a(210) = 36, A066620(210) = 35.

			The a(n) sets for n = 6, 12, 24, 30, 36, 60, 72, 96:
  {2,3}  {2,3}  {2,3}  {2,3}    {2,3}  {2,3}    {2,3}  {2,3}
         {3,4}  {3,4}  {2,5}    {2,9}  {2,5}    {2,9}  {3,4}
                {3,8}  {3,5}    {3,4}  {3,4}    {3,4}  {3,8}
                       {5,6}    {4,9}  {3,5}    {3,8}  {3,16}
                       {2,15}          {4,5}    {4,9}  {3,32}
                       {3,10}          {5,6}    {8,9}
                       {2,3,5}         {2,15}
                                       {3,10}
                                       {3,20}
                                       {4,15}
                                       {5,12}
                                       {2,3,5}
                                       {3,4,5}

The case of pairs is A089233.
The version with 1's, empty sets, and singletons is A225520.
The version for subsets of {1..n} is A320426.
The version for strict partitions is A337485.
The version for compositions is A337697.
The version for prime indices is A337984.
The maximal case with 1's is A343652.
The version with empty sets is a(n) + 1.
The version with singletons is A343654(n) - 1.
The version with empty sets and singletons is A343654.
The version with 1's is A343655.
The maximal case is A343660.
A018892 counts pairwise coprime unordered pairs of divisors.
A048691 counts pairwise coprime ordered pairs of divisors.
A048785 counts pairwise coprime ordered triples of divisors.
A051026 counts pairwise indivisible subsets of {1..n}.
A100565 counts pairwise coprime unordered triples of divisors.
A305713 counts pairwise coprime non-singleton strict partitions.
A343659 counts maximal pairwise coprime subsets of {1..n}.
Cf. A007359, A067824, A074206, A076078, A084422, A187106, A285572, A324837, A326675, A327516, A338315.

Table[Length[Select[Subsets[Rest[Divisors[n]]],CoprimeQ@@#&]],{n,100}]

A087080 Number of elements in the coprime subsets of the integers 1 to n.

Original entry on oeis.org

0, 1, 4, 12, 20, 52, 60, 148, 196, 300, 332, 780, 828, 1904, 2080, 2348, 2812, 6352, 6608, 14736, 15632, 17456, 18640, 41152, 42432, 60912, 64800, 80928, 85408, 186304, 187584, 406400, 457344, 497472, 523456, 585280, 596288, 1284224, 1348032, 1457792, 1495424

Offset: 0

Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003

nonn

A coprime set of integers has (m,n)=1 for each pair of integers in the set.

			a(4)=20 since the 12 coprime subsets of (1,2,3,4) are ( ) (1) (2) (3) (4) (1,2) (1,3) (1,4) (2,3) (3,4) (1,2,3) (1,3 4) and these contain 20 elements.

Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication.

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

A087077 gives the number of elements in the primitive subsets. A084422 gives the number coprime subsets. A087081 gives the sum of the elements in coprime subsets.

iscoprime(v) = {local(i); for (i=1, #v-1, for (j=i+1, #v, if (gcd(v[i], v[j]) != 1, return (0)););); return (1);}
a(n) = {sn = vector(n, i, i); pset = vector(1<<#sn, i, vecextract(sn, i-1)); nb = 0; for (i=1, #pset, if (iscoprime(pset[i]), nb += #pset[i]);); return (nb);} \\ Michel Marcus, Jul 12 2013

Terms a(38) and beyond from Fausto A. C. Cariboni, Oct 20 2020

A087081 Sum of the elements in the coprime subsets of the integers 1 to n.

Original entry on oeis.org

0, 1, 6, 24, 48, 156, 192, 580, 836, 1444, 1660, 4596, 4980, 13184, 14768, 17308, 21756, 55888, 58768, 146416, 157552, 181008, 196304, 481664, 500096, 765648, 825152, 1073920, 1148288, 2745728, 2768768, 6505728, 7453952, 8233792, 8736960, 9984832, 10208064

Offset: 0

Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003

nonn

A coprime set of integers has (m,n)=1 for each pair of integers in the set.

			a(4)=48 since the 12 coprime subsets of (1,2,3,4) are ( ) (1) (2) (3) (4) (1,2) (1,3) (1,4) (2,3) (3,4) (1,2,3) (1,3 4) and the sum of the elements is 48.

Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication.

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

A087078 gives the sum of the elements in the primitive subsets. A084422 gives the number coprime subsets. A087080 gives the number of elements in coprime subsets.

Terms a(35) and beyond from Fausto A. C. Cariboni, Oct 20 2020

A270970 Number of subsets of {1,...,n} with sum of elements equal to least common multiple of elements.

Original entry on oeis.org

1, 2, 4, 5, 6, 8, 9, 11, 14, 16, 17, 21, 22, 24, 28, 31, 32, 37, 38, 53, 56, 57, 58, 71, 72, 73, 77, 85, 86, 131, 132, 138, 141, 142, 143, 163, 164, 165, 167, 289, 290, 310, 311, 316, 403, 404, 405, 454, 455, 458, 460, 463, 464, 478, 479, 557, 559, 560, 561

Offset: 1

Michel Marcus, Mar 27 2016

nonn

Similar to A270875 but also counts singletons, the trivial solutions.

Hiroaki Yamanouchi, Table of n, a(n) for n = 1..200

Cf. A084422, A270875.

Table[Length@ Select[Rest@ Subsets@ Range@ n, Total@ # == LCM @@ # &], {n, 22}] (* Michael De Vlieger, Mar 27 2016 *)

a(n) = {nb = 0; S = vector(n, k, k); for (i = 0, 2^n - 1, ss = vecextract(S, i); if (sum(k=1, #ss, ss[k]) == lcm(ss), nb++);); nb;}

a(n) = A270875(n) + n.

a(31)-a(58) from Hiroaki Yamanouchi, Mar 30 2016

A355146 Triangle read by rows: T(n,k) is the number of subsets of {1,...,n} of cardinality k in which every pair of elements is coprime; n >= 0, 0 <= k <= A036234(n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 2, 1, 5, 9, 7, 2, 1, 6, 11, 8, 2, 1, 7, 17, 19, 10, 2, 1, 8, 21, 25, 14, 3, 1, 9, 27, 37, 24, 6, 1, 10, 31, 42, 26, 6, 1, 11, 41, 73, 68, 32, 6, 1, 12, 45, 79, 72, 33, 6, 1, 13, 57, 124, 151, 105, 39, 6, 1, 14, 63, 138, 167, 114, 41, 6

Offset: 0

Marcel K. Goh, Jun 27 2022

For n >= 1, the alternating row sums equal 0.

			Triangle T(n,k) begins:
  n/k 0  1  2  3  4  5 6
  0   1
  1   1  1
  2   1  2  1
  3   1  3  3  1
  4   1  4  5  2
  5   1  5  9  7  2
  6   1  6 11  8  2
  7   1  7 17 19 10  2
  8   1  8 21 25 14  3
  9   1  9 27 37 24  6
  10  1 10 31 42 26  6
  11  1 11 41 73 68 32 6
  12  1 12 45 79 72 33 6
  ...
For n=8 and k=5 the T(8,5)=3 sets are {1,2,3,5,7}, {1,3,4,5,7}, and {1,3,5,7,8}.

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

Row sums give A084422.

Cf. A000720, A036234, A186974, A320436.

cp's OEIS Frontend

A343654 Number of pairwise coprime sets of divisors > 1 of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A343659 Number of maximal pairwise coprime subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A196720 Number of subsets of {1..n} (including empty set) such that the pairwise GCDs of elements are not distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A320436 Irregular triangle read by rows where T(n,k) is the number of pairwise coprime k-subsets of {1,...,n}, 1 <= k <= A036234(n), where a single number is not considered to be pairwise coprime unless it is equal to 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A324739 Number of subsets of {2...n} containing no element whose prime indices all belong to the subset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A343653 Number of non-singleton pairwise coprime nonempty sets of divisors > 1 of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A087080 Number of elements in the coprime subsets of the integers 1 to n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A087081 Sum of the elements in the coprime subsets of the integers 1 to n.

Views

Author

Keywords

Comments

Examples

References