I'm answering so this is so it gets off the "Unanswered Questions" list... :)
Algorithm
Here's a "brute force" (but somewhat fast) approach for a generalized upper limit of $N$. (This case is $N=199$
- Generate (or obtain) a sorted array of all primes less than $N$. (This is $\pi(N)$, where $\pi$ is the prime counting function)
- Generate a sorted array of all powers of two less than $N$. (There are $\lfloor\log_2(N)\rfloor$ of these.) This could be done dynamically (not stored in array) using bitshifts.
- Iterate through all the odd numbers less than $N$ but greater than 3 (there are about $N/2$ of these).
- For each odd number, iterate through the powers of two
- Subtract the power of two from the odd number, and do a binary search on the prime array to see if the difference is prime.
- If you find a prime, the statement has been verified for the odd number. Continue to next odd.
Runtime:
Approximate $\pi(N) = \text{Li}(N)$, where $\text{Li}(x)$ is the logarithmic integral. Also assume we are given the prime list. Then, we have an upper bound of the runtime: $$\mathcal{O}\left(\frac{N}{2}\lfloor\log_2(N)\rfloor\cdot\log_2(\text{Li}(N))\right)\approx \mathcal{O}\left(N\lg(N)\cdot\lg(\text{Li}(N))\right)$$
(The first factor from iterating through odd numbers, the second from the number of powers of two, and the third factor from the binary search on the prime array.)
Java Code
public class MathPost {
static final int N = 199;
//Assumed to have all primes under N
static int[] primeArray = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199};
public static void main(String[] args) {
boolean isTrue = true;
boolean trueForAPowerOfTwo = false;
int powerOfTwo = 1;
int supposedPrime = 0;
int oddNumber;
for (oddNumber = 3; oddNumber <= N; oddNumber += 2) {
//We don't know if the proposition is true for this odd number with any power of two yet
trueForAPowerOfTwo = false;
for (int power = 0; (1 << power) < oddNumber; power++) {
//Find the power of two we are considering
powerOfTwo = 1 << power;
//Determine the difference of the power of two and the odd number.
supposedPrime = oddNumber - powerOfTwo;
//The following sets the "wasTrueForAPowerOfTwo" variable to true if we find a prime difference
trueForAPowerOfTwo |= java.util.Arrays.binarySearch(primeArray, supposedPrime) >= 0;
}
isTrue &= trueForAPowerOfTwo;
if (!isTrue) break;
}
System.out.printf("The proposition is %s\n", isTrue);
if (!isTrue) {
System.out.printf("Counterexample: The odd number %d cannot be expressed as desired.\n", oddNumber);
}
}
}
The Result
The statement is false. Take the odd (prime) number $127$. It cannot be expressed as the sum of a power of two and another prime:
\begin{align}
127-1 &= 126 &\text{ (Not prime)}\\
127-2 &= 125 &\text{ (Not prime)}\\
127-4 &= 123 &\text{ (Not prime)}\\
127-8 &= 119 &\text{ (Not prime)}\\
127-16 &= 110 &\text{ (Not prime)}\\
127-32 &= 95 &\text{ (Not prime)}\\
127-64 &= 63 &\text{ (Not prime)}
\end{align}