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-6 of 6 results.

A007360 Number of partitions of n into distinct and pairwise relatively prime parts.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 10, 11, 10, 13, 17, 19, 21, 22, 21, 24, 32, 37, 37, 38, 40, 45, 55, 65, 69, 66, 64, 75, 86, 100, 113, 107, 106, 122, 145, 165, 174, 167, 162, 179, 222, 253, 255, 255, 255, 273, 328, 373, 376, 369, 377, 406, 476, 553, 569, 537, 529
Offset: 1

Views

Author

N. J. A. Sloane and Mira Bernstein, following a suggestion from Marc LeBrun

Keywords

Examples

			From _Gus Wiseman_, Sep 23 2019: (Start)
The a(1) = 1 through a(10) = 6 partitions (A = 10):
  (1)  (2)  (3)   (4)   (5)   (6)    (7)   (8)    (9)    (A)
            (21)  (31)  (32)  (51)   (43)  (53)   (54)   (73)
                        (41)  (321)  (52)  (71)   (72)   (91)
                                     (61)  (431)  (81)   (532)
                                           (521)  (531)  (541)
                                                         (721)
(End)

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Number of partitions of n into relatively prime parts = A000837.
The non-strict case is A051424.
Strict relatively prime partitions are A078374.
Cf. A007359, A038348, A084422, A186974, A187106, A303140, A302569, A303362, A304714, A320426, A320436.

Programs

  • Mathematica
    $RecursionLimit = 1000; b[n_, i_, s_] := b[n, i, s] = Module[{f}, If[n == 0 || i == 1, 1, If[i<2, 0, f = FactorInteger[i][[All, 1]]; b[n, i-1, Select[s, #Jean-François Alcover, Mar 20 2014, after Alois P. Heinz *)
Table[Length[Select[IntegerPartitions[n],Length[#]==1||UnsameQ@@#&&CoprimeQ@@Union[#]&]],{n,0,30}] (* Gus Wiseman, Sep 23 2019 *)

Formula

a(n) = A051424(n)-A051424(n-2). - Vladeta Jovovic, Dec 11 2004

Extensions

More precise definition from Vladeta Jovovic, Dec 11 2004
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 13 2005

A320426 Number of nonempty pairwise coprime subsets of {1,...,n}, where a single number is not considered to be pairwise coprime unless it is equal to 1.

Original entry on oeis.org

1, 2, 5, 8, 19, 22, 49, 64, 95, 106, 221, 236, 483, 530, 601, 712, 1439, 1502, 3021, 3212, 3595, 3850, 7721, 7976, 11143, 11878, 14629, 15460, 30947, 31202, 62433, 69856, 76127, 80222, 89821, 91612, 183259, 192602, 208601, 214232, 428503, 431574, 863189
Offset: 1

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) = 8 subsets of {1,2,3,4} are {1}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}. - _Michael B. Porter_, Jan 12 2019
From _Gus Wiseman_, May 09 2021: (Start)
The a(2) = 2 through a(6) = 22 sets:
   {1}     {1}      {1}       {1}        {1}
  {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 case with singletons is A187106.
The version without singletons (except {1}) is A276187.
Row sums of A320436.
The version for divisors > 1 is A343654.
The version for divisors without singletons is A343655.
The maximal version is A343659.
A018892 counts coprime unordered pairs of divisors.
A051026 counts pairwise indivisible subsets of {1...n}.
A087087 ranks pairwise coprime subsets of {1...n}.
A326675 ranks pairwise coprime non-singleton subsets of {1...n}.
Cf. A007359, A007360, A066620, A089233, A100565, A225520, A325683, A326359, A337485, A343652.

Programs

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

Formula

a(n) = A187106(n) - n + 1 = A084422(n) - n.
a(n) = A276187(n) + 1. - Gus Wiseman, May 08 2021

Extensions

a(25)-a(43) from Alois P. Heinz, Jan 08 2019

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

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

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

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

Links

Crossrefs

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

Programs

  • Mathematica
    Table[Length[Select[Subsets[Range[n],{k}],GCD@@#==1&]],{n,10},{k,n}]
  • PARI
    T(n,k) = sum(d=1, n\k, moebius(d)*binomial(n\d, k)) \\ Andrew Howroyd, Jan 19 2023

Formula

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

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

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

Views

Author

Marcel K. Goh, Jun 27 2022

Keywords

Comments

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

Examples

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

Links

Crossrefs

Row sums give A084422.
Cf. A000720, A036234, A186974, A320436.
Showing 1-6 of 6 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.