Distinct exponents in the factorization of the factorial, a problem of Erdős

Question

In the 1982 paper below, Paul Erdős proved that if $h(n)$ is the number of distinct exponents in the prime factorization of $n!$ then $$c_1\Big(\frac{n}{\log n}\Big)^{1/2} < h(n) < c_2\Big(\frac{n}{\log n}\Big)^{1/2}$$ for all sufficiently large $n$, where $c_1, c_2$ are positive constants. Then he said that "there is no doubt" that $$h(n) = (c + o(1))\Big(\frac{n}{\log n}\Big)^{1/2}$$ as $n$ goes to infinity, for some positive constant $c$, but that "we do not know enough about the difference of consecutive primes" to conclude so.

I wonder if now, after 40 years, "we" know enough to prove Erdős conjecture (?)

• P. Erdős, Miscellaneous problems in number theory, Congressus Numerantium 34 (1982), 25-45. https://users.renyi.hu/~p_erdos/1982-08.pdf

Answer 1

The primes $p \leq \sqrt{n}$ can be ignored as the number of them is $$\approx \sqrt{n} / \log (\sqrt{n} )= 2 \sqrt{n}/\log n = o (1) \cdot \sqrt { n/\log n}$$

For primes $p> \sqrt{n}$, the exponent of $p$ is simply $\lfloor n/p \rfloor$. So an equivalent problem is to count the number of $1 \leq k \leq \lfloor \sqrt{n} \rfloor$ such that the interval $ (n/(k+1), n/k]$ contains a prime.

When $k$ is small, these intervals are very long, and one can prove that all or almost all contain a prime. When $k$ is large, the intervals are very short, and one can prove that few of them contain two primes and then use the prime number theorem to count primes.

The tricky case is the critical range when $k \approx \sqrt{n / \log n}$, say $ \sqrt{n/\log n}/2 < k < 2 \sqrt{n/\log n}$. In this range, the expected proportion of intervals that contain a prime is strictly between $0$ and $1$. To get the exact constant, we would need to estimate this proportion precisely, which seems quite difficult. Doing this by the moment method would require understanding the expected number of primes in the interval, the expected number of pairs of primes, triples, etc. and I don't think we have asymptotics for anything but the expected number and maybe the pairs.

That said, the Cramér random model suggests that $c$ is exactly

$$\int_{0}^{\infty} \left(1 - e^{ - 2/ x^2} \right) dx = \sqrt{2\pi},$$

if I did the calculation right, with the integrand at $x$ being the probability to have a prime in the interval associated to $k = x \sqrt{n/\log n}$.