A085945 -id:A085945 - cp's OEIS frontend

A320423 Number of set partitions of {1,...,n} where each block's elements are pairwise coprime.

1, 1, 1, 2, 2, 8, 4, 28, 18, 120, 60, 888, 252, 5220, 1860, 22224, 9552, 311088, 59616, 2473056, 565920, 13627008, 4051872, 235039392, 33805440, 1932037632, 465239808, 20604487680, 4294865664, 386228795904, 35413136640

Offset: 0

Gus Wiseman, Jan 08 2019

Two or more numbers are pairwise coprime if no pair of them has a common divisor > 1. A single number is not considered to be pairwise coprime unless it is equal to 1.

			The a(5) = 8 set partitions:
  {{1},{2,3},{4,5}}
  {{1},{2,5},{3,4}}
   {{1,2},{3,4,5}}
   {{1,4},{2,3,5}}
   {{1,2,3},{4,5}}
   {{1,2,5},{3,4}}
   {{1,3,4},{2,5}}
   {{1,4,5},{2,3}}

Cf. A000110, A051424, A084422, A085945, A186974, A187106, A302569, A302696, A303139, A303140, A320424, A320426, A320430, A320768.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
Table[Length[spsu[Select[Subsets[Range[n]],CoprimeQ@@#&],Range[n]]],{n,10}]

a(17)-a(18) from Alois P. Heinz, Jan 17 2019

a(19)-a(30) from Christian Sievers, Nov 28 2024

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

Original entry on oeis.org

1, 2, 3, 6, 8, 16, 24, 48, 84, 168, 216, 432, 648, 1296, 2448, 4896, 6528, 13056, 19584, 39168, 77760, 155520, 229248, 458496, 790272, 1580544, 3128832, 6257664, 9386496, 18772992, 24081408, 48162816, 95938560, 191877120, 378335232, 756670464, 1135005696, 2270011392

Offset: 1

Gus Wiseman, Mar 13 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.

Also the number of subsets of {2...n} with complement containing no term whose prime indices all belong to the subset.

			The a(1) = 1 through a(6) = 16 subsets:
  {}  {}   {}     {}       {}         {}
      {2}  {3}    {3}      {4}        {4}
           {2,3}  {4}      {5}        {5}
                  {2,3}    {3,5}      {6}
                  {3,4}    {4,5}      {3,5}
                  {2,3,4}  {2,3,5}    {4,5}
                           {3,4,5}    {4,6}
                           {2,3,4,5}  {5,6}
                                      {2,3,5}
                                      {3,4,5}
                                      {3,5,6}
                                      {4,5,6}
                                      {2,3,4,5}
                                      {2,3,5,6}
                                      {3,4,5,6}
                                      {2,3,4,5,6}
An example for n = 15 is {2, 3, 5, 8, 9, 10, 11, 15}. The numbers from 2 to 15 with all prime indices in the subset are {3, 5, 9, 11, 15}, which all belong to the subset, as required.

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

Cf. A000720, A001221, A001462, A007097, A084422, A085945, A112798, A276625, A290689, A290822, A304360, A306844.

Cf. A324697, A324698, A324736, A324738, A324748, A324753, A324755.

Table[Length[Select[Subsets[Range[2,n]],Function[set,SubsetQ[set,Select[Range[2,n],SubsetQ[set,PrimePi/@First/@FactorInteger[#]]&]]]]],{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-1, k, pset(k+1)>>1), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k, b)->if(k>#p, 1, my(t=self()(k+1, b+(1<Andrew Howroyd, Aug 24 2019

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

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

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 4, 4, 6, 6, 8, 8, 16, 16, 16, 16, 16, 16, 32, 32, 40, 40, 52, 52, 64, 64, 72, 72, 144, 144, 176, 176, 200, 200, 232, 232, 464, 464, 464, 464, 536, 536, 1072, 1072, 1072, 1072, 2144, 2144, 2400, 2400, 2400, 2400, 4800, 4800, 4800, 4800, 4800

Offset: 1

Gus Wiseman, Mar 17 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(2) = 1 through a(9) = 6 maximal subsets:
  {2}  {2}  {2,4}  {3,4}    {3,4,6}    {3,4,6}    {3,4,6,8}    {2,4,5,6,8}
       {3}  {3,4}  {2,4,5}  {2,4,5,6}  {3,6,7}    {3,6,7,8}    {2,5,6,7,8}
                                       {2,4,5,6}  {2,4,5,6,8}  {3,4,6,8,9}
                                       {2,5,6,7}  {2,5,6,7,8}  {3,6,7,8,9}
                                                               {4,5,6,8,9}
                                                               {5,6,7,8,9}

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

The non-maximal version is A324739.
The version for subsets of {1...n} is A324744.
An infinite version is A324694.
Cf. A076078, A084422, A085945, A112798, A276625, A304360, A306844.
Cf. A324695, A324738, A324742, A324743, A324763, A324750, A324754, A324755, A324760.

maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[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]));
my(ismax(b)=for(k=1, #p, if(!bittest(b,k) && bitnegimply(p[k], b), my(e=bitor(b, 1<#p, ismax(b), my(f=bitnegimply(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 27 2019

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

A324837 Number of minimal subsets of {1...n} with least common multiple n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 8, 1, 1, 2, 2, 2, 5, 1, 2, 2, 4, 1, 8, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 16, 1, 2, 3, 1, 2, 8, 1, 3, 2, 8, 1, 7, 1, 2, 3, 3, 2, 8, 1, 5, 1, 2, 1, 16, 2, 2

Offset: 1

Gus Wiseman, Mar 19 2019

nonn

Note that the elements must be pairwise indivisible divisors of n.

Differs from A303838 at positions {1, 180, 210, ...}. For example, a(210) = 49, A303838(210) = 55. - Gus Wiseman, Apr 01 2019

			The a(30) = 8 subsets are: {30}, {2,15}, {3,10}, {5,6}, {6,10}, {6,15}, {10,15}, {2,3,5}.

Gus Wiseman, Table of n, a(n) for n = 1..300

Cf. A000005, A006126, A074971, A076078, A085945, A285572, A285573, A286518, A286520, A303837, A303838, A324837.

minim[s_]:=Complement[s,First/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
Table[Length[minim[Select[Rest[stableSets[Divisors[n],Divisible]],LCM@@#==n&]]],{n,100}]

A320430 Number of set partitions of [n] where the elements of each non-singleton block are pairwise coprime.

Original entry on oeis.org

1, 1, 2, 5, 10, 37, 60, 295, 658, 2621, 5368, 38535, 66506, 551529, 1234264, 5004697, 13721836, 143935131, 256835337, 2971237021, 6485081140, 35162930303, 95872321543, 1315397878401, 2399236456202, 25866803180347, 72374386475590, 563368417647305, 1479943119911866

Offset: 0

Gus Wiseman, Jan 08 2019

nonn

Two or more numbers are pairwise coprime if no pair of them has a common divisor > 1.

			The a(4) = 10 set partitions: 1|2|3|4, 14|2|3, 13|2|4, 12|3|4, 1|23|4, 1|2|34, 134|2, 123|4, 14|23, 12|34.

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

Cf. A000110, A000258, A008277, A051424, A085945, A186974, A187106, A302569, A303139, A320424, A320426, A320423, A333517.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
Table[Length[spsu[Select[Subsets[Range[n]],Length[#]==1||CoprimeQ@@#&],Range[n]]],{n,10}]

a(14)-a(15) from Alois P. Heinz, Jan 08 2019
a(16) from Alois P. Heinz, Mar 26 2020
a(17)-a(24) from Giovanni Resta, Mar 27 2020
a(25)-a(28) from Alois P. Heinz, Aug 03 2023

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

A320424 Number of set partitions of {1,...,n} where each block's elements are relatively prime.

Original entry on oeis.org

1, 1, 1, 2, 4, 13, 31, 140, 480, 2306, 9179, 58209, 249205, 1802970, 9463155, 63813439, 389176317, 3415876088, 20506436732, 195865505549, 1353967583125, 12006363947433, 93067012435816, 1019489483393439, 7779097711766093, 86684751695545733, 766357409555622203

Offset: 0

Gus Wiseman, Jan 08 2019

nonn

Two or more numbers are relatively prime if they have no common divisor > 1. A single number is not considered to be relatively prime unless it is equal to 1.

			The a(5) = 13 set partitions:
  {{1},{2,3},{4,5}}
  {{1},{2,5},{3,4}}
   {{1},{2,3,4,5}}
   {{1,2},{3,4,5}}
   {{1,3},{2,4,5}}
   {{1,4},{2,3,5}}
   {{1,5},{2,3,4}}
   {{1,2,3},{4,5}}
   {{1,2,4},{3,5}}
   {{1,2,5},{3,4}}
   {{1,3,4},{2,5}}
   {{1,4,5},{2,3}}
    {{1,2,3,4,5}}
For example, {{1},{2,5},{3,4}} belongs to the list because {1} is relatively prime, {2,5} is relatively prime, and {3,4} is relatively prime. On the other hand, {{1},{2,4},{3,5}} is missing from the list because {2,4} is not relatively prime.

Cf. A000110, A000258, A000837, A008277, A085945, A289508, A289509, A300486, A303139, A320423, A320430.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],And@@(GCD@@#==1&/@#)&]],{n,10}]

lista(nn) = my(m, t=Mat([[], 1]), v, w, z); print1(1); for(n=1, nn, m=Map(); for(i=1, #t~, v=t[i, 1]; if(n-2+sum(j=1, #v, v[j]>1)Jinyuan Wang, Mar 02 2025

a(13)-a(23) from Alois P. Heinz, Jan 08 2019

a(24)-a(26) from Jinyuan Wang, Mar 02 2025

A109511 Number of subsets of the first n numbers having a common divisor greater than 1.

Original entry on oeis.org

0, 1, 2, 4, 5, 10, 11, 19, 23, 40, 41, 79, 80, 145, 164, 292, 293, 577, 578, 1096, 1163, 2188, 2189, 4357, 4373, 8470, 8726, 16924, 16925, 33832, 33833, 66601, 67628, 133165, 133244, 266332, 266333, 528478, 532577, 1056985, 1056986, 2113717

Offset: 1

Reinhard Zumkeller, Jul 01 2005

nonn

			a(6) = #{{2}, {3}, {4}, {5}, {6}, {2,4}, {2,6}, {3,6}, {4,6}, {2,4,6}} = 10.

Alois P. Heinz, Table of n, a(n) for n = 1..2000
Eric Weisstein's World of Mathematics, Inclusion-Exclusion Principle.

Partial sums of A178472.

Cf. A008683, A000225, A085945.

Table[Sum[-MoebiusMu[k] (2^Floor[n/k] - 1), {k, 2, n}], {n, 1, 41}]  (* Geoffrey Critzer, Jan 03 2012 *)

a(n) = sum(k = 2, n, -moebius(k) * (1 << (n\k) - 1)); \\ Amiram Eldar, May 09 2025

a(n) = Sum_{k=2..n} -A008683(k) * (2^floor(n/k)-1).
a(n) = 2^n - A085945(n) - 1 = A000225(n) - A085945(n);
a(n) - a(n-1) = 1 iff n is prime;
a(p^e) = a(p^e - 1) + 2^(p^(e-1) - 1) for p prime, e > 0;
a(p*q) = a(p*q - 1) + 2^(p-1) + 2^(q-1) - 1 for primes p <> q.

A320435 Regular triangle read by rows where T(n,k) is the number of relatively prime k-subsets of {1,...,n}, 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 4, 1, 1, 9, 10, 5, 1, 1, 11, 19, 15, 6, 1, 1, 17, 34, 35, 21, 7, 1, 1, 21, 52, 69, 56, 28, 8, 1, 1, 27, 79, 125, 126, 84, 36, 9, 1, 1, 31, 109, 205, 251, 210, 120, 45, 10, 1, 1, 41, 154, 325, 461, 462, 330, 165, 55, 11, 1, 1, 45, 196

Offset: 1

Gus Wiseman, Jan 08 2019

Two or more numbers are relatively prime if they have no common divisor > 1. A single number is not considered to be relatively prime unless it is equal to 1.

			Triangle begins:
    1
    1    1
    1    3    1
    1    5    4    1
    1    9   10    5    1
    1   11   19   15    6    1
    1   17   34   35   21    7    1
    1   21   52   69   56   28    8    1
    1   27   79  125  126   84   36    9    1
    1   31  109  205  251  210  120   45   10    1
    1   41  154  325  461  462  330  165   55   11    1
    1   45  196  479  786  923  792  495  220   66   12    1
    1   57  262  699 1281 1715 1716 1287  715  286   78   13    1
The T(6,2) = 11 sets are: {1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,3}, {2,5}, {3,4}, {3,5}, {4,5}, {5,6}. Missing from this list are: {2,4}, {2,6}, {3,6}, {4,6}.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Row sums are A085945.
Second column is A015614.
Cf. A000837, A186974, A187106, A289508,  A289509, A300486, A303139, A320424, A320436.

Table[Length[Select[Subsets[Range[n],{k}],GCD@@#==1&]],{n,10},{k,n}]

T(n,k) = sum(d=1, n\k, moebius(d)*binomial(n\d, k)) \\ Andrew Howroyd, Jan 19 2023

T(n,k) = Sum_{d=1..floor(n/k)} mu(d)*binomial(floor(n/d), k). - Andrew Howroyd, Jan 19 2023

cp's OEIS Frontend

A320423 Number of set partitions of {1,...,n} where each block's elements are pairwise coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324762 Number of maximal 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

A324837 Number of minimal subsets of {1...n} with least common multiple n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A320430 Number of set partitions of [n] where the elements of each non-singleton block are pairwise coprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

A320424 Number of set partitions of {1,...,n} where each block's elements are relatively prime.

Views

Author

Keywords