Problem #681: Is it true that for all large $n$ there exists $k$ such...

Is it true that for all large $n$ there exists $k$ such that $n+k$ is composite and\[p(n+k)>k^2,\]where $p(m)$ is the least prime factor of $m$?

SOLVED

Problem Statement

Is it true that for all large $n$ there exists $k$ such that $n+k$ is composite and\[p(n+k)>k^2,\]where $p(m)$ is the least prime factor of $m$?

Categories: Number Theory Primes

Related to questions of Erdős, Eggleton, and Selfridge. This may be true with $k^2$ replaced by $k^d$ for any $d$.

See also [680] and [682].

Source: erdosproblems.com/681 | Last verified: January 16, 2026