6

This question, as well as its answers and comments, highlights a lot of unsettling numerical coincidences where certain sums over twin primes ostensibly converge to all kinds of weird values, however most of them look fishy in some aspects such as convergence rate (see comments by Terry Tao). To shed more light on this, it would be helpful to obtain further values of these (partial) sums, still linear computation of these quickly becomes prohibitive.

A simpler related problem is to count the number $f(N)$ of twin primes in a range $[1, N]$ (basically, summing $1$ instead of other stuff over primes $(p, p + 2) \leq N$). The question is: which algorithms would allow us to compute this number in $O(N^{\alpha})$ time for $\alpha < 1$? What if we want to approximate $f(N)$ with (arbitrary) relative tolerance $\delta$?

Just for the reference point, there are quite a few sublinear algorithms for counting primes in a range; good places to look are here, here and here. It is not clear how much of these results can carry over to twin prime counting though.

Mikhail Tikhomirov
  • 5,382

1 Answers1

5

This is a well-studied problem - so well-studied that the well-known Pentium division bug was a by-product. See Nicely's web page.

Igor Rivin
  • 95,560
  • 1
    Thanks for the reference! It seems to me that the algorithm used there was a highly tuned version of a linear algorithm (possibly even slower?), so my question still stands. – Mikhail Tikhomirov Nov 14 '17 at 04:12
  • 1
    @MikhailTikhomirov That's the best algorithm there is. – Igor Rivin Nov 14 '17 at 04:25
  • I don't see a lot of evidence for that. The article was published in 1995, and it sure looks more like a technical paper rather than a math or theoretical CS paper. So for the algorithm there to be the "best" algorithm, there should have been no fruitful research prior to the article and 20+ years after. Taking a more literal interpretation of your "best algorithm" claim, it would be groundbreaking to discover that we can't theoretically surpass the linear barrier for one reason or another! – Mikhail Tikhomirov Nov 14 '17 at 04:40
  • 2
    @MikhailTikhomirov We can't even prove that $P\neq NP,$ so I would not hold my breath for any proofs, but all evidence I see (the article is just one example) seems to indicate that a tweaked sieve is the best there is. – Igor Rivin Nov 14 '17 at 05:41
  • 2
    @MikhailTikhomirov : Nicely's paper is the one standardly cited for this problem. For example, "New bounds and computations on prime-indexed primes" from 2013 cites it and gives no indication of any significant later improvements. Obviously Igor Rivin could not mean that a linear-time algorithm is provably unbeatable since that would in particular imply a proof of the twin prime conjecture, but beating linear time would be huge news and we would all hear about it. – Timothy Chow Nov 15 '17 at 03:36