I am curious to know if a lower bound on the number of ways (call this $\beta$ and assume $p_1 + p_2$ distinct from $p_2 + p_1$) in which two primes $p_1, p_2$ that add up to a given even integer $n$, has been conjectured (Obviously, I would think not proven yet). For $n = 2^t$, a really good lower bound that I have arrived at is $$\beta \ge \pi(\pi(n))$$

x-axis is $n=2^t$ and y-axis shows $\beta$

enter image description here

A similar chart for $n = 2 * 3^t$ is shown below.

x-axis is $n=2 * 3^t$ and y-axis shows $\beta$

enter image description here

For all other compositions of n, $\pi(\pi(n))$ while not such a good lower bound, provides a lower bound nevertheless.

Here is the main idea. Let K represent the number of odd primes $<n$, therefore $K = \pi(n) - 1$. Let $P_1, P_2, \ldots, P_r$ represent the $r$ odd primes $< \sqrt{n}$. Now we need to find how many of these K primes add up to a prime and here is where we end up with probability. However, we can take a different approach.

Let $n = 2^t$ and let $n = t_1 \bmod P_1 = t_2 \bmod P_2 = \ldots = t_r \bmod P_r$. We are interested in identifying how many of the $K$ primes leave none of these remainders ($t_i$). If a prime P has a different remainder (different from the $t_i$) modulo each of the $r$ primes , then we are sure that $n-P$ is also prime (since then $n-P \ne 0 \bmod P_i$ for $1 \le i \le r$).

But unlike a sequence of integers, the set of consecutive primes do not leave remainders in a "periodic" manner. For example, there are 135 odd primes less than 770. Of these 135, there are 66 primes that are $1 \bmod 3$ and 68 primes that are $2 \bmod 3$. In some cases, some remainders may not occur. However, we can be sure of one thing. The number of remainders that are 1 mod 3 (or 2 mod 3) will be close to $1/2$. If the number of remainders is $> 1/2$, it will be greater than $1/2$ by a $\delta$. The number of remainders that are $1$ or $2$ or $3$ or $4 \bmod 5$ will be close to $1/4$ or higher or lower than $1/4$ by $\delta$ and so on for all $P_i$.

We assumed n is a power of 2. However if n has a prime factor q, then we simply can ignore this as none of the primes will leave a zero remainder modulo q (except q). We can now pass K through the classic Legendre sieve.

Let Q = product of all odd primes less than $\sqrt{n}$. (There may be a more elegant and concise way to write the below using the Mobius function).

Lower Bound for $$\beta \approx K - (\sum_{i=1}^r \lfloor\frac K {P_i-1}\rfloor )+ (\sum_{i=1 \text{ and } i<j<r}^r \lfloor\frac K {(P_i-1)(P_j-1)}\rfloor) - \ldots $$

Suppose $n$ has $s$ odd prime factors such as $q_1, q_2, \ldots, q_s$. Some of these $q_i$ could be equal to some of the $P_i$. So the modified LB will look like:

Lower Bound for $$\beta \approx K - (\sum_{i=1, (P_i \ne q_i \text{ for all }i)}^r \lfloor\frac K {P_i-1}\rfloor )+ (\sum_{i=1 \text{ and } i<j<r \text { and } (P_i \ne q_i \text{for all i)}}^r \lfloor\frac K {(P_i-1)(P_j-1)}\rfloor) - \ldots $$

for $n$ with odd prime factors. Essentially, in the sieve, we ignore any $P_i$ that is a prime factor of $n$.

For large n, actual $\beta$ will be higher as the remainders of $n \bmod P_i$ are not equally distributed in $0,1,2,\ldots,P_i-1$.

  • 1
    $\begingroup$ This a quantitative form of the Goldbach conjecture (described as the "extended Goldbach conjecture" here). And yes, it's still unproven. $\endgroup$ May 25, 2016 at 6:24
  • $\begingroup$ @Greg, Thanks for your comment. Why does the Sieve method (as shown above) not work in the proof for GC? Sieves do a perfectly good job for counting primes.. Thanks in advance! $\endgroup$
    – sku
    May 26, 2016 at 5:08
  • 1
    $\begingroup$ They don't, really. There are exponentially many terms in your inclusion-exclusion sum, and removing the floor functions results in an error in each term. This is a standard problem which sieves try to overcome, but (so far) unsuccessfully in the case of Goldbach. $\endgroup$ May 26, 2016 at 8:35

2 Answers 2


The lower bound is one partition unless the Cartesian plane has an inherent contradiction. It is defined by linear equations for prime intercepts:

$x = 2p_{1} $

$y = -0.5x - p_{2}$

where $x < y < n$

The $x$ intercept is $2p_{1}$ and the $y$ intercept is $p_{2}$ such that the lines intersect at the coordinates of one even $n$. Graphically and logically, there must be a point of intersection - and that intersection must lie in the region defined by $x\geq3$ and $y\leq n-3$. If there were no such intersection, the coordinate plane would offer no solution to the intersection of a slope with a vertical line, which is impossible.

Line and slope in partitions:

Linear line and slope in partitions

Line and slope as coordinates:

Linear line and slope as coordinates


N is the sum of primes p and w. There are n-1 ways to write N = p+q for integers p and q. Random p, q would be both prime with probability 1 / ln p and 1 / ln (N-p). However we know that p, q are both odd unless N <= 4, so we only use half the p’s but the q’s = N-p are twice as likely to be prime. We can look at N modulo 6 which influences the number of solutions. Ignoring this, the expected number is N, pi(N), divided by the average of 2 / ln (N-p).

Now you are looking for a lower bound. The count is a bit lower if N is not divisible by 6 and a bit higher otherwise, same for N multiple of 5, 7, 11 etc. so you calculate the expected number for n not divisible by 3, 3 or 5, 3 or 5 or 7. Then you have many values of N; your actual number will be variable. You can try to calculate variance and standard variation.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .