Is there an integer $n$ such that $n^2+1$ is divisible by a prime $p$ with $2n<p<2n+\sqrt n$?
It's complicated to describe my interest, but these are near-missed for arc-cotangent reducible numbers (A002312) which would provide a counterexample that certain types of numbers are equivalent to that sequence.
The chance that a random number is divisible by some prime in that range is roughly $$ \frac{1}{2\log n\sqrt n} $$ the sum of which diverges far too rapidly to explain the absence of examples for $n<10^7.$ (I recognize that these heuristics are too rough for the situation in at least two ways, but it helps show that the situation is interesting.)
Your intuition is right to suspect an algebraic obstacle to the random behavior the heuristic predicts. Suppose that $k\ge1$ is such that $2n+k$ divides $n^2+1$. Writing $n^2+1=(2n+k)d$, we see that $d$ must be greater than $\frac n2-\frac k4$, since $(2n+k)(\frac n2-\frac k4) = n^2-\frac{k^2}4$ is too small. But then the smallest that $d$ can be, given that it is an integer, is $\frac n2-\frac k4+\frac14$. This implies that $$ n^2 + 1 = (2n+k)d \ge (2n+k)\big( \tfrac n2-\tfrac k4+\tfrac14 \big) = n^2 + \tfrac n2 + \tfrac k4 - \tfrac{k^2}4, $$ and so $(\frac k2-\frac14)^2 = \frac{k^2}4 - \frac k4 + \frac1{16} \ge \frac n2 - \frac{15}{16}$. We conclude that $$ (2n+k)\mid (n^2+1) \implies k\ge 2\sqrt{\tfrac n2 - \tfrac{15}{16}} + \tfrac14 \ge \sqrt{2n} $$ (the latter inequality holding for $n\ge30$). Note that this holds for all divisors, not just prime divisors.