A085342 Number of primes between phi(n) and n, where n is included in the count if it is a prime, while phi(n) is never included in the count even if it is a prime.

0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 3, 2, 2, 1, 4, 1, 4, 3, 4, 1, 5, 1, 4, 2, 4, 1, 6, 1, 5, 3, 5, 2, 6, 1, 5, 3, 6, 1, 8, 1, 6, 5, 6, 1, 9, 2, 7, 4, 6, 1, 9, 4, 7, 5, 7, 1, 11, 1, 8, 7, 7, 3, 10, 1, 8, 5, 10, 1, 11, 1, 10, 9, 10, 4, 12, 1, 11, 6, 10, 1, 14, 5, 10, 7, 11, 1, 15, 4, 10, 7, 10, 4, 13, 1

Offset: 1

Author

Labos Elemer, Jul 10 2003

Keywords

• nonn
• look

Comments

Number of primes in (phi(n), n]. - Charles R Greathouse IV, Dec 26 2013

Examples

			n=12: phi(n)=4, pi(12)-pi(4)=5-2=3.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384

Crossrefs

Cf. A000720, A000010, A010051, A070803, A070804, A074398, A085341-A085347.

Programs

Mathematica

Array[PrimePi[#] - PrimePi@ EulerPhi@ # &, 97] (* Michael De Vlieger, Dec 16 2017 *)

PARI

a(n) = primepi(n) - primepi(eulerphi(n)); \\ Michel Marcus, Dec 26 2013

Formula

a(n) = pi(n) - pi(phi(n)) = A000720(n) - A000720(A000010(n)).

a(n) = A074398(n) + A010051(n). - Antti Karttunen, Dec 16 2017

Extensions

Name clarified by Antti Karttunen, Dec 16 2017