127 and 331 are counterexamples. It was a conjecture of Polignac that every odd number can be written as a sum of an odd prime and a power of two, but many counterexamples have been found. They are called "obstinate numbers". Erdos has proved that there is an infinite arithmetic progression of obstinate numbers.

127 and 331 are counterexamples. It was a conjecture of Polignac that every odd number can be written as a sum of an odd prime and a power of two, but many counterexamples have been found. They are called "obstinate numbers". Erdos has proved that there is an infinite arithmetic progression of obstinate numbers.

Edit (response to the added question): There will be infinitely many such prime counterexamples as a corollary to Erdos' theorem and Dirichlet's theorem on arithmetic progressions. See "Not always buried deep: selections of problems from analytic and combinatorial number theory" by P. Pollack.