Is This Simple Algorithm the Key to Finding the Next Largest Prime Number?

[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?

 

[DrClaude]

Have a look at the discussion in https://www.physicsforums.com/threads/prime-numbers-formula.838617/

 

[nocat2]

Have a look at the discussion in https://www.physicsforums.com/threads/prime-numbers-formula.838617/

Yes, thanks. I am aware of the many false claims made in this particular area. Note that I referred 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).

 

[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?

 

[nocat2]

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?

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

 

[willem2]

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

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.

 

[nocat2]

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.

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.

 

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

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.

 

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

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.

 

[micromass]

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.

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.

 

[nocat2]

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.

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.

 

[micromass]

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.

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.

 

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

 

[micromass]

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.

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?

 

[nocat2]

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

 

[micromass]

Then what form does it have?

 

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

 

[micromass]

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.

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.

 

[nocat2]

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.

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?

 

[micromass]

So it's a generalization of the Mersenne primes?

 

[nocat2]

So it's a generalization of the Mersenne primes?

No, not at all related.

 

[nocat2]

No, not at all related.

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.

 

[willem2]

In the search for large primes and semi-primes one should test numbers of the form

N = p(x) - 2y^n

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

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

 

[nocat2]

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.

 

[nocat2]

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

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

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.

 

[willem2]

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.

You said that you would get the best results for the largest possible n, which would result in the smallest prime and a number with the largest difference to p(x),
This doesn't seem the case in practice. If n is smaller than the largest possible n, 2*y^n will be at least a factor y smaller than the primorial.

I tested some intervals of 10000 numbers, close to 10^164. After eliminating everything that is divisible by numbers up to 400, about 9200-9300 candidates remain, about 230-270 of them are primes, between 2.6% and 2.9%. Your algorithm doesn't seem to be a very large improvement, although it does seem to do a bit better than selecting random numbers combined with trial division. .
It is a bit faster than trial division, but If large numbers of prime numbers are desired, the sieve of erathostenes will be very much faster, because all computations, except for the first number in the sieve can be done with just addition of ordinary integers.
A problem with your method is also that the primorial will become very large, so it's very hard to produce a prime candidate of a desired size.

 

[nocat2]

It is a bit faster than trial division, but If large numbers of prime numbers are desired, the sieve of erathostenes will be very much faster, because all computations, except for the first number in the sieve can be done with just addition of ordinary integers.
A problem with your method is also that the primorial will become very large, so it's very hard to produce a prime candidate of a desired size.

To clarify, I am not looking to produce a large number of primes. I am looking to produce a small number of very large primes. In particular, I see this as a viable method to find a new largest prime. It's for sport, really.