# Method to solving this proof with a java app

I'm writing a program to solve this proof, but I don't know how to go about solving it. If anyone has some insight it would be great help. Thanks

• For every odd integer $n$, $3 \leq n \leq 199$, there exists an integer $m \geq 0$, and a prime number $p$, such that $n = 2^{m} + p$.
-
Recursively generate powers of two less than $n$, and check if the difference between $n$ and $2^m$ is prime using an appropriate method? – J. M. Nov 18 '10 at 23:56
You mean a search-routine that's simpler than brute force? – Unreasonable Sin Nov 18 '10 at 23:58
Ingenious. That's basically like solving for p, then checking if it's prime, right? – Trevor Arjeski Nov 19 '10 at 0:00
I planned on doing brute force. – Trevor Arjeski Nov 19 '10 at 0:01
As there are only 46 primes (one of which you don't need) less than 199 and only 7 powers of 2, you could just make the two lists, list the 7*45 sums, sort them, and check. – Ross Millikan Nov 19 '10 at 0:09

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$

1. Generate (or obtain) a sorted array of all primes less than $N$. (This is $\pi(N)$, where $\pi$ is the prime counting function)
2. 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.
3. Iterate through all the odd numbers less than $N$ but greater than 3 (there are about $N/2$ of these).
1. For each odd number, iterate through the powers of two
2. 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.
3. 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}

-
I had solved this on my own 3 years ago, but I really appreciate the time you took to write this answer. – Trevor Arjeski Feb 28 '13 at 15:04
@TrevorArjeski wow. I'm impressed you actually came back to look at this! :) I figured you'd have solved it (3yrs is a while to work on a problem), but thought it was an interesting question and enjoyed writing up a solution... – apnorton Feb 28 '13 at 22:22