5
$\begingroup$

Let's denote for all $m\geqslant 2$, $N_m$ the number of solutions of

$$\varphi(n)=m$$

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$ is $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}.$$

enter image description here

enter image description here

The question.

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – eyeballfrog Mar 8 '17 at 21:57
  • $\begingroup$ 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. $\endgroup$ – fleablood Mar 8 '17 at 23:59
  • $\begingroup$ Does this high red-dot-pattern hold when you check the red-dot-pattern for divisors or powers of 12? $\endgroup$ – Carlos Toscano-Ochoa Mar 9 '17 at 10:02
  • $\begingroup$ @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}$... $\endgroup$ – E. Joseph Mar 9 '17 at 10:50
  • 2
    $\begingroup$ 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 $\endgroup$ – Gerry Myerson Mar 9 '17 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.