A074398 Number of primes between n and phi(n), with neither n nor phi(n) included in the count in case they are primes.

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

Offset: 1

Author

Joseph L. Pe, Sep 24 2002

Keywords

• nonn
• look

Examples

			phi(6) = 2 and there are 2 primes between 2 and 6 (endpoints are excluded), namely 3, 5. Hence a(6) = 2.
		

Links

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

Crossrefs

Cf. A000010, A000720, A010051, A085342.

Programs

Mathematica

(*gives number of primes < n*) f[n_] := Module[{r, i}, r = 0; i = 1; While[Prime[i] < n, i++ ]; i - 1]; (*gives number of primes between m and n with endpoints excluded*) g[m_, n_] := Module[{r}, r = f[m] - f[n]; If[PrimeQ[n], r = r - 1]; r]; Table[g[n, EulerPhi[n]], {n, 1, 100}]
(* Second program: *)
Array[PrimePi@ # - PrimePi@ EulerPhi@ # - Boole@ PrimeQ@ # &, 96] (* or *) Array[Count[Range[EulerPhi@ # + 1, # - 1], ?PrimeQ] &, 96] (* _Michael De Vlieger, Dec 16 2017 *)

PARI

A074398(n) = (primepi(n) - primepi(eulerphi(n)) - isprime(n)); \\ Antti Karttunen, Dec 16 2017

Formula

a(n) = A085342(n) - A010051(n) = A000720(n) - A000720(A000010(n)) - A010051(n). - Antti Karttunen, Dec 16 2017

Extensions

Name clarified by Antti Karttunen, Dec 16 2017