8
$\begingroup$

This is essentially a Bertrand's postulate version for twin primes. I am interested in both an explicit example and large lower bounds for it because of this answer of mine. In the comments below the answer, it is shown that there is no such $n$ below $8\times 10^{15}$.

An efficient algorithm would be as follows: take an initial point $m$ for which Bertrand's postulate for twin primes is true (say, $13$). Find the greatest prime twin $p\lt 2n$. The new initial point is $p$. Iterate.

An explicit example of such $n$ would cause a very large gap $\approx n$. Although it seems quite unlikely for such $n$ to exist, a proof remains far from reality, so I am interested in a computational effort.

Do we know $n\gt 5$ with no twin prime $n\lt q \lt 2n$? If not, what's the best known lower bound?

$\endgroup$
4
$\begingroup$

We can't yet prove that there are infinitely many twin primes, so we certainly can't prove that there's a twin prime in (n, 2n). But it's surely true. Indeed, between n and 2n we expect there to be about $Cn/\log^2 n$ twin primes for some positive constant $C$.

If you look at the worst case, consider A113275: Kourbatov found that the twin prime 1121784847637957 was followed by a longer gap of non-twin primes than any smaller twin prime, but the distance to the next twin prime was just 23382. That's a lot smaller than the 1121784847637957 you'd need to make the twin prime Bertrand fail!

Using the same approach as Michael Stocker I was able to check that there are no exceptions up to $10^{120}.$

Edit: I extended the range to $10^{262}$ and proved all the primalities. Time required was a few hours.

$\endgroup$
  • $\begingroup$ $+1$. The $10^{120}$ was computed assuming Michael's result or unconditionally? Here is the relevant ArXiV paper. $\endgroup$ – Ian Mateus Feb 4 '14 at 15:54
  • $\begingroup$ @IanMateus: Unconditionally, starting from 13. $\endgroup$ – Charles Feb 4 '14 at 15:59
  • $\begingroup$ This shows that we can rearrange $1, 2, 3,\ldots, n$ such that the sum of any adjacent numbers is prime for every number $n$ up to $10^{165}$. Nice! $\endgroup$ – Ian Mateus Feb 4 '14 at 16:31
  • 1
    $\begingroup$ @IanMateus: Indeed -- see oeis.org/A103839 $\endgroup$ – Charles Feb 4 '14 at 16:47
1
$\begingroup$

You can get very far with very little effort. I think an example to make your algorithm clearer wouldn't be bad. If we have a twin-prime p,p+2, for every n in the interval [((p+2)+1)/2 , p-1] there is (at least) one twin-prime in [n,2n], namely p,p+2.

We know that 17 and 19 form a twin prime. So every n in [10,16] satifies "Bertrands postulate for twin-primes" So the next twin-prime we want so find should generate a Interval that starts no earlier than 17. So we want ((p+2)+1)/2 < 18. Now we look for the biggest twin prime that satisfies that unequality. We find the twin-prime 29,31 and the Interval [16,28] --- 41,43 ; [22,40] --- 71,73 ; [37,70] --- 137,139; [70,136] --- ......

I let my pc compute for only a few minutes without much optimization and got to the 96 digit twinprim 65401729995203484466533471060061363152550275078004047522007054662124597261449032607389217013721 (+2)

$\endgroup$
  • $\begingroup$ Did you use any probabilistic prime test in the code? They are probably not safe for such large numbers. $\endgroup$ – Ian Mateus Feb 4 '14 at 13:44
  • $\begingroup$ @IanMateus: Considering that a primality proof of a number that size takes 200 milliseconds, Michael probably didn't have to use a PrP test. $\endgroup$ – Charles Feb 4 '14 at 15:17
  • $\begingroup$ @Charles if true, that's impressive! Only $5$ orders of magnitude from a googol. $\endgroup$ – Ian Mateus Feb 4 '14 at 15:22
  • $\begingroup$ @IanMateus: That's how long it took my aging PC to prove the primality of the number 654...721 in the answer. $\endgroup$ – Charles Feb 4 '14 at 15:29
  • $\begingroup$ I used javas BigInteger isProbablePrime function. They are not 100% primes, but you can get the probability very high. Numbers of that size can be tested for "certain" primality very easily too. $\endgroup$ – Michael Stocker Feb 4 '14 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.