This conjecture states that:

 

Every odd positive integer is the sum of a prime and a power of two.

 

Obviously this conjecture was proved false as a counterexample was found:

 

509

 

But, how do I prove that 509 is not the sum of a prime and a power of two?

 

After that, what's the next smallest counterexample after 509?

There are only finitely many powers of two less than 509

I thought Polignac stated that any even number can be written as a difference of primes in an infinite number of ways (a more general version of the twin-prime conjecture) ?

 

<after quickly Googling>

 

But this conjecture (odd = prime + power of 2) also appears to be attributed to Polignac. There's another counterexample at 877, but I'm not sure if this is the next one. The smallest counterexample is 127. It looks like many of these numbers are themselves primes.

Thanks guys! I figured the first part which can be done via contradiction. I'm stuck trying to find a smallest counterexample after 509 though.