Find A Counter-Example to This

  1. Hi!

    Say p(x) is the product of the first x odd prime numbers (e.g. p(4)=3*5*7*11) and i is at least one. Then consider:
    1 < p(x) ± 2*i < (p(x+1)/p(x))2

    My hypothesis is that the above formula, obeying the restrictions, always produces a prime number.
    For example if x=3 and i=13, then p(3)-2*13=79. 79 is bigger than 1 and smaller than 112, therefore it's a prime number.

    I'm not a python programmer, but this code yields prime numbers using the above formula:

    Code (Text):
    from math import ceil

    def is_prime(number):
        if(number < 2):
            return False
        i = 2
        while i <= ceil(number**0.5):
            if(number%i == 0):
                return False
            i = i + 1
        return True

    def f(number_of_primes):
        flag = True
        prime_product = 1
        prime_array = []

        n, i = 3, 0
        while i < number_of_primes:
            if(is_prime(n) == True):
                prime_product = prime_product * n
                prime_array.append(n)
                i = i + 1
            n = n + 1
       
        while True:
            if(is_prime(n) == True):
                largest_prime = n
                break
            n = n + 1

        i = 1
        while True:
            for x in range(len(prime_array)):
                if(i%prime_array[x] == 0):
                    flag = False
                    break

            if flag == False:
                flag = True
                i = i + 1
                continue
           
            n = prime_product - 2*i
            if n <= 1:
                break
            if n < largest_prime**2:
                if is_prime(n) == False:
                    print("NOT : ", n, " : ", i)
                    break
                else:
                    print("NMB : ", n, " : ", i)
            i = i + 1

    def g(number_of_primes):
        flag = True
        prime_product = 1
        prime_array = []

        n, i = 3, 0
        while i < number_of_primes:
            if(is_prime(n) == True):
                prime_product = prime_product * n
                prime_array.append(n)
                i = i + 1
            n = n + 1
       
        while True:
            if(is_prime(n) == True):
                largest_prime = n
                break
            n = n + 1

        i = 1
        while True:
            for x in range(len(prime_array)):
                if(i%prime_array[x] == 0):
                    flag = False
                    break

            if flag == False:
                flag = True
                i = i + 1
                continue
           
            n = prime_product + 2*i
            if n < largest_prime**2:
                if is_prime(n) == False:
                    print("NOT : ", n, " : ", i)
                    break
                else:
                    print("NMB : ", n, " : ", i)
            else:
                break
            i = i + 1

    x = 4 # Enter a non-negative integer
    f(x)
    print("- - - - -")
    g(x)
     
    Scroll down and assign a non-negative integer to x in the code and run it. If the program detects a non-prime then it should output "NOT" followed by the generated number. If the generated number is a prime, then it outputs "NMB". The second number after the second colon is the value of i. So the above example would be displayed as: "NMB : 79 : 13" (excluding the double quotes)

    Thanks for help.
     
  2. jcsd
  3. jedishrfu

    Staff: Mentor

    What is your question? to find a counter example? or to prove your conjecture?
     
  4. I want somebody to prove this wrong, by finding a counter example.

    And I'm really sorry, I forgot to mention that i must not be divisible by any of the primes found in the product p(x).

    So again,
    1 < p(x) ± 2*i < (p(x+1)/p(x))2
    where p(x) is the product of the first x odd prime numbers, and i is a positive integer not divisible by any prime in the product p(x).


    Example: p(4) - 2*514 = 127.
    514 is positive and not divisible by 3, 5, 7, or 11. And 127 is less than 169, so according to the conjecture 127 should be a prime, and it is.
     
  5. jedishrfu

    Staff: Mentor

    Your best strategy here would be to let the program find the counter example by finding a list of primes for input and then running it thru its paces. Also if you could find a related program that can check for primeness of a number you could incorporate it in to the mix.
     
  6. micromass

    micromass 18,543
    Staff Emeritus
    Science Advisor

    It's a true conjecture. Here's a proof:

    First, we note that since ##p(x)## is not divisible by ##2## and ##2i## is divisible by ##2##, then ##p(x) - 2i## is not divisible by ##2##.
    Second, if ##p## is an odd prime occuring in the product of ##p(x)##, then ##p## divides ##p(x)## and ##p## does not divide ##2i##, thus ##p## does not divide ##p(x) - 2i##.

    So we deduce that if ##p## is any prime dividing ##p(x)-2i##, then ##p## cannot occur in ##p(x)##. Thus ##p\geq p(x+1)/p(x)##.

    So, assume that ##p(x) - 2i## is composite, then there are there are two prime numbers ##p## and ##q## that divide ##p(x) - 2i##. Thus we have ##pq\leq p(x)-2i##. But we also have that ##p\geq p(x+1)/p(x)## and ##q\geq p(x+1)/p(x)##. Thus ##pq\geq (p(x+1)/p(x))^2##. So we see that
    [tex](p(x+1)/p(x))^2\leq pq\leq p(x)-2i < (p(x+1)/p(x))^2[/tex]
    which is a contradiction.
     
    1 person likes this.
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted