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-5 of 5 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)
		

Crossrefs

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.

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

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

Original entry on oeis.org

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

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. A single number is not considered to be pairwise coprime unless it is equal to 1.

Examples

			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}}
		

Crossrefs

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]],CoprimeQ@@#&],Range[n]]],{n,10}]

Extensions

a(17)-a(18) from Alois P. Heinz, Jan 17 2019
a(19)-a(30) from Christian Sievers, Nov 28 2024

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.

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

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

A333517 Number of set partitions of {1, 2, ..., n} such that, for any two numbers in the same part, one divides the other.

Original entry on oeis.org

1, 1, 2, 3, 7, 9, 25, 30, 78, 138, 342, 386, 1307, 1448, 3406, 6818, 18907, 20478, 65901, 70781, 213704, 397874, 885118, 939377, 3624495, 5034048, 11032794, 20966732, 59398560, 62307000, 225641196, 235937708, 682530590, 1183122260, 2540294162, 4026533578, 15943721982, 16555409210, 35301649136, 59929463166
Offset: 0

Views

Author

Robert Dougherty-Bliss, Mar 26 2020

Keywords

Comments

a(n) <= A000110(n) for all n since a(n) counts set partitions.
a(n) >= n for all n, since the singletons form a suitable partition and separately moving 1 into each set creates n - 1 new suitable partitions.

Examples

			For n = 3, the suitable partitions are {{1}, {2}, {3}}, {{1, 3}, {2}}, and {{1, 2}, {3}}, so a(3) = 3.
		

Crossrefs

Programs

  • Maple
    g:= proc(n, s) `if`(n<2, 1+nops(s),
          b(n, sort(map(i-> `if`(isprime(i), 1, i), s))))
        end:
    b:= proc(n, s) option remember; add(`if`(irem(s[j], n)>0, 0,
          g(n-1, subsop(j=n, s))), j=1..nops(s))+g(n-1, [s[], n])
        end:
    a:= n-> g(n, []):
    seq(a(n), n=0..28);  # Alois P. Heinz, Mar 26 2020
  • Mathematica
    g[n_, s_] := If[n<2, 1+Length[s], b[n, Sort[If[PrimeQ[#], 1, #]& /@ s]]];
    b[n_, s_] := b[n, s] = Sum[If[Mod[s[[j]], n] > 0, 0, g[n-1, ReplacePart[s, j -> n]]], {j, 1, Length[s]}] + g[n-1, Append[s, n]];
    a[n_] := g[n, {}];
    a /@ Range[0, 28] (* Jean-François Alcover, Nov 14 2020, after Alois P. Heinz *)

Extensions

a(25)-a(39) from Alois P. Heinz, Mar 26 2020
Showing 1-5 of 5 results.