Least prime factor spikes: is $p(n+k)>k^2+1$ solvable for every large $n$? (Erdős #680)

Let $p(m)$ denote the least prime factor of $m$. Is it true that for all sufficiently large $n$ there exists some $k$ such that $$p(n+k)>k^2+1?$$ Can one further prove that this fails if $k^2+1$ is replaced by $e^{(1+\epsilon)\sqrt{k}}+C_\epsilon$ for every $\epsilon>0$, where $C_\epsilon>0$ is a suitable constant? The first part asks that near every large $n$ one can find an index $k$ whose shifted integer $n+k$ has an unusually large least prime factor; the second asks how far this phenomenon can be pushed before it must break down.

Acceptance. FULLY RESOLVES: a complete unconditional proof — a Lean/Coq formalisation matching the DeepMind formal-conjectures statement for #680 is preferred, otherwise a full written proof — that for all large $n$ some $k$ satisfies $p(n+k)>k^2+1$; and/or a proof of the second part, showing the $e^{(1+\epsilon)\sqrt{k}}+C_\epsilon$ version fails for every $\epsilon>0$. ADVANCES: prove the first statement conditionally under a precisely stated prime-distribution hypothesis (an explicit form of prime $k$-tuples / short-interval conjectures, improving on the informal 'plausible assumptions'); or prove the generalisation with $k^2$ replaced by $k^d$ for a specific $d>1$ (conditional or unconditional, clearly flagged); or computationally verify that every $n$ up to a record $N$ admits such a $k$, supplying the search program and the attained $N$ strictly beyond any bound recorded here. Deliver the proof or the verification code with its attained $N$.