Yong-Gao Chen informed me of the paper by F. Cohen and J. L. Selfridge, "Not every number is the sum or difference of two prime powers", Math. Comp. 29(1975), 79-81 where one finds: COROLLARY 47867742232066880047611079 is prime and neither the sum nor difference of a power of two and a prime. If p is the prime in this corollary we have for all powers 2^n the numbers 2^n + p and p - 2^n must be composite. So p will be isolated in the base 2 version of the graph on primes. Yong-Gao also says that the conjecture:
For each "base" b > 1 there is a positive integer (hopefully a prime) k such that for all positive d < b and for all nonnegative n, the numbers k + d*b^n and k - d*b^n are composite.
follows from a well-known conjecture of Erdos: "There are covering systems with arbitrarily large least modulous." Yong-Gao says that the conjecture is not easy, but he thinks he can prove it for small b. Say b = 3 and 4. Not so sure whether he can do b = 10. --Edwin