Is there a functon that counts the number of ways in which an even number can be expressed as a sum of two primes?

  • 6
    $\begingroup$ there is one, you just defined it... $\endgroup$ – Xoff Aug 7 '12 at 12:55

See Goldbach's comet at Wikipedia.

EDIT: To expand on this a little, let $g(n)$ be the number of ways of expressing the even number $n$ as a sum of two primes. Wikipedia gives a heuristic argument for $g(n)$ to be approximately $2n/(\log n)^2$ for large $n$. Then it points out a flaw with the heuristic, and explains how Hardy and Littlewood repaired the flaw to come up with a better conjecture. The better conjecture states that, for large $n$, $g(n)$ is approximately $cn/(\log n)^2$, where $c>0$ depends on the primes dividing $n$. In all cases, $c>1.32$.

I stress that this is all conjectural, as no one has been able to prove even that $g(n)>0$ for all even $n\ge4$.


Yes, there is such a function and it has been studied for at least a century. See Sloane's A002375. But it doesn't have a set letter specified for it. Here I will use $g$. So, for example, $g(36) = 4$, $g(38) = 2$. (If you're looking in Sloane's, be sure to divide by 2 before looking up). There is also a function which requires the primes to be distinct, so $31 + 7 = 38$ counts but $19 + 19$ does not; that has also been studied for at least a century.

Now, is there a formula that you can plug in an even number $2n$ and have it give you an answer without knowing the primes up to $n$? I think that if the Riemann hypothesis is proven, it could lead to such a formula. As a quick and dirty estimate, I suggest $g(2n) \approx \frac{n}{8}$; your mileage may vary.

EDIT: Gerry Myerson rightly pointed out that $g(2n) < \pi(n)$, and that my quick and dirty estimate is quite inadequate for large numbers. From his comment, I revise my quick and dirty estimate to $g(2n) \approx \frac{n}{4 \log n}$. The point that I was getting at is that Bertrand's postulate tells us there is always at least one prime between $n$ and $2n$, and it seems unlikely to me that each and every prime in that interval would fail to "match" to a prime between 1 and $n$.

  • $\begingroup$ Your $g(n)$ is clearly no bigger than the number of primes up to $2n$. For $n$ large, the number of primes less than $2n$ is roughly $2n/\log n$, which is much smaller than $n/8$. So the "quick and dirty" estimate can't be much good, once $n$ is large enough. Also, to the best of my knowledge, the Riemann Hypothesis has nothing to do with it. $\endgroup$ – Gerry Myerson Dec 21 '14 at 19:49
  • $\begingroup$ Mostly good points. As for the Riemann hypothesis, that's just speculation on my part. $\endgroup$ – Robert Soupe Dec 21 '14 at 21:10
  • $\begingroup$ The Prime Number Theorem tells us much more than Bertrand's Postulate; instead of one prime between $n$ and $2n$, there are asymptotically $n/\log n$ of them. And a careful consideration of the likelihood of matchups with primes between $1$ and $n$ leads to an estimate of $cn/(\log n)^2$ for $g(n)$, for a certain constant $c$. Have a look at the Wikipedia essay on the Goldbach conjecture. $\endgroup$ – Gerry Myerson Dec 22 '14 at 8:15
  • 2
    $\begingroup$ You guys, you're basically in agreement on the essential point here: as $n$ gets larger, so does the number of potential Goldbach sums. A quick and dirty estimate is just that, and not a tight upper or lower bound. But Gerry, I think you'd do well to post your own answer. Another way of saying the same thing is that a Goldbach failure number is probably less likely to exist than an odd perfect number. $\endgroup$ – Lisa Dec 22 '14 at 17:31
  • 2
    $\begingroup$ @Lisa, I did post an answer, over two years ago. $\endgroup$ – Gerry Myerson Dec 22 '14 at 18:34

Let's define g(n) as the number of decompositions of $2n$ into ordered sums of two odd primes (A002372)

The following sum gives the exact value for g(n): $$g(n) = \sum_{i=2}^{\pi(2n)} \pi(2n-p(i))-\pi(2n-1-p(i))$$

where $p(n)$ is the nth prime and $\pi(n)$ is the prime-counting function.

Now if you are looking for something that will work without knowing the primes up to $n$, we can get a pretty good estimate from the sum above. Let's consider the sum of all $g(i)$ from $i=3\to n$: $$ \sum_{i=3}^{n} g(i)$$ From the first sum, we can get: $$\sum_{i=3}^{n} g(i) = 1+\sum_{i=3}^{\pi(2n)} \pi(2n-p(i))$$ If we replace $\pi(n)$ with $\frac{n}{ln(n)}$ and $p(n)$ with $nln(n)$, we know from the prime number theorem that the bigger the interval $n-3$ gets, the more precise our estimation gets: $$\sum_{i=3}^{n} g(i) \approx 1+\sum_{i=3}^{\frac{2n}{ln(2n)}} \frac{2n-iln(i)}{ln(2n-iln(i))}$$ Since: $$ g(n) = \sum_{i=3}^{n} g(i) - \sum_{i=3}^{n-1} g(i)$$ $$ g(n) \approx (1+\sum_{i=3}^{\frac{2n}{ln(2n)}} \frac{2n-iln(i)}{ln(2n-iln(i))})-(1+\sum_{i=3}^{\frac{2(n-1)}{ln(2(n-1))}} \frac{2(n-1)-iln(i)}{ln(2(n-1)-iln(i))})$$ $$ g(n) \approx \sum_{i=3}^{\frac{2n}{ln(2n)}} \frac{2n-iln(i)}{ln(2n-iln(i))}-\sum_{i=3}^{\frac{2n-2}{ln(2n-2)}} \frac{2n-2-iln(i)}{ln(2n-2-iln(i))}$$

The results is quite surprising, yet not very practical. The value of the estimation seems to behave like the real g(n), only in a more regular way:
enter image description here enter image description here


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.