I would like to search for primes of the form $$\varphi(n)^n+n$$ where $\ \varphi(n)\ $ denotes the totient function.
The problem is that neither pfgw nor factordb seems to support the totient-function.
Is there some trick allowing to determine the totient-function with some other functions that are supported by pfgw ?
With PARI/GP, I calculated the positive integers $n$, such that the above expression is prime. These are $\ 1,2,3,187\ $ and no other below $\ 3\ 000\ $
Best Answer
The totient function of an integer $n$ with prime factorisation $\prod \limits_{k=1}^r p_k^{\alpha_k}$ is given by $\varphi(n) = \prod \limits_{k=1}^r p_k^{\alpha_k-1}(p_k-1)$. This allows you to determine the totient based off a prime factorisation, and furthermore also tells you that $n$ cannot have a square factor since if $p^2$ divides $n$ then $p$ divides $\varphi(n)$, and so we now have $\varphi(n) = \prod \limits_{k=1}^r (p_k-1)$ where $n$ is a product of distinct primes.