Assume Goldbach Conjecture and write an even number $2n$ as the sum of two primes. The obvious approach is the forward search: Start with $p=3$ and check if $2n-p$ is a prime. If yes, stops, else we proceed to check with the next prime $p=5$ and so on. An alternate approach is the backward search: Start with the largest prime $\pi(2n)$ and check if $2n-p_{\pi(2n)}$ is a prime. If yes, stop, else we proceed to check with the previous prime $p_{\pi(2n)-1}$ and so on.
For $n \le 1.03 \times 10^{10}$ I counted how many searches both approaches required before we found the first solution. The data shows that for the backward search $2n-p_{\pi(2n)}$ is the first solution in about $59\%$ of the time and $2n-p_{\pi(2n)-1}$ is the first solution nearly $20\%$ of the time. For the forward search, $2n-3$ is the first solution in only about $8.8\%$ of the cases while $2n-5$ is the first solution in only about $8.2\%$ of the cases. These percentages are expected to decreases as $n$ increases.
The graph below shows the probability that the forward and the backward requires $k = 1,2,\ldots 60$ before finding the first solution.
Notice that for $k = 1,2,3$ the backward probabilities higher while for $k \ge 4$ the forward probabilities is higher. Based on this data, an algorithm to minimize the number of searches is as follows.
- Check if the largest prime q < 2n is a solution
- If yes, stop else, check with the previous prime
- If yes, stop else, check with the previous prime
- If yes, stop else, start with p = 11 (corresponding to k=4) and continue searching successive primes until a solution is found
I implemented the forward, the backward and the above modified search and ran it for $n \le 10^{10}$. The forward search was the slowest while the modified algorithm was marginally faster than backward search. This is despite the fact the in the backward search, finding the largest prime less than $2n$, and then its previous prime and so on takes more computational time than searching for primes in ascending order $3,5,7,11, \ldots $
Question 1: Is there a way to improve upon the above algorithm and reduce the number of searches?
Question 2: What is the expected number of searches in the forward, backward and above algorithms
Related question: How soon can we represent a number as the sum of two primes?
You could apply Sieve of Eratosthenes that gives primes in a range. You can sieve the range $(2, n/2)$. The sieving takes $O(n \log \log n)$ time and $O(n)$ space.
You could then test pairs of primes in this range using a modified binary search. This is based on the fact that if $p + q = n$ with $p, q$ prime, then both $p$ and $q$ will be in the sieved results of the range $(2, n/2)$. The sieved results occupies space $N = O\left({n \over \log n}\right)$ by the Prime Number Theorem.
For a given $p$, the binary search for $q$ takes $O(\log N)$ time where $N$ is the size of the sieved results. This search may or may not succeed in finding the pair $p,q$ such that $p + q = n$.
Therefore, this takes $O(N \log N)$ time, in the worst case (actually $O({N \over 2} \log N)$, but we are ignoring the constant factor in Big-O notation).