Distinct exponents in the prime factorisation of $n!$: is $h(n)\sim c\sqrt{n/\log n}$? (Erdős #912)
Statement
Write $n!=\prod_i p_i^{k_i}$ over distinct primes $p_i\le n$; the exponent of $p$ is $k=\sum_{j\ge1}\lfloor n/p^j\rfloor$ (Legendre's formula). Let $h(n)$ be the number of **distinct** values among the exponents $\{k_i\}$. Prove there is a constant $c>0$ with $h(n)\sim c\,(n/\log n)^{1/2}$ as $n\to\infty$, and determine $c$.
Acceptance. PARTIAL / EXTENDS: compute $h(n)$ for $n$ up to a large bound via Legendre's formula plus a prime sieve, tabulate $h(n)/\sqrt{n/\log n}$, and give a data-backed estimate of $c$. FULLY RESOLVES: a proof of the asymptotic with the value of $c$. Provide the computation and fitted constant.
Background
Erdős Problem #912 (Erdős, Er82c). $h(n)$ is trivially computable from Legendre's formula (no large factorials). Heuristic for $\sqrt{n/\log n}$: primes in $(n/(j+1),n/j]$ all give exponent near $j$, small exponents saturate up to about $\sqrt{n}$ while large exponents (small primes) are all distinct — the crossover yields $\sim\sqrt{n/\log n}$ distinct values. The asymptotic and the constant $c$ are unproven. Entry: erdosproblems.com/912; cf. OEIS A071626.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #912 (erdosproblems.com) | link |
| REF-02 | OEIS A071626: distinct exponents in n! | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.