Quote by Dodo
Post #9 shows examples of primes not of the form p + 2^n. I imagine that finding counterexamples for p  2^n (in particular, checking those on A065381) is harder, since there is no limit to p or 2^n.

I made another conjecture: those primes that cannot be written as p + 2^n could be written as p  2^n
Consider the two sets:
S = set of primes of the form p + 2^n
S' = set of primes of the form p  2^n
If we prove that all primes should be in one of these two sets the infinity of the two sets will be proved.
In fact post #5 shows that the primes not in S may could be found in the infinity of the negative integer line as p + 2^n, which I wonder is the same thing of find this primes in the infinity of the positive integer line as p  2^n. We can search to infinity for them, increasing both p and 2^n until find a match.
This is why [tex]S \subset\ S'[/tex], I think. This is why trying to show that primes are in the form p + 2^n contain "gaps" = p  2^n.
And now, by Tchebychef: for m > 1 there is at least one prime p such that m < p < 2m
if we put m = 2^n, n a natural > 0 ==> 2^n < p < 2^(n+1)
perhaps this theorem could be usefull