A072344 a(n) = the least natural number k such that k*phi(n) + 1 is prime.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 2, 3, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 1, 1, 1, 1, 3, 1, 3, 2, 1, 1, 3, 3, 1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 2, 2

Offset: 1

Author

Joseph L. Pe, Jul 16 2002

Keywords

• nonn

Examples

			phi(35) = 24 and the least natural number k such that 24 k + 1 is prime is k = 3; so a(35) = 3.
		

Links

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

Crossrefs

Cf. A000010, A034693, A072917.

Programs

Mathematica

f[n_] := Module[{i}, i = 0; While[ ! PrimeQ[i*EulerPhi[n] + 1], i++ ]; i]; Table[f[i], {i, 1, 150}]

PARI

A034693(n) = { my(k=1); while(!isprime(1+(k*n)), k++); k; };
A072344(n) = A034693(eulerphi(n)); \\ Antti Karttunen, Aug 22 2017

Formula

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