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$?
Primes of the form $n\pm k$
2 Answers
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$).
-
1If $n$ is even, then there is a stronger bound: $k \le n - 3$. ;) – 2012-06-08
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).