# Prime Numbers (again)

1. Nov 16, 2015

### nocat2

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. Nov 16, 2015

### Staff: Mentor

3. Nov 16, 2015

### nocat2

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).

4. Nov 16, 2015

### willem2

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?

5. Nov 16, 2015

### nocat2

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).

6. Nov 16, 2015

### willem2

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.

7. Nov 16, 2015

### nocat2

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.

8. Nov 16, 2015

### nocat2

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.

9. Nov 17, 2015

### nocat2

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.

10. Nov 17, 2015

### micromass

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.

11. Nov 17, 2015

### nocat2

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.

12. Nov 17, 2015

### micromass

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.

13. Nov 17, 2015

### nocat2

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.

14. Nov 17, 2015

### micromass

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?

15. Nov 17, 2015

### nocat2

Not of the form 4x^2+bx+c

16. Nov 17, 2015

### micromass

Then what form does it have?

17. Nov 17, 2015

### nocat2

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.

18. Nov 17, 2015

### micromass

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.

19. Nov 17, 2015

### nocat2

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?

20. Nov 17, 2015

### micromass

So it's a generalization of the Mersenne primes?