Is this proposed method of finding primes valid? If so, would it be effective?

Question

(See question towards the end)

Suppose we take the first four consecutive primes, $$2, 3, 5, 7$$ Since these are prime numbers, the greatest common divisor will be 1. In other words, they will be co-prime. Knowing this, this also means their lowest common multiple will be the product of the primes multiplied. $2*3*5*7$ will result in $210$.

$210$ obviously will not be prime as it is divisible by $2, 3, 5,$ and $7$, but this must mean $210$'s only factors are $2, 3, 5,$ and $7$ because every number has only one prime factorization which is also unique (ignore composite factors, they will not matter in my method).

Following this logic, $23$, equal to the expression $(2*3*5) - 7$, cannot be divisible by $2, 3, 5,$ or $7$.

$23$'s not divisible by $7$ because we know the first term in the expression, $(2*3*5)$, wasn't a multiple of 7 (since it didn't have 7 in its prime factorization), so subtracting 7 from it won't change that. Also, since $7$ is co-prime with the other three primes, subtracting $7$ from $(2*3*5)$ makes $23$ not divisible by $2, 3,$ or $5$ as well.

$23$ then is not divisible by $2, 3, 5,$ or $7$. Due to how factors work, to check if any positive integer, c, is prime, you can take the square root of c and find primes below that value. If no primes less than the square root of c divide evenly into c, c is prime.

If we apply this to $23$, we get $\lfloor{\sqrt23}\rfloor = 4$. We showed earlier $23$ is not divisible by primes up to $7$, so it's not divisible by primes up to $4$ either. Therefore $23$ is prime.

Generalizing this, we can take the first n consecutive primes ( $p_1, p_2, p_3, ... , p_{n-1}, p_n$) and organize these primes into two groups however you'd like. Then, take the products of the primes within each group. Let's name the larger product, a, and the smaller product, b.

Take the difference of $a - b$. This difference between a and b will always be prime as long as the statements: $$\sqrt{a - b} \leq p_n$$ and $${a - b} >1$$

is true where $p_n$ is the nth prime.

For example, $227$ is a prime which I found using this method. We take the first 8 consecutive primes, $$2, 3, 5, 7, 11, 13, 17, 19$$ and split them into any two groups we'd like, in this case:

1. $2, 5, 17, 19$

2. $3, 7, 11, 13$

Taking the products of each group we get:

$2*5*17*19 = 3,230$

$3*7*11*13 = 3,003$

Have the larger product be a and the the smaller product be b. Afterwards, take the difference of $a - b$ : $$3,230 - 3,003 = 227$$

$\lfloor{\sqrt227}\rfloor = 15$.

$15 < 19$ and $227 > 1$, so $227$ is prime.

---

My Question:

Is this method for finding primes valid? If so, would it be effective to use when trying to find large primes?

(This question was really hard to articulate, and I'm aware I likely didn't do a good job. Edits, suggestions, and clarification is very much welcome!)

Answer 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.

Answer 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 . . .

1. 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]$
2. 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$.