|
|
A087080
|
|
Number of elements in the coprime subsets of the integers 1 to n.
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A coprime set of integers has (m,n)=1 for each pair of integers in the set.
|
|
REFERENCES
|
Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication.
|
|
LINKS
|
|
|
EXAMPLE
|
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.
|
|
PROG
|
(PARI) 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
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|