I've tried to be more mathematically explicit and less expositional in this proof. The motivating principle is that certain relative expressions are always available to use, and they can guarantee the existence of a graph yielding a prime within a given range.
Let $f(a,0):=a$, and otherwise
$$ f(a,b):= \begin{cases} &f(a,&b-1)&&\text{if }\gcd(a,b)>1 \\ &f(a-1,&b-1)&&\text{if }\gcd(a,b)=1 \end{cases} $$
where $f$ is defined for $a,b\in\mathbb Z$ and $a\geq b \geq 0$.
I recognize that its effect is probably not immediately obvious, so hopefully this table conveys the gist. Primes are blue bolded.
Let $p$ be an arbitrary prime, and consider $$f(2p-1,p-1)\tag{1}\label{1}.$$
$\gcd(2p-1,p-1)=1$ for any $p$, so $f(2p-1,p-1)$ will become $f(2p-2,p-2)$ after its first iteration. This only amounts to
$$(2p-1)-(p-1)=(2p-2)-(p-2)=p\ ,$$
and we can see that $\gcd(2p-c,p-c)=1$ for all $0<c<p$. Note that the $b$-value in our function is essentially a counter from $p$ down to $0$, and when it get there we've triggered our exit condition: $$f(2p-p,p-p)=f(p,0)=p.$$
This tells us that if we will always retrieve our prime back after feeding it through $f(2p-1,p-1)$. Of course, we still need to cover some values that don't require we already know a prime.
Let $p_0<p$ be the nearest prime before $p$. Then we turn to
$$f(2(p-k)-1,(p-k)-1),\qquad 0 < k < p-p_0\tag{2}\label{2}.$$
These $k$ values will use the composite terms leading up to $p$ instead of $p$, in the same general form as before. However, we assert that that function, using any $k$ in this range$-$that is, values falling within the nearest prime gap$-$will nevertheless yield the same $p$ as before. In the case of $k=1$:
$$ \begin{array}{c|c|c} & k=0 & k=1 \\ \hline 1& f(2p-1,p-1) \\ 2& f(2p-2,p-2) & f(2p-3,p-2) \\ 3& f(2p-3,p-3) & \color{red}{f(2p-4,p-3)} \\ 4& f(2p-4,p-4) & f(2p-4,p-4) \end{array} $$
On the third line, the $a$ value $2p-4$ and the $b$ value $p-3$ will both be even and therefore not coprime, resulting in the $a$ value not decrementing, which puts it in sync with the other sequence. $k=2$ does the same thing with an extra step, and I'll skip the math because obviously this approach won't scale well; we'll need something more general.
These instances of divisibility are because our other $k$-sequences were chosen to be composite. This is good news. Half of the values will be even every other step, and will have their sequence sync and become identical to $\eqref{1}$ almost immediately. The worst case you can run into is a perfect square $q$ such that $q^2<p$, which will make something like $\left\lfloor{\sqrt{p}}\right\rfloor$ adjustments, but this is still enough to guarantee a sequence merge before $b=0$, which is all we need. (There is a theoretical one-off edge case at $n=11^2$, but I think it is harmless for our purposes.)
It is clear after looking over graph representations of all of these situations that there are two wildly different types: graphs which are rooted with a prime at location $b=0$, and those that are rooted with a composite at $b=0$. If we could only deal with prime-rooted graphs, this would be trivial, but it's problematic to eliminate the possibility of selecting a composite-based graph (well, problematic to prove it.)
Here's a reference pic highlighting the type of paths I discuss in case it too helps get the idea across. Feel free to ignore it if it's just confusing. (Value pairs are shown as subscripts on graph: $(a,b) \mapsto a_b$)
A key aspect of this approach is the observation that every ordered pair $(a,b)$ that we use with our function is either already set in a prime-rooted graph, or it isn't; if all the pairs we care about are indeed in prime-rooted graphs, we need proof. One way we can get that proof is to establish that some particular type of value will always appear in a prime-rooted graph, in which case we can also be sure that it cannot ever appear in a composite-rooted graph.
What we've done is explicitly confirm the presence of nodes on the graph that can only exist if there's a prime at the $b=0$ position. By this I'm referring to the bottommost point ($29_0$ in my example) or "root node," to which the entire directed graph is being funneled.
If indeed all value pairs of form $\eqref{2}$ return the same prime as $\eqref{1}$, we will have accomplished two critical things at once:
- Obtained an entry value-pair point for some prime-bearing graph for any $n$.
- Established that such prime-bearing graphs do exist for every $n$, fulfilling our existence and proximity requirements.
The bottom line is that given any $n$, we can take $f(2n-1,n-1)=q$ where $q$ will be a guaranteed prime in range $(n,2n)$.
In particular, it should be the first prime after $n$. For the record, I have run this algorithm through $10^4$ without any errors, but the proof is the issue here.
Looking it over, I'm pretty certain about the first step, tying $(2n-1,n-1)$ to a prime. If there's a flaw in this proof, I have to suspect it's a faulty justification for the $k$-offsets necessarily merging to a single path in time. Confirmation or constructive criticism welcome.