Problem Statement
Let $f(n,m)$ be minimal such that in $(m,m+f(n,m))$ there exist distinct integers $a_1,\ldots,a_n$ such that $k\mid a_k$ for all $1\leq k\leq n$. Prove that\[\max_m f(n,m) \leq n^{1+o(1)}\]and that\[\max_m (f(n,m)-f(n,n))\to \infty.\]
Categories:
Number Theory
Progress
A problem of Erdős and Pomerance [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 [Er92c] Erdő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 [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].
Source: erdosproblems.com/711 | Last verified: January 16, 2026