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


    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
    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
    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
    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
    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
    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
    So it's a generalization of the Mersenne primes?
  22. Nov 17, 2015 #21
    No, not at all related.
  23. Nov 18, 2015 #22
    In the search for large primes and semi-primes one should test numbers of the form

    N = p(x) - 2y^n

    Where p(x) is 3*5*7*11*....*x
    and x is some last prime in consecutive list.

    y>x and y is prime

    n is largest possible that yields positive N

    Smaller n works with reduced probability of prime.
  24. Nov 18, 2015 #23
    The success rate goes down with increasing x

    I've used the largest prime below X for x, and tried all the primes between X and X+1000 for y, as well as all the n possible.
    Digits is the number of decimal digits of p(x). Nearly all the primes found are very close to p(x).
    Code (Text):

    X    primes    cand.    perc.    digits

    100    205       2152    9.5      39
    200    234       4427    5.3      84
    300    206       6244    3.3      122
    400    238       7960    3.0      164
    The last calculation took 20 minutes, no doubt mostly spent calling isprime() in pari
  25. Nov 18, 2015 #24
    Thanks for running that. No surprise the success rate decreases with increasing x. It is encouraging that the rate of decrease slows as fast as shown.
    It appears this method is at least 10 times as successful for 164 digit primes as would be expected from random guesses.
    I suggest it would be more successful than searching for mersenne primes.
  26. Nov 18, 2015 #25
    I'm surprised nearly all the primes found were "very close to p(x)".
    Certainly, the closer the output is to p(x) the more likely it is to be prime - I'm just surprised they are very close.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook