6
$\begingroup$

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

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$
6
  • $\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$ Mar 8, 2017 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, 2017 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$ Mar 9, 2017 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, 2017 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$ Mar 9, 2017 at 11:04

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .