1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Find A Counter-Example to This

  1. Jun 12, 2014 #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. Jun 12, 2014 #2

    jedishrfu

    Staff: Mentor

    What is your question? to find a counter example? or to prove your conjecture?
     
  4. Jun 12, 2014 #3
    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. Jun 13, 2014 #4

    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. Jun 13, 2014 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook