A077150 Number of composite numbers between n and 2n that are coprime to n.

0, 0, 1, 0, 3, 0, 4, 2, 3, 0, 7, 0, 9, 3, 4, 3, 12, 2, 14, 4, 7, 4, 17, 2, 14, 6, 11, 5, 22, 1, 23, 9, 13, 8, 16, 3, 27, 9, 15, 6, 31, 2, 33, 11, 14, 12, 37, 7, 32, 10, 21, 12, 41, 6, 27, 11, 22, 14, 45, 3, 48, 18, 24, 19, 35, 6, 53, 19, 30, 9, 56, 10, 59, 23, 26

Offset

1,5

Comments

It can be proved that 12 is the largest number n such that a(n) = 0.

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Formula

a(n) = phi(n) + Pi(n) - Pi(2n). - Charles R Greathouse IV, May 18 2011

Example

a(5) = 3 as there are 3 coprime (to 5) composite numbers between 5 and 10, i.e., 6, 8 and 9.

Maple

A077150 := proc(n) local k, s: s:=0: for k from n+1 to 2*n-1 do if(not isprime(k) and gcd(k, n)=1)then s:=s+1: fi: od: return s: end: seq(A077150(n), n=1..100); # Nathaniel Johnston, May 18 2011

Prog

(PARI) for(k=1, 100, s=0:for(n=k+1, 2*k-1, if(!isprime(n), if(gcd(n, k)==1, s=s+1))):print1(s", "))
(PARI) a(n)=eulerphi(n)+primepi(n)-primepi(2*n) \\ Charles R Greathouse IV, May 18 2011

Crossrefs

Sequence in context: A081170 A201291 A272192 * A065453 A152770 A098601

Adjacent sequences: A077147 A077148 A077149 * A077151 A077152 A077153

Keyword

nonn,easy

Author

Amarnath Murthy, Oct 30 2002

Extensions

More terms from Ralf Stephan, Mar 18 2003

Status

approved