2
$\begingroup$

The function g(N) for counting the prime pairs in an even integer N can be implemented as:

g = 0 for p in primes ≤ N/2: if is_prime(N - p): g += 1

Question: Is there a separate algorithm, that uses an apparently different logic, but still achieves the same count of prime pairs in N?

Improve this question
New contributor
Jie Pan is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
5
  • 1
    $\begingroup$ I changed your title to say what g(N) is, and changed the reference to "a separate function" to "a separate algorithm" (since the usual view of functions is by their extension, so that two functions that have the same outputs for all inputs are the same, even if the internal details of the algorithms by which those outputs are computed are different). I hope that that was all right. $\endgroup$ Commented 11 hours ago
  • 2
    $\begingroup$ An obvious way to make it considerably faster is not to test the primality of all these numbers one after another separately, but generate them all using some variant of the sieve of Eratosthenes. $\endgroup$ Commented 10 hours ago
  • $\begingroup$ One can also try numerically estimating the integrals used in the circle method $\endgroup$ Commented 9 hours ago
  • 2
    $\begingroup$ This question was cross-posted to Math StackExchange. $\endgroup$ Commented 9 hours ago
  • 1
    $\begingroup$ @LSpice, thanks for changing "a separate function" into "a separate algorithm". Yes, it is more to the point as my thinking was more on the side of algorithm and underlying logic. I am not thinking of optimization of the same algorithm as used in the g(N) function. $\endgroup$ Commented 5 hours ago

1 Answer 1

Reset to default
2
$\begingroup$

If you define $$f(z) = \sum_{p \le N} e^{2\pi i p z}$$ then by the circle method $$g(N) = \int_{0}^{1} f(z)^2 e^{-2\pi i N z} dz$$

The algorithm you gave (direct search) is local. This algorithm (circle method) is global, it creates interference pattern of all primes simultaneously.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ It might be worth noting that due to highly oscillatory nature of the integrand, even estimating it is extremely nontrivial, let alone evaluating it exactly. In principle it's possible, but in practice this algorithm is very inefficient $\endgroup$ Commented 8 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.