Is this proposed method of finding primes valid? If so, would it be effective?
Solution 1:
Yes, this method is valid (in particular, your reasoning that the numbers you come up with are prime is correct), but it's not likely to be particularly effective.
I'm going to assume familiarity with big- and little-O notation; if you aren't familiar with this, Wikipedia is a good resource.
The key issue that makes this not very effective is the $\sqrt{a-b}\leq p_n$ condition. This means that, if you want to find a prime that's about $X$, you need to know all the primes less than $\sqrt X$. This essentially means that trial division would work fine (since this is all you need for trial division), as would something like the Sieve of Eratosthenes.
The other thing is that, as $n$ gets big, the condition that $\sqrt{a-b}\leq p_n$ becomes really hard to satisfy. Consider the product $$P_x=p_1p_2\cdots p_n$$ of all primes less than some number $x$. It is known that this product is $e^{x(1+o(1))}$. You're looking for a divisor $a$ of this product so that $$0\leq a-\frac{P_x}{a}\leq x^2.$$ Solving for $a$, this becomes $$0\leq a^2-P_x\leq ax^2\Leftrightarrow \sqrt{P_x}\leq a\leq \frac{x^2+\sqrt{x^2+4P_x}}{2}=\frac{x^2}2+\sqrt{P_x+\frac{x^2}4}.$$ The issue is that, as $x$ is large, $P_x$ is much larger than $x^2$, and so $$\sqrt{P_x+\frac{x^2}4}\leq \sqrt{P_x}+1.$$ This essentially means any product $a$ has to lie in a range around $\sqrt{P_x}$ of size about $x^2$. Because there are $2^n\ll P_x$ divisors of $P_x$, it seems unlikely that many of them will be so close to $\sqrt{P_x}$, and so for many large primes this technique may not give any numbers at all.
Solution 2:
Your proposed method works to find a prime strictly between $p_n$ and $p_n^2$, provided you can find qualifying values of $a,b$ such that $1 < |a-b| < p_n^2$.
The idea is interesting, but as far as practical value, there are two major problems . . .
- An exhaustive search would require testing on the order of $2^{n-1}$ potential pairs $(a,b)$, so unless $n$ is small, say $n < 50$, such a search would not be feasible.$\\[4pt]$
- Worse, it seem likely that for almost all $n > 9$ (possibly all), there will be no qualifying values of $a,b$ such that $1 < |a-b| < p_n^2$. In particular, there are no such values of $a,b$ for $10\le n\le 20$.