Results 1 to 8 of 8

Math Help - Given the first n primes, is there a known function that always produces a new prime?

  1. #1
    Member
    Joined
    Mar 2008
    Posts
    78

    Given the first n primes, is there a known function that always produces a new prime?

    When I first read Euclid's proof that there are infinite primes, I mistakenly thought the product of all n primes plus 1 must also be prime. That is not true. However, are there any other known formulas that can use some or all of the first n primes and be guaranteed to produce a new prime that is not one of the first n? (but not necessarily the n+1th prime)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    You can use Euclid's proof to generate that new prime. If you have some list of primes p_1,p_2,\ldots, p_n, then we consider the number p_1p_2\cdots p_n+1. Although this number may not be prime, you can factor it to get a new prime not on your list.

    For example, if we have p_1=2 and p_2=7, then p_1p_2+1=15. This isn't prime, but if we factor it, we have 15=3\cdot 5, so we have at least one new prime not on our list.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2008
    Posts
    78
    Oh right...I mean one that doesn't require trial and error factoring though.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Not exactly an answer, I started this thread http://www.mathhelpforum.com/math-help/f7/regarding-wilsons-theorem-150928.html
    some time ago, just something I observed.

    In summary, given a prime p, check if ( (p-1)! + 1 ) / p is also prime. If it's not, divide by p again. That should be prime. It works up to p = 101. After that, there's problems with doing the large factorial ...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2010
    Posts
    21
    I wouldn't even bother with using Wilson's Theorom for practical purposes. It's interesting to study, but it's probably faster to check each prime up to sqrt(n) as a divisor of n, n being the number you are testing. This is probably the easiest method to write a program for. There are prime generating polynomials, but they aren't perfect. This one discovered by Euler is considered best:
    x*x - x + 41

    I'm pretty sure that there is no formula like the one you are asking for though.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by browni3141 View Post
    I wouldn't even bother with using Wilson's Theorom for practical purposes. It's interesting to study, but it's probably faster to check each prime up to sqrt(n) as a divisor of n, n being the number you are testing. This is probably the easiest method to write a program for. There are prime generating polynomials, but they aren't perfect. This one discovered by Euler is considered best:
    x*x - x + 41

    I'm pretty sure that there is no formula like the one you are asking for though.
    It can be proven that there are no trivial prime polynomials.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Given the first n primes p_1,...,p_n we have:

    p_{n+1}=\left \lfloor 1 - \log_2\left(-\tfrac{1}{2}+\displaystyle\sum_{d|P_n}{\displaysty  le\frac{\mu(d)}{2^d-1}}\right) \right \rfloor where P_n = p_1\cdot ...\cdot p_n is the product of the first n primes.

    You can see the proof here.

    But I would rather use some brute primality testing if I had to find the next prime, hahaha.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primes that are quadratic residues another prime.
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 16th 2011, 02:10 PM
  2. Twins of primes with one distinct prime factor
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: November 8th 2010, 09:53 AM
  3. [SOLVED] Prove that an isomorphism produces a basis of W
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 1st 2010, 04:05 AM
  4. Prime gaps between primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 18th 2010, 05:11 AM
  5. Replies: 3
    Last Post: January 14th 2008, 04:47 AM

Search Tags


/mathhelpforum @mathhelpforum