$\sigma_0(n)=\varphi(n)$

Question

$$\sigma_0(n)=\varphi(n)$$ for positive integer $n$. For which $n$ does equality hold? I have found a few numbers $(3, 8, 10, 18 ...)$.

Answer 1

The number of divisors of $n$ is at most $2\sqrt{n}$ while the number of numbers coprime to $n$ is at least equal to the number of primes in the range $(n/2,n)$ (when $n$ is prime the reasoning is different but it is still very much true).

We can give a lower bound on the number of primes in the range $(n/2,n)$ by using lower and upper bounds for the prime counting function, some of which can be found here.

For example, we have that for $x\geq 55$ we have $\frac{x}{\ln(x)+2}< \pi(x) < \frac{x}{\ln(x) - 4}$.

It follows that the number of primes in the range $(n/2,n)$ for $n\geq 110$ is at least $\frac{n}{\ln(n) + 2} - \frac{n/2}{\ln(n/2)-4}$ which we can just bound by $\frac{n}{3\ln(n)}$.

For what values do we have $\frac{n}{3\ln (n)} > 2\sqrt{n}$? It appears for all $n>2109$.

So it follows we must only check all numbers in the range $1,\dots,2109$.

I did this and the only solutions are $1,3,8,10,18,24,30$ (actually I checked up to $10^5$ just in case I was careless in some of the bounds)

Answer 2

The sequence of such $n$ is called A020488. We have exactly the following $7$ values $$ 1, 3, 8, 10, 18, 24, 30. $$ A reason is also given: "This sequence is complete because $\tau(n) < n^{2/3}$ for all $n$ except a few small numbers, whereas $\phi(n) > n/(\exp(\gamma) \cdot \log(\log(n)) + 3/(\log(\log(n)))$ for $n > 2$.