A072917 a(n) = p(n) - phi(n), where p(n) is the least prime greater than phi(n).

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 3, 1, 1, 1, 3, 3, 1, 1, 1, 1, 3, 1, 1, 3, 1, 5, 1, 1, 1, 5, 1, 1, 1, 1, 3, 5, 1, 1, 1, 1, 3, 5, 5, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 5, 5, 3, 1, 5, 3, 5, 1, 5, 1, 1, 1, 1, 1, 5, 1, 5, 5, 1, 1, 5, 3, 1, 3, 1, 1, 5, 1, 3, 1, 1, 1, 5, 1, 1, 1, 1

Offset: 1

Author

Joseph L. Pe, Aug 11 2002

Keywords

• easy
• nonn

Examples

			phi(15) = 8 and the least prime > 8 is 11; hence a(15) = 11 - 8 = 3.
		

Links

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

Crossrefs

Cf. A000010, A013632, A072344.

Programs

Mathematica

a[n_] := Module[{r, p}, p = EulerPhi[n]; r = p + 1; While[ ! PrimeQ[r], r = r + 1]; r - p]; Table[a[i], {i, 1, 100}]
lpg[n_]:=Module[{ep=EulerPhi[n]},NextPrime[ep]-ep]; Array[lpg,200] (* Harvey P. Dale, May 29 2017 *)

PARI

A072917(n) = (nextprime(1+eulerphi(n)) - eulerphi(n)); \\ Antti Karttunen, Aug 22 2017

Formula

a(n) = A013632(A000010(n)). - Antti Karttunen, Aug 22 2017