A087077 -id:A087077 - cp's OEIS frontend

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

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

A087078 Sum of the elements in the primitive subsets of the integers 1 to n.

Original entry on oeis.org

0, 1, 3, 11, 22, 73, 115, 341, 545, 1141, 1864, 4849, 6505, 16285, 26245, 47093, 68981, 163937, 221957, 517937, 726737, 1312865, 2093745, 4753105, 5953777, 12335601, 19516365, 34112821, 48603289, 107522689, 137759953, 302797921, 422868865

Offset: 0

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

nonn

A primitive set has no element that divides another element in the same set.

			a(4)=22 since the primitive subsets of (1,2,3,4) are ( ) (1) (2) (3) (4) (2,3) (3,4) and the sum of the elements in these subsets is 22.

R. K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, New York, (1994).

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..64
Eric Weisstein's World of Mathematics, Primitive Sequence.

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

A355145 Triangle read by rows: T(n,k) is the number of primitive subsets of {1,...,n} of cardinality k; n>=0, 0<=k<=ceiling(n/2).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 1, 4, 2, 1, 5, 5, 2, 1, 6, 7, 3, 1, 7, 12, 10, 3, 1, 8, 16, 15, 5, 1, 9, 22, 26, 13, 2, 1, 10, 28, 38, 22, 4, 1, 11, 37, 66, 60, 26, 4, 1, 12, 43, 80, 76, 35, 6, 1, 13, 54, 123, 156, 111, 41, 6, 1, 14, 64, 161, 227, 180, 74, 12

Offset: 0

Marcel K. Goh, Jun 20 2022

A set is primitive if it does not contain distinct i and j such that i divides j.

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

			Triangle T(n,k) begins:
   n/k 0  1  2  3  4  5  6  7  8  9 10 11 12
    0  1
    1  1  1
    2  1  2
    3  1  3  1
    4  1  4  2
    5  1  5  5  2
    6  1  6  7  3
    7  1  7 12 10  3
    8  1  8 16 15  5
    9  1  9 22 26 13  2
   10  1 10 28 38 22  4
   11  1 11 37 66 60 26  4
   12  1 12 43 80 76 35  6
   ...
For n=6 and k=3 the T(6,3) = 3 primitive sets are {2,3,5}, {3,4,5}, and {4,5,6}.

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

Columns k=0..2 give: A000012, A000027, A161664.
Row sums give A051026.
T(2n,n) gives A174094.
T(2n-1,n) gives A192298 for n>=1.
Cf. A087077, A087086.

Sum_{k=1..ceiling(n/2)} k * T(n,k) = A087077(n). - Alois P. Heinz, Jun 24 2022

cp's OEIS Frontend

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

A087078 Sum of the elements in the primitive subsets of the integers 1 to n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A355145 Triangle read by rows: T(n,k) is the number of primitive subsets of {1,...,n} of cardinality k; n>=0, 0<=k<=ceiling(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula