Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime Numbers

  1. Oct 11, 2008 #1
    Ok, here's a challenge for you guys.

    Lets figure out a pattern for prime numbers.
     
  2. jcsd
  3. Oct 11, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Right. Get back to you with the solution as soon as I have a moment.
     
  4. Oct 11, 2008 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ooh, I've figured it out. The prime numbers appear precisely at those integers that have exactly two positive factors!
     
  5. Oct 11, 2008 #4
    Do you mean besides 1 and the number itself?
     
  6. Oct 11, 2008 #5
    Um, correct me if I'm wrong, but prime numbers don't have factors.
     
  7. Oct 11, 2008 #6
    How can a number not have factors?
     
  8. Oct 11, 2008 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Chime in, everyone:

    A prime number is divisible by precisely two positive factors, one and itself.
     
  9. Oct 11, 2008 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    They're all either of the form 30a + b, where b is in {1, 7, 11, 13, 17, 19, 23, 29}, or in the 'exceptional set' {2, 3, 5}.
     
  10. Oct 12, 2008 #9
    Of course, a lot of non-primes like 49 or 77 fit the pattern as well. :)

    There should be some sort of FAQ on these forums, since this subject (and others) repeat very often, and I believe you (CR) posted a 'prime formula' just a few months ago.

    Nor I can say I understand the OP's motivation. This ain't no circus, yo.
     
  11. Oct 12, 2008 #10
    Prime numbers have exactly two (positive integer) divisors: 1, and the number itself. after all, N = 1 * N, and N = N * 1.

    As far as I know, some patterns have been found which generate only prime numbers, but no pattern has been found which generates all of them. In general, to see if some large numer is prime, one has to try all possible divisors. (In practice some divisors, such as 2, 3 and 5, are readily discernible if the number is written in base 10.)

    One interesting pattern is the following. If the last prime number found is M, calculate N = M! + 1, or 1 * 2 * 3 *....*(M-1) * M + 1. Now, either N is itself prime, or else it has a prime divisor larger than M. This recipe generates an infinite number of primes, therefore proving that there is no largest prime.

    Starting with 1, the recipe gives the sequence 2, 3, 7, 71... and already misses 5.
     
  12. Oct 12, 2008 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Asymptotically, almost all numbers of the form I posted are composite.

    The only people who would read the FAQ are those who don't need to read it.

    I did post a formula for primes not too long ago.

    It's widely-believed, though absolutely false, that it is a 'great unsolved problem' in math to find patterns in prime numbers or a formula for primes. Amusingly, little is further from the truth -- any person can easily find patterns in the primes, and formulas/algorithms for the primes are a dime a dozen.
     
  13. Oct 12, 2008 #12
    Show us an infinite pattern which generates ONLY PRIME numbers and you will be famous.
     
  14. Oct 12, 2008 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    When do I get my accolades?
     
  15. Oct 12, 2008 #14

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    My mousepad (an old sheet of scrap paper) lists nine different infinite patterns that generate only prime numbers: the sieves of Eratosthenes, Pritchard (x2), Dunten-Jones-Sorenson, Atkin-Bernstein, Galway (x2), and Sorenson, along with Bernstein's version of AKS. (It also mentions the Miller-Rabin test, but that generates infinitely many composites -- though it still produces mostly primes.) I could probably list ten more prime-generating patterns/methods/algorithms off the top of my head.

    Admittedly, all of these people are famous to some degree. But less complicated or worthwhile methods are created all the time. Further, there are methods (like the LL test for Mersenne primes) that are conjectured to produce infinitely many primes but no one has proven it yet.
     
    Last edited: Oct 12, 2008
  16. Oct 13, 2008 #15
    I believe the 'great unsolved problem' is a closed form for the sequence of primes. This thread won't rest in peace until you copy it *again*, or paste a link, or something.

    In the meantime, Google is wise, Google is good. http://mathworld.wolfram.com/PrimeFormulas.html
     
  17. Oct 13, 2008 #16

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yes, because an amazing achievement like Sorenson's pseudosquare sieve (deterministically detecting primes in log-squared space as fast as Miller-Rabin!) is somehow less meaningful than some computationally worthless double summation based on Wilson's theorem. :rolleyes:
     
  18. Nov 27, 2008 #17
    There are a number of algorithms to derive primes, it goes without saying - but these don't resolve to, or immediately suggest any simple predictable "pattern". Yet the distribution of the primes does have what seems to be apparent "pattern", it could be said, anyway. Against this, Mandlebrot patterns aren't apparent by just glancing at the equation for that set, either.
     
  19. Nov 29, 2008 #18
    what exactly is Sorenson's pseudosquare sieve?
     
  20. Nov 29, 2008 #19

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    The basic idea doesn't actually come from Sorenson but from the pseudosquare primality test of Lukes-Patterson-Williams. Most of the basic ideas can be found here:
    http://www.ams.org/mcom/1996-65-216/S0025-5718-96-00762-4/S0025-5718-96-00762-4.pdf

    The original LPW paper is "Some results on pseudosquares", Math. Comp. 65 (1996). The Sorenson paper that turned it into an efficient sieve is on SpringerLink here:
    http://www.springerlink.com/content/914n525q4801q7q1/
    (1-page preview; full text at some colleges; also printed as a chapter in Algorithmic Number Theory)
     
  21. Dec 1, 2008 #20
    Maybe I am misreading what some of the more prominent people in this thread are saying, but a function such that

    f(n) = pn

    would surely be a feat which guarantees a spot in mathematical history?

    The trouble with the approaches that already exist seem to be that either they don't generate all, or when they generate all, they also generate a lot of garbage (like negative values that have to be discarded and such).

    I as a complete nub in the field of math I feel like making a prediction (while I am still sufficiently naive to do so):

    Any breakthrough in a sequentially generating prime formula will rely on a breakthrough in factoring, which in turn will rely on refinement of modular arithmetic.

    so there.

    k
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prime Numbers
  1. Prime Numbers (Replies: 44)

  2. Prime Numbers (Replies: 24)

  3. Prime number. (Replies: 7)

  4. Prime Numbers (Replies: 1)

Loading...