Values taken by Euler's phi function

What are the values taken by Euler's phi function? For example, one can show that $\varphi(n)$ is even for $n \neq 1$ or $2$ by reducing the equality $\displaystyle n= \sum\limits_{d|n} \varphi(d)$ modulo $2$; so $\varphi (\mathbb{N}^*) \subset 2\mathbb{N} \cup \{1\}$ (in fact, strictly included; see for example here).

Do we know exactly $\varphi(\mathbb{N}^*)$?

Solution 1:

This is a rather difficult question in general. I believe the closest results to what you are looking for were obtained by Kevin Ford in the first of his two landmark papers in this area: “The distribution of totients,” Ramanujan J. (1998) and “The number of solutions of $\phi(x) = m$,” Annals of Math. (1999). Both are available on his web page. To paraphrase Theorem 12 from Ford's paper, most numbers in $\varphi(\mathbb N)$ have an unusually high number of prime factors.

That isn't too surprising, given that most prime powers $p^k \mid\mid n$ induce at least $k+1$ prime factors in $\varphi(n)$, since $p-1$ has at least $2$ factors (for $p \ge 5$). But there is a surprisingly precise estimate for how many extra factors one gets this way.

If $\Omega(n)$ counts the number of prime divisors of $n$ with multiplicity (e.g. $\Omega(2^3\cdot 5) = 4$), it is well-known that for a typical integer, $\Omega(n) \approx \log \log n$ (see Hardy-Ramanujan or the beautiful Erdős-Kac theorem). However, a typical $m \in \varphi(\mathbb N)$ satisfies $$\Omega(m) \approx 2.186263 \log \log m,$$ where the constant (presumably transcendental) is equal to $(1-\varrho)^{-1}$ with $\varrho$ being the unique positive root of the power series $\sum_{n=0}^\infty ((n+1)\log(n+1)-n\log n-1) x^n$.

The above statement should indicate to you two things: that the structure of the set $\varphi(\mathbb N)$ is probably far from trivial, and also that it is somewhat thin, since it consists mostly of atypical integers. Indeed, the main theorem of the paper (Theorem 1) gives the precise order of magnitude of the counting function $V(x) := \#\{n \le x : n \in \varphi(\mathbb N)\}$. Up to some multiplicative constants,

$$V(x) \asymp \frac{x}{\log x} \exp(C(\log \log \log x - \log \log \log \log x)^2 + D(\log \log \log x) - (D + 1/2 - 2C) \log \log \log \log x),$$

where $C \approx 0.8178146$ and $D \approx 2.1769687$ also arise from the above power series. Stating this intimidating formula less precisely, we could also say $$V(n) = \frac{n}{\log n} \exp(C_n \log \log \log^2 n),$$ where $C_n \to C$.

So the numbers appearing in $\varphi(\mathbb N)$ are a little bit more common than primes. As is typical in probabilistic number theory, these phenomena tend to be extremely hard to witness experimentally, since $\log \log \log n$ grows so slowly (and with great dignity).

Solution 2:

(Assuming the question will be corrected to indicate even for $\phi$)

The concept you are discussing is referred to as a nontotient number. All odd numbers $\gt 1$ are nontotient and so are some of the even numbers.

There is a set of necessary conditions which reduce the candidates that are even nontotients but the number of conditions varies with the number. For example, since $\phi (p) = p-1$, a nontotient is not one less than a prime ($\phi + 1$ not prime). Since $\phi (3p) = 2(p-1)$, a nontotient cannot be twice a number one less than a prime ($\frac{\phi}2 + 1$ not prime). You can continue creating conditions to cover the forms of all semi-primes with small factors and beyond.

So, as far as I know, just like the primes you can narrow the candidates fairly quickly using the small primes, but the exact values which are cototient require a bit of testing on each one.

Solution 3:

You are wrong. It can be shown that $\varphi(p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}) = p_1^{k_1 - 1} (p_1 - 1) p_2^{k_2 - 1} (p_2 - 1) \ldots p_r^{k_r - 1} (p_r - 1)$ if that is the prime decomposition of the number. If $n$ is divisible by 4, $\varphi(n)$ is even. If $n$ is divisible by an odd prime, $\varphi(n)$ is even. So only $\varphi(1) = \varphi(2) = 1$ are odd.