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

Author

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

Keywords

• nonn

Comments

A coprime set of integers has (m,n)=1 for each pair of integers in the set.

Examples

			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.
		

References

• Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication.

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 0..120

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.

Programs

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

Extensions

Terms a(38) and beyond from Fausto A. C. Cariboni, Oct 20 2020