About the number of solutions of $\varphi(n)=m$

Let's denote $$N_m$$ as the number of solutions of

$$\varphi(n)=m$$

for all $$m\geqslant 2$$,

where $$\varphi$$ is Euler totient function, i.e.

$$N_m:=\#\{n\in \mathbb N,\ \varphi(n)=m\}.$$

We can prove easily that $$N_m=0$$ if $$m$$ is odd.

We also know that $$N_m<\infty$$ for all $$m$$ (thanks to this).

I plotted the sequence $$(N_m)$$, and I putted red points when

$$m\equiv 0\pmod{12}.$$

The question.

Why is every "high" point (i.e. corresponding to a high value of $$N_m$$) a red point?

• 12 has a lot of divisors, as do its multiples. Since $\phi$ is multiplicative, $N_m$ should behave something like $\sum_{d|N_m} N_d N_{N_m/d}$, which means more divisors is better. Mar 8, 2017 at 21:57
• Not only a lot of divisors but divisors close together. $\phi(p^iq^j) = p^{i-1}(p-1)q^{j-1}(q-1)$. the 2s, 3, and 4 could represent primes, or numbers one less than prime in far more ways then most other sets of numbers. 2 is, of course the only number that is both prime and one less than a prime. Mar 8, 2017 at 23:59
• Does this high red-dot-pattern hold when you check the red-dot-pattern for divisors or powers of 12? Mar 9, 2017 at 10:02
• @CarlosToscano-Ochoa I will definitely try that! The issue here is that I have to calculate $\varphi(n)$ for $n$ large since I can only determine $N_m$ until I have computed $\varphi(n)$ for $0\leqslant n\leqslant \sqrt m/2$. My computer crash when I try to computer larger values of $N_m$, and $N_{12^3}$ is already $N_{1728}$... Mar 9, 2017 at 10:50
• Your sequence $N_n$ is tabulated at oeis.org/A058277 (but only the nonzero values), and up to the 10,000th term at oeis.org/A058277/b058277.txt Including the zero terms, it's at oeis.org/A014197 and oeis.org/A014197/b014197.txt Mar 9, 2017 at 11:04

Let $$m\in\Bbb{N}$$ be given, and let $$n\in\Bbb{N}$$ be such that $$\varphi(n)=m$$. If $$m\neq0\pmod{12}$$ then either $$3\nmid m$$ or $$4\nmid m$$. If $$4\nmid m$$ then either $$n=p^k$$ or $$n=2p^k$$ for some prime $$p\equiv3\pmod{4}$$, or $$n=4$$. Similarly, if $$3\nmid m$$ then $$n$$ is a product of primes congruent to $$2\pmod 3$$, or $$3$$ times such a product. Both conditions are quite restrictive, and so $$N_m$$ should be small.