Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given some arbitrary natural number $n$, can we always find a $k$ such that $n+k$ and $n-k$ are both prime? Has there been any work on finding an upper bound for $k$?

share|cite|improve this question
up vote 14 down vote accepted

Being able to find such a $k$ for any $n$ is equivalent to the Goldbach conjecture, since it would imply that any even number $2n$ is a sum of two primes, $n+k$ and $n-k$. So we don't yet know if there is always such a $k$, much less an upper bound for the smallest such $k$ (other than something trivial like $k\leq n-2$).

share|cite|improve this answer
If $n$ is even, then there is a stronger bound: $k \le n - 3$. ;) – huon Jun 8 '12 at 3:51

Since your question is equivalent to Goldbach, one can try to apply heuristics to estimate what the upper bound on $k$ ought to be (but proving any such upper bound is strictly harder than Goldbach's conjecture). The number of values of $k$ such that $n+k$ and $n-k$ are both prime should be $\gg n/\log^2 n$, and there should be even more solutions when $n$ has many small prime factors.

Therefore, I would expect on $k$ to be $O(\log^2 n)$ on average, so any upper bound should be at least this large. A Cramér-type heuristic based on random subsets of size $n/\log^2 n$ in $[1,n]$ suggests that $k$ should be no larger than $O(\log^3 n)$ with finitely many exceptions (and those could be subsumed into the implied constant).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.