OFFSET
1,1
COMMENTS
Maximal solution is either k=2p or, in the case of Mersenne primes M, k=2(M+1) and f(k)=p or f(k)=M.
EXAMPLE
k = 192: phi(192) = 64, cototient(192) = 128, k - phi(192) - 1 = 127 is prime;
k = 2p: 2p - phi(2p) - 1 = 2p - p + 1 - 1 = p, so 2*prime is always a solution;
k = 2^(q+1), where q is a Mersenne prime exponent: cototient(k) - 1 = 2^(p+1) - 2^p - 1 = 2^p - 1, which is the corresponding Mersenne prime.
Numbers k in {192, 224, 248, 254, 256} give p = 127;
numbers k in {72, 80, 88, 92, 94} give p = 47.
MATHEMATICA
Do[s=n-EulerPhi[n]-1; If[PrimeQ[s], Print[n, s]], n, 1, 10000]
Select[Range[250], PrimeQ[#-EulerPhi[#]-1]&] (* Harvey P. Dale, Sep 05 2023 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Labos Elemer, Apr 26 2002
STATUS
approved