Take the 2-minute tour ×
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.

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|improve this question
add comment

2 Answers

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|improve this answer
1  
If $n$ is even, then there is a stronger bound: $k \le n - 3$. ;) –  dbaupp Jun 8 '12 at 3:51
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.