Problem Statement
Is it true that, for all sufficiently large $n$, there exists some $k$ such that\[p(n+k)>k^2+1,\]where $p(m)$ denotes the least prime factor of $m$?
Can one prove this is false if we replace $k^2+1$ by $e^{(1+\epsilon)\sqrt{k}}+C_\epsilon$, for all $\epsilon>0$, where $C_\epsilon>0$ is some constant?
Can one prove this is false if we replace $k^2+1$ by $e^{(1+\epsilon)\sqrt{k}}+C_\epsilon$, for all $\epsilon>0$, where $C_\epsilon>0$ is some constant?
Categories:
Number Theory Primes
Progress
This follows from 'plausible assumptions on the distribution of primes' (as does the question with $k^2$ replaced by $k^d$ for any $d$); the challenge is to prove this unconditionally.Erdős observed that Cramer's conjecture\[\limsup_{k\to \infty} \frac{p_{k+1}-p_k}{(\log k)^2}=1\]implies that for all $\epsilon>0$ and all sufficiently large $n$ there exists some $k$ such that\[p(n+k)>e^{(1-\epsilon)\sqrt{k}}.\]There is now evidence, however, that Cramer's conjecture is false; a more refined heuristic by Granville [Gr95] suggests this $\limsup$ is $2e^{-\gamma}\approx 1.119\cdots$, and so perhaps the $1+\epsilon$ in the second question should be replaced by $2e^{-\gamma}+\epsilon$.
See also [681] and [682].
Source: erdosproblems.com/680 | Last verified: January 16, 2026