Recently I have been studying primes of various forms (and those forms are number theoretic and special functions). Let $\pi_{f(x)}(n)$ denote the number of primes less than $n$ which are of the form $f(x)$ for some $x\in\Bbb{Z}$. I first studied the function $\pi_{\phi(x)}(n)$. Few primes of such form occur. Here is a table of $\pi_{\phi(x)}(n)$: \begin{array}{|c|c|} \hline n&\pi_{\phi(x)}(n)\\ \hline 100&3\\ \hline 1000&3\\ \hline 10000&3\\ \hline 100000&3\\ \hline 1000000&3\\ \hline 10000000&3\\ \hline \end{array} I noticed that for all $10000000\ge n\ge6$, $\pi_{\phi(x)}(n)=3$. So I conjectured that $$\forall n\geq6,\,\,\pi_{\phi(x)}(n)=3$$ is this conjecture true?
Note: The software I used for these computations is pari/gp.

  • 1
    $\begingroup$ Failure to note that phi(n) is even for all $n\geq 3$ indicates that more thought should have been put into this question/conjecture before asking it on MathOverflow $\endgroup$ – Yemon Choi Nov 25 '20 at 2:28

Assuming $\phi(x)$ is referring to Euler's totient function, note $\phi(1) = \phi(2) = 1$ and it's always even for all $x \ge 3$. This is because of the totient function's multiplicative nature, with all odd primes having an even totient value, and $2$ or more factors of $2$ also having an even totient function.

Thus, $\phi(x)$ can only be a prime $\ge 2$ when it's $2$. This only happens when $x$ has just one factor of $3$, a factor of $3$ and a factor of $2$, or $2$ factors of $2$. Thus, this means it only occurs for the $3$ values of $x \in \{3, 4, 6\}$.

However, as the question says it's looking for the number of primes of the form $\phi(x)$ which are less than $n$, then for all $n \ge 3$, using the standard definition of what are prime numbers, the answer would be $1$ (i.e., prime $2$). If $1$ is considered to be a prime (as the OP states in a comment below), the result would then be $2$ instead.

  • $\begingroup$ Oh, I forgot that simple fact :P. Thanks. $\endgroup$ – Leonhard Euler Nov 24 '20 at 6:45
  • 3
    $\begingroup$ There are only two such primes, $2,3$. So, $\pi_{\phi(x)}(n)$ should be equal to $2$. I think $1$ was considered to be a prime. $\endgroup$ – Alapan Das Nov 24 '20 at 6:54
  • 2
    $\begingroup$ @epic_math You're welcome. As Alapan Das indicated, there is actually only one prime of the form $\phi(x)$, i.e., $2$ (or, if you consider $1$ to be a prime, then $2$). It seems you're actually counting the number of $x$ for which $\phi(x)$ is a prime, which is technically not quite the same thing as what you wrote in your question. $\endgroup$ – John Omielan Nov 24 '20 at 7:01
  • $\begingroup$ @AlapanDas oh yes, my software considered 1 to be a prime. $\endgroup$ – Leonhard Euler Nov 24 '20 at 7:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.