Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.
share|improve this question
    
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
3  
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

1 Answer 1

up vote 2 down vote accepted

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: $$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)}$$

share|improve this answer
    
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
1  
@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... –  anorton Feb 28 '13 at 22:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.