# Time complexity of finding the largest Goldbach partition

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.

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

• In the case of M a multiple of 3, at most $$\frac{M}{3}$$ tests need to be performed.