A problem of Erd\H{o}s and Pomerance \cite{ErPo80}, who proved that\[\max_m f(n,m) \ll n^{3/2}\]and\[n\left(\frac{\log n}{\log\log n}\right)^{1/2} \ll f(n,n)\ll n(\log n)^{1/2}.\]In \cite{Er92c} Erd\H{o}s offered 1000 rupees for a proof of either; for uniform comparison across prizes I have converted this using the 1992 exchange rates.

van Doorn \cite{vD26} has provided an affirmative answer to the second question, proving that, for all large $n$, there exists $m=m(n)$ such that\[f(n,m)-f(n,n) \gg \frac{\log n}{\log\log n}n.\]See also [710].


References


[Er92c] Erd\"{o}s, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50.

[ErPo80] P. Erd\H{o}s and C. Pomerance, Matching the natural numbers up to $n$ with distinct multiples of another interval. Indigationes Math. (1980), 147-151.

[vD26] W. van Doorn, On the length of an interval that contains distinct multiples of the first $n$ positive integers. Integers (2026), #A7.