New method to generate twin primes.

257 Views Asked by At

Is this a valid method to generate twin primes?

Let $q = \left\lfloor \sqrt{n} \right\rfloor$. If $n = q \cdot (q + 2)$ and

$\quad \gcd(n,m) = 1 \quad \forall m \in \left[ \left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{\sqrt{n}}{2} \right\rfloor \right] $

then $n$ is the product of twin primes.

Update

Based upon Command Master's answer, the optimized method so far is

Let $q = \left\lfloor \sqrt{n} \right\rfloor$. If $n = q \cdot (q + 2)$ and

$\quad \nexists m \in [2, \root 4\of{n} + 1] : n \equiv 0 \pmod{m}$

then $n$ is the product of twin primes.

Comparisons between Old vs New methods.

1

There are 1 best solutions below

2
On BEST ANSWER

This is correct. Suppose that $n = q(q+2) = (q+1)^2-1$. If $q$ or $q+2$ aren't prime, they have a factor which is at most $\sqrt{q+2} = \sqrt{\sqrt{n+1}+1}$. $\sqrt{\sqrt{n+1}+1} < \frac{\sqrt{n}}{2}$ for $n > 24$, so for $n \leq 24$ we need to check manually, which isn't hard, and for $n > 24$ that factor which is less than $\frac{\sqrt{n}}2$ much divide some number in range of $\frac{\sqrt{n}}2$ consecutive numbers, so the direction you gave is correct.

For the other direction, I assume you meant $[\lfloor \frac{n}2 \rfloor, \lfloor \frac{n}2 \rfloor + \lfloor \frac{\sqrt{n}}2 \rfloor]$, since otherwise the answer is false even for $143$.

Suppose $q$ and $q+2$ are primes, and $q = 2k-1$. So $n = 4k^2 - 1$. If we substitute that to the range, we get $[2k^2 - 1, 2k^2 - 1 + k - 1]$. Since the range is clearly smaller than $q$ and $q+2$, we only need to make sure the lower bound $\mod q$ is less then the upper bound $\mod q$, and same for $q+2$.

Note that $k \equiv 2^{-1} \pmod q$, so $2k^2 - 1 \equiv 2^{-1} - 1 \pmod q$ and $2k^2 - 1 + k - 1 \equiv 2^{-1} - 1 + 2^{-1} - 1 \equiv -1 \equiv q-1 \pmod q$, and obviously $2^{-1} - 1 \mod q < q-1$.

For $q+2$, we note that $k \equiv - 2^{-1} \pmod {q+2}$, so $2k^2 - 1 \equiv 2^{-1}-1 \pmod{q+2}$ and $2k^2 - 1 + k - 1 \equiv 2^{-1} - 1 - 2^{-1} - 1 \equiv -2 \equiv q-2 \pmod {q+2}$, and since $2^{-1} \mod {q+2} \neq 0,1$, the inequality is still correct.