cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-8 of 8 results.

A276187 Number of subsets of {1,..,n} of cardinality >= 2 such that the elements of each counted subset are pairwise coprime.

Original entry on oeis.org

0, 1, 4, 7, 18, 21, 48, 63, 94, 105, 220, 235, 482, 529, 600, 711, 1438, 1501, 3020, 3211, 3594, 3849, 7720, 7975, 11142, 11877, 14628, 15459, 30946, 31201, 62432, 69855, 76126, 80221, 89820, 91611, 183258, 192601, 208600, 214231, 428502, 431573, 863188, 900563
Offset: 1

Views

Author

Robert C. Lyons, Aug 23 2016

Keywords

Comments

n is prime if and only if a(n) = 2*a(n-1)+n-1. - Robert Israel, Aug 24 2016

Examples

			From _Gus Wiseman_, May 08 2021: (Start)
The a(2) = 1 through a(6) = 21 sets:
  {1,2}   {1,2}    {1,2}     {1,2}      {1,2}
          {1,3}    {1,3}     {1,3}      {1,3}
          {2,3}    {1,4}     {1,4}      {1,4}
         {1,2,3}   {2,3}     {1,5}      {1,5}
                   {3,4}     {2,3}      {1,6}
                  {1,2,3}    {2,5}      {2,3}
                  {1,3,4}    {3,4}      {2,5}
                             {3,5}      {3,4}
                             {4,5}      {3,5}
                            {1,2,3}     {4,5}
                            {1,2,5}     {5,6}
                            {1,3,4}    {1,2,3}
                            {1,3,5}    {1,2,5}
                            {1,4,5}    {1,3,4}
                            {2,3,5}    {1,3,5}
                            {3,4,5}    {1,4,5}
                           {1,2,3,5}   {1,5,6}
                           {1,3,4,5}   {2,3,5}
                                       {3,4,5}
                                      {1,2,3,5}
                                      {1,3,4,5}
(End)

Links

Crossrefs

Cf. A000010, A002088, A018805.
The case of pairs is A015614.
The indivisible instead of coprime version is A051026(n) - n.
Allowing empty sets and singletons gives A084422.
The relatively prime instead of pairwise coprime version is A085945(n) - 1.
Allowing all singletons gives A187106.
Allowing only the singleton {1} gives A320426.
Row sums of A320436, each minus one.
The maximal case is counted by A343659.
The version for sets of divisors is A343655(n) - 1.
A000005 counts divisors.
A186972 counts pairwise coprime k-sets containing n.
A186974 counts pairwise coprime k-sets.
A326675 ranks pairwise coprime non-singleton sets.
Cf. A007360, A063647, A186971, A302696, A305713, A320423, A320430, A326077, A327516, A337485.

Programs

  • Maple
    f:= proc(S) option remember;
    local s, Sp;
    if S = {} then return 1 fi;
    s:= S[-1];
    Sp:= S[1..-2];
    procname(Sp) + procname(select(t -> igcd(t,s)=1, Sp))
end proc:
seq(f({$1..n}) - n - 1, n=1..50); # Robert Israel, Aug 24 2016
  • Mathematica
    f[S_] := f[S] = Module[{s, Sp}, If[S == {}, Return[1]]; s = S[[-1]]; Sp = S[[1;;-2]]; f[Sp] + f[Select[Sp, GCD[#, s] == 1&]]];
Table[f[Range[n]] - n - 1, {n, 1, 50}] (* Jean-François Alcover, Sep 15 2022, after Robert Israel *)
  • PARI
    f(n,k=1)=if(n==1, return(2)); if(gcd(k,n)==1, f(n-1,n*k)) + f(n-1,k)
a(n)=f(n)-n-1 \\ Charles R Greathouse IV, Aug 24 2016
  • Sage
    from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets
def is_coprime(x, y): return gcd(x, y) == 1
max_n = 40
seq = []
for n in range(1, max_n+1):
    P = PairwiseCompatibleSubsets(range(1,n+1), is_coprime)
    a_n = len([1 for s in P.list() if len(s) > 1])
    seq.append(a_n)
print(seq)

Formula

a(n) = A320426(n) - 1. - Gus Wiseman, May 08 2021

Extensions

Name and example edited by Robert Israel, Aug 24 2016

A343655 Number of pairwise coprime sets of divisors of n, where a singleton is not considered pairwise coprime unless it is {1}.

Original entry on oeis.org

1, 2, 2, 3, 2, 6, 2, 4, 3, 6, 2, 10, 2, 6, 6, 5, 2, 10, 2, 10, 6, 6, 2, 14, 3, 6, 4, 10, 2, 22, 2, 6, 6, 6, 6, 17, 2, 6, 6, 14, 2, 22, 2, 10, 10, 6, 2, 18, 3, 10, 6, 10, 2, 14, 6, 14, 6, 6, 2, 38, 2, 6, 10, 7, 6, 22, 2, 10, 6, 22, 2, 24, 2, 6, 10, 10, 6, 22, 2
Offset: 1

Views

Author

Gus Wiseman, Apr 26 2021

Keywords

Comments

First differs from A015995 at a(210) = 88, A015995(210) = 86.

Examples

			For example, the a(n) subsets for n = 1, 2, 4, 6, 8, 12, 16, 24 are:
  {1}  {1}    {1}    {1}      {1}    {1}      {1}     {1}
       {1,2}  {1,2}  {1,2}    {1,2}  {1,2}    {1,2}   {1,2}
              {1,4}  {1,3}    {1,4}  {1,3}    {1,4}   {1,3}
                     {1,6}    {1,8}  {1,4}    {1,8}   {1,4}
                     {2,3}           {1,6}    {1,16}  {1,6}
                     {1,2,3}         {2,3}            {1,8}
                                     {3,4}            {2,3}
                                     {1,12}           {3,4}
                                     {1,2,3}          {3,8}
                                     {1,3,4}          {1,12}
                                                      {1,24}
                                                      {1,2,3}
                                                      {1,3,4}
                                                      {1,3,8}

Crossrefs

The case of pairs is A063647.
The case of triples is A066620.
The version with empty sets and singletons is A225520.
A version for prime indices is A304711.
The version for strict integer partitions is A305713.
The version for subsets of {1..n} is A320426 = A276187 + 1.
The version for binary indices is A326675.
The version for integer partitions is A327516.
The version for standard compositions is A333227.
The maximal case is A343652.
The case without 1's is A343653.
The case without 1's with singletons is A343654.
The maximal case without 1's 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.
A325683 counts maximal Golomb rulers.
A326077 counts maximal pairwise indivisible sets.
Cf. A007360, A062319, A067824, A076078, A084422, A187106, A282935, A285572, A304709, A320423, A337485, A343659.

Programs

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

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

Original entry on oeis.org

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

Views

Author

Gus Wiseman, Apr 26 2021

Keywords

Comments

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

Examples

			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}

Crossrefs

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.

Programs

  • Mathematica
    pwcop[y_]:=And@@(GCD@@#1==1&)/@Subsets[y,{2}];
Table[Length[Select[Subsets[Rest[Divisors[n]]],pwcop]],{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

Views

Author

Gus Wiseman, Jan 08 2019

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

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

Programs

  • Mathematica
    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}]

Extensions

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

Views

Author

Gus Wiseman, Jan 08 2019

Keywords

Examples

			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

Crossrefs

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.

Programs

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

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

Views

Author

Gus Wiseman, Jan 08 2019

Keywords

Comments

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.

Examples

			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.

Crossrefs

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

Programs

  • Mathematica
    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}]
  • PARI
    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

Extensions

a(13)-a(23) from Alois P. Heinz, Jan 08 2019
a(24)-a(26) from Jinyuan Wang, Mar 02 2025

A319187 Number of pairwise coprime subsets of {1,...,n} of maximum cardinality (A036234).

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 3, 6, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 24, 24, 24, 24, 24, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 72, 72, 72, 72, 72, 72, 72, 72
Offset: 1

Views

Author

Gus Wiseman, Jan 09 2019

Keywords

Comments

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.

Examples

			The a(8) = 3 subsets are {1,2,3,5,7}, {1,3,4,5,7}, {1,3,5,7,8}.

Links

Crossrefs

Rightmost terms of A186974 and A320436.
Run lengths are A053707.
Cf. A015614, A036234, A051424, A085945, A186971, A186972, A186994, A276187, A303139, A320423, A320426.
Cf. A000005, A045948.

Programs

  • Mathematica
    Table[Length[Select[Subsets[Range[n],{PrimePi[n]+1}],CoprimeQ@@#&]],{n,24}] (* see A186974 for a faster program *)
  • PARI
    a(n) = prod(p=1, n, if (isprime(p), logint(n, p), 1)); \\ Michel Marcus, Dec 26 2020

Formula

a(n) = Product_{p prime <= n} floor(log_p(n)).
a(n) = A000005(A045948(n)). - Ridouane Oudra, Sep 02 2019

A320438 Irregular triangle read by rows where T(n,k) is the number of set partitions of {1,...,n} with all block-sums equal to d, where d is the k-th divisor of n*(n+1)/2 that is >= n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 3, 7, 1, 1, 9, 1, 1, 1, 1, 43, 35, 1, 1, 102, 62, 1, 1, 1, 1, 68, 595, 1, 1, 17, 187, 871, 1480, 361, 1, 1, 2650, 657, 1, 1, 9294, 1, 1, 23728, 1, 1, 27763, 4110, 1, 1, 1850, 25035, 108516, 157991, 7636, 1, 1, 11421, 411474, 1
Offset: 1

Views

Author

Gus Wiseman, Jan 08 2019

Keywords

Examples

			Triangle begins:
    1
    1
    1    1
    1    1
    1    1
    1    1
    1    4    1
    1    3    7    1
    1    9    1
    1    1
    1   43   35    1
    1  102   62    1
    1    1
    1   68  595    1
    1   17  187  871 1480  361    1
    1 2650  657    1
Row 8 counts the following set partitions:
  {{18}{27}{36}{45}}  {{1236}{48}{57}}  {{12348}{567}}  {{12345678}}
                      {{138}{246}{57}}  {{12357}{468}}
                      {{156}{237}{48}}  {{12456}{378}}
                                        {{1278}{3456}}
                                        {{1368}{2457}}
                                        {{1458}{2367}}
                                        {{1467}{2358}}

Crossrefs

Row lengths are A164978. Row sums are A035470.
Cf. A000110, A000258, A008277, A112956, A164977, A275714, A279375, A300335, A320423, A320424, A321455, A321469.

Programs

  • Mathematica
    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]],Total[#]==d&],Range[n]]],{n,12},{d,Select[Divisors[n*(n+1)/2],#>=n&]}]

Extensions

More terms from Jinyuan Wang, Feb 27 2025
Name edited by Peter Munn, Mar 06 2025
Showing 1-8 of 8 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.