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!

Prime Numbers (again)

  1. Nov 16, 2015 #1
    I have a simple algorithm that appears to generate many primes (or semi-primes with relatively large factors). By 'relatively large', I mean large in relation to inputs.

    I have tested this algorithm for small values, and of the forty (six-digit) numbers produced, 22 are prime, 16 are semi-prime (with at least one relatively large factor) and only two have three prime factors (exponents 1).

    This is easily extended to very large numbers and I expect the results would remain similar. Is this of interest to anyone?
     
  2. jcsd
  3. Nov 16, 2015 #2

    DrClaude

    User Avatar

    Staff: Mentor

  4. Nov 16, 2015 #3
    Yes, thanks. I am aware of the many false claims made in this particular area. Note that I refered to my method as an algorithm. It certainly is conducive to programing but is not an algebraic solution. Also, I propose that outputs are rich in primes, not that they are always primes. Really, I'm just throwing out the stats to learn if they are encouraging (or not).
     
  5. Nov 16, 2015 #4
    Trial division up to 41 will also leave about 55% primes with six-digit numbers. That's only 13 divisions. Is your method faster than that?
     
  6. Nov 16, 2015 #5
    My algorithm is not so much a test for primality as it is a generator of primes (and semi-primes with at least one factor significantly greater than input).
     
  7. Nov 16, 2015 #6
    My algorith can do that too. Pick a random number and trial divide by the first 13 primes. You get 55% primes, and I do not doubt that a large number of the rest would be semi primes, since the numbers have no small factors. If your algorithm can't beat this, it's no good.
     
  8. Nov 16, 2015 #7
    Well, I guess mine would have the advantage that it only requires the first 7 primes for a six-digit generated prime, so it is possibly twice as fast.
     
  9. Nov 16, 2015 #8
    And of course with larger number digits generated, the greater the savings on required first primes. From what I can see, the savings (time, processing) would be substantial.
     
  10. Nov 17, 2015 #9
    How about this:
    I have a quadratic function that gives >50% prime and >40% semiprime results for any prime number input less than 350. The results are majority six-digit primes.
     
  11. Nov 17, 2015 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Ah function like ##n^2 - n + 41##? This is not new. The high frequency of primes generated by a quadratic function has been noted already. The most dramatic visualization of this is the Ulam spiral which shows a lot of "lines" indicating a quadratic relationship between primes. https://en.wikipedia.org/wiki/Ulam_spiral

    If you meant something else with quadratic function, then sorry for the irrelevant post.
     
  12. Nov 17, 2015 #11
    I'm familiar with that quadratic, and no, mine is different. Also note, the quadratic I have is exceptionally prime rich - when inputs are primes.
    And I suspect there will prove to be hundreds of thousands of these quadratic types that will be similarly prime rich.
    Oh, and quadratics are only one subset. There are also many such prime rich cubics, quartics, etc.
    The general form is an n-degree polynomial with restrictions on n depenedent on the initial values.
     
  13. Nov 17, 2015 #12

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Did you check the wikipedia link and more specifically the Hardy-Littlewood Conjecture F? If the conjecture is true (to which all the numerical evidence points), then you can use it to predict exactly which polynomial is prime rich and which are not. As you can see in that link, a quadratic has been found which generates primes 11 times more often than by taking random numbers. This is the prime-richest quadratic ever found. So what you're doing is not new and follows immediately from the Hardy-Littlewood Conjecture F.
     
  14. Nov 17, 2015 #13
    My quadratic(s) are not of that form and I suspect the one I have tested is 27 times more likely to generate a six-digit prime than by chance.
     
  15. Nov 17, 2015 #14

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    It is not of the form ##\alpha n^2 + \beta n + \gamma## for some ##\alpha,\beta,\gamma##? Then you shouldn't call it a quadratic. What is the form of your function?
     
  16. Nov 17, 2015 #15
    Not of the form 4x^2+bx+c
     
  17. Nov 17, 2015 #16

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Then what form does it have?
     
  18. Nov 17, 2015 #17
    Before I disclose that, I would like to know if these results are of interest.
    Input 27 prime numbers from 23 through 149 and the output gives 17 of 27 as six-digit primes. Remaining 10 are almost entirely six-digit semi-prime.
     
  19. Nov 17, 2015 #18

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Depends entirely on the form of your function. If you found a quadratic polynomial ##\alpha x^2 + \beta x + \gamma## which generates 27 times more primes than choosing numbers randomly, then yes, this would be of interest. But I can think of other situations where this would not be of interest.
     
  20. Nov 17, 2015 #19
    The data I gave is off slightly (I was using a printout of primes without having my reading glasses) but the numbers are close enough.
    Form is T=a-x^n
    Works nicely for n>=2 so long as T (test) remains positive.
    Is this form of interest?
     
  21. Nov 17, 2015 #20

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    So it's a generalization of the Mersenne primes?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prime Numbers (again)
  1. Prime Number (Replies: 15)

  2. Prime numbers (Replies: 12)

  3. Prime numbers (Replies: 8)

  4. Prime Numbers (Replies: 1)

Loading...