FALSIFIABLE
Open, but could be disproved with a finite counterexample.
Is it true that for any $n,k\geq 1$, if $n+1,\ldots,n+k$ are all composite then there are distinct primes $p_1,\ldots,p_k$ such that $p_i\mid n+i$ for $1\leq i\leq k$?
Note this is trivial when $k\leq 2$. Originally conjectured by Grimm
[Gr69]. This is a very difficult problem, since it in particular implies $p_{n+1}-p_n <p_n^{1/2-c}$ for some constant $c>0$, in particular resolving
Legendre's conjecture.
Grimm proved that this is true if $k\ll \log n/\log\log n$. Erdős and Selfridge improved this to $k\leq (1+o(1))\log n$. Ramachandra, Shorey, and Tijdeman
[RST75] have improved this to\[k\ll\left(\frac{\log n}{\log\log n}\right)^3.\]This is problem B32 in Guy's collection
[Gu04].
See also
[860].
View the LaTeX source
This page was last edited 30 September 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #375, https://www.erdosproblems.com/375, accessed 2025-12-07
