Consider the following algorithm (Python, untested):
def gcdPrimer(n, a=0):
if a == n/2:
return a
else:
return gcdPrimer(n + (1 if gcd(a+1, n)==1 else 0), a+1)
(or Mathematica)
gcdPrimerR[n_Integer, a_Integer: 0] :=
If[a == n/2, a,
gcdPrimerR[n + Boole[CoprimeQ[a + 1, n]], a + 1]]
This algorithm returns the largest prime less than $n$.
First, $a$ always increments by $1$. After $a$ does this, if $a$ is coprime to $n$, then $n$ also increments by $1$. However, if $a \mid n$, then $n$ does not change. This continues until $2a=n$, at which point $a$ should be our target prime and we halt.
The purpose behind the sometimes-incrementing is to account for the size of the prime gap that our target prime is in, if any; $n$ will delay like that for $k$ iterations, if $n-k$ is the target prime. Non-incrementing passes are denoted by the $*$'s in the $n$ column. What it's actually doing amounts to obfuscated trial division, the mechanism which makes this whole thing work.
The table below shows what things look like as it processes a run with $n=28$. Specifically, it's what things look like at the end of each pass through the function.
$$ \begin{array}{|r|c|c|c|c|} \hline a & n & a/n & \gcd(a,n) & n \bmod a \\ \hline 1 & 29 & \frac{1}{29} & 1 & 0 \\ 2 & 30 & \frac{1}{15} & 2 & 0 \\ 3 & 30* & \frac{1}{10} & 3 & 0 \\ 4 & 30* & \frac{2}{15} & 2 & 2 \\ 5 & 30* & \frac{1}{6} & 5 & 0 \\ 6 & 30* & \frac{1}{5} & 6 & 0 \\ 7 & 31 & \frac{7}{31} & 1 & 3 \\ 8 & 32 & \frac{1}{4} & 8 & 0 \\ 9 & 33 & \frac{3}{11} & 3 & 6 \\ 10 & 34 & \frac{5}{17} & 2 & 4 \\ 11 & 35 & \frac{11}{35} & 1 & 2 \\ 12 & 36 & \frac{1}{3} & 12 & 0 \\ 13 & 37 & \frac{13}{37} & 1 & 11 \\ 14 & 38 & \frac{7}{19} & 2 & 10 \\ 15 & 39 & \frac{5}{13} & 3 & 9 \\ 16 & 40 & \frac{2}{5} & 8 & 8 \\ 17 & 41 & \frac{17}{41} & 1 & 7 \\ 18 & 42 & \frac{3}{7} & 6 & 6 \\ 19 & 43 & \frac{19}{43} & 1 & 5 \\ 20 & 44 & \frac{5}{11} & 4 & 4 \\ 21 & 45 & \frac{7}{15} & 3 & 3 \\ 22 & 46 & \frac{11}{23} & 2 & 2 \\ 23 & 46* & \frac{1}{2} & 23 & 0 \\ \hline \end{array} $$
Mechanism of algorithm
As near as I can tell, the general principle is solid and should work in virtually all cases. It's been tested through $10^5$ without incident. Because of how the GCD pair is set up, $n$ is able to delay $k$ times (where $n-k$ is the next lowest prime) by having $a$ encounter incrementally more divisors near the start, corresponding to $2$ through $k$. I am only about $85\%$ sure that I grok that aspect of it, so if someone needs to correct me, please do.
What this gives us
Let's assume for the moment that the algorithm is sound for any integer input.
Then, consider this in terms of Bertrand's Postulate. If we want to establish that a prime exists in $(r,2r)$, we simply call $\mathsf{gcdPrimer}(2r)$, and we're basically done.
The beautiful part about this is that the mechanics of the algorithm (if sound) confirm Bertrand's Postulate implicitly. Consider the two extremes we could see:
- $2r-1\in\mathbb P$, and only one non-increment step is used by $n$. $a$ increments up to $2r-1$ as $n$ reaches $2(2r-1)$, and $a=2r-1$ is returned.
- The other extreme is where any potential problems most likely lie. That said, even if $n$ barely changes, $a$ only needs to halve it to return, and it's easily guaranteed to do that even in worst-case scenarios. Since $n=2r$, no matter what we'll have some $a>n/2$, and thus $a>r$.
In either case, we stay within our target $(r,2r)$ interval.
What this doesn't give us
It seems to me that the only way this fails is through an argument that some totally unreasonable prime gap can appear and cause the algorithm to misbehave and return a composite. (I could invoke Bertrand to mostly wave this problem away, but the idea of this whole exercise is to prove this from scratch.)
Even faced with a gargantuan prime gap, $n$ could never freeze completely$-$that would imply that every integer smaller than $n$ divides it, so we're in no danger of returning a value $\leq r$, regardless of any other considerations.
Given that, the only remaining issue (albeit a huge one) is whether the algorithm can be trusted to return a prime no matter what. I am reasonably certain that it can, but am less certain that it's provable. I'm still working on that part of it, but I decided to post what I have so far in case I'm way off or somebody has some insight.