Suppose we are given a large even integer $N$, and we want to determine primes $p$ and $q$ such that $N = p + q$, subject to the conditions that $p \geqslant q$ and $p - q$ is as small as possible. (Of course, since Goldbach's conjecture is still unsolved, we cannot be sure that such $p$ and $q$ exist.)

What is (a lower bound for) the time complexity of this problem?

One algorithm (which was the first thing that popped into my head) for finding such $p$ and $q$ would be to check the primality of the numbers

\begin{align*} \tfrac{N}{2}, \quad \tfrac{N}{2} \pm 1, \quad \tfrac{N}{2} \pm 2, \quad \ldots \end{align*}

and stop once you reach the first $k$ such that the numbers $\tfrac{N}{2} \pm k$ are both prime. In the worst possible case (i.e. when $N$ is a counterexample to Goldbach), this algorithm has to check the primality of

\begin{align*} 2 \left( \frac{N}{2}-2 \right) + 1 = N - 3 \end{align*} numbers. But there are various algorithms for checking primality, depending on the size of the number in question, so in order for the algorithm to be as efficient as possible, not all of the $N-3$ primality checks should be done with the same primality test. For example, for small values of $\tfrac{N}{2}-k$, the most efficient primality test would probably be to compare $\tfrac{N}{2}-k$ with the entries in a list of the first (say) $100000$ primes, while for large values of $\tfrac{N}{2}+k$ (say, $\tfrac{N}{2}+k$ larger than the $100000$'th prime) this is pointless.

  • $\begingroup$ You don't need to check all distances. $\endgroup$ – Roddy MacPhee Feb 24 at 19:18

Let N=2M ,a few things of note:

  • primes greater than 3, are 1 or -1 mod 6
  • No prime divisors of M need be checked
  • If M is not a multiple of three, the primes used in testing below N need only be 3 and all odd primes of a single mod 6 value.
  • In the case of M a multiple of 3, at most $\frac{M}{3}$ tests need to be performed.
  • If M is x mod 3,x non-zero, only primes that are x mod 3 need testing.
  • These are limited by the Modular prime counting function

The upper (not lower) bound is Therefore, the Modular prime counting function, times the length of your average primality test.

If you go to the number of gaps of the same form less than M, and find no primes above n with that, Then by the pigeonhole principle a match is gauranteed if a prime of the righy kind can exist between n and 2n-3


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.