Problem Statement
Let $t_n$ be minimal such that $\{n+1,\ldots,n+t_n\}$ contains a subset whose product with $n$ is a square number (and let $t_n=0$ if $n$ is itself square). Estimate $t_n$.
Categories:
Number Theory
Progress
A problem of Erdős, Graham, and Selfridge. For example, $t_6=6$ since $6\cdot 8\cdot 12=24^2$. It is trivial that $t_n\geq P(n)$, where $P(n)$ is the largest prime divisor of $n$.Erdős originally asked whether the set with $t_n\geq n^{1-o(1)}$ has density zero. Selfridge then proved that $t_n=P(n)$ if $P(n)>\sqrt{2n}+1$, and $t_n \ll n^{1/2}$ otherwise.
Bui, Pratt, and Zaharescu [BPZ24] proved that the distribution of $t_n$ continues to follow $P(n)$, in that for any fixed $c\in (0,1]$\[\lim_{x\to \infty}\frac{\lvert \{ n\leq x : t_n\leq n^c\}\rvert}{x} = \lim_{x\to \infty}\frac{\lvert \{ n\leq x : P(n)\leq n^c\}\rvert}{x}.\]They also prove that for at least $x^{1-o(1)}$ many $n\leq x$ we have\[t_n \leq \exp(O(\sqrt{\log n\log\log n}))\]and for all non-square $n$\[t_n \gg (\log\log n)^{6/5}(\log\log\log n)^{-1/5}.\]See also [437].
This is problem B30 of Guy's collection [Gu04].
Source: erdosproblems.com/841 | Last verified: January 16, 2026