# Some ways to get a set of primes

What would be some easy way to get a set of primes?

I do not want a way to get a complete set of primes; rather, I just want to see a way of getting some subset of primes - which cardinality would still be infinite.

-
I am not sure but I don't think that's possible. –  Patrick Li Nov 1 '12 at 1:02
See this Wikipedia article: en.wikipedia.org/wiki/Formula_for_primes –  Eric Naslund Nov 1 '12 at 1:43
If I had what you don't want I would be rich. –  AD. Nov 1 '12 at 6:34
@EricNaslund Thanks for sharing that, good reading. –  AD. Nov 1 '12 at 6:42

Consider the sequence $$a_n=a_{n-1}+\gcd(n,a_{n-1}),\ \ a_1=7$$ Then $a_n-a_{n-1}$ is always either a prime or 1.

The introduction of Eric Rowland's paper on this sequence discusses several other prime generating functions which might be worth looking at.

-
This seems very computationally practical indeed. How to reconcile this with @Gerry's answer? Is it known that this sequence generates an infinite number of distinct primes? (If not, this example may not satisfy the conditions of the question.) –  Dan Brumleve Nov 1 '12 at 3:13
Playing with it a bit I noticed it seems to output 1 with increasing frequency and primes ever more rarely. So it is evidently not as practical as it had seemed to me. –  Dan Brumleve Nov 1 '12 at 3:23
@DanBrumleve I just read some parts of the paper and it seems to state that there are some ways to figure out how many '1' gaps appear, and using that shortcut, improves the computation. I am not sure if the paper really is saying this. I am still reading the paper. –  lovers Nov 1 '12 at 3:33
While I am still reading the paper, the question would be: a same prime number appears after few steps, and is there any method to predict when the number will be repeated? –  lovers Nov 1 '12 at 3:34
@lovers Googling "Rowland sequence" will provide many resources on computing the sequence as well as the shortcut method. Here is a site which has sample code and a pdf which explores the sequence in depth. –  E.O. Nov 1 '12 at 4:27
show 1 more comment

There is no known formula which

1. produces infinitely many primes, and

2. produces only primes, and

3. is practical.

-
I think this fits better as a comment than an answer. The term "practical" is highly subjective, and not well defined. Also see: en.wikipedia.org/wiki/Formula_for_primes –  Eric Naslund Nov 1 '12 at 1:44
For that to make any sense you need to precisely define "formula" and "practical". Otherwise it is meaningless. –  Bill Dubuque Nov 1 '12 at 1:44
Sufficient unto the day is the rigor thereof. I try to suit my answer to my perception of the question. If OP is not satisfied, I'm happy to supply more precision. –  Gerry Myerson Nov 1 '12 at 1:48
@GerryMyerson: Apt reply, you have my +1. –  Eric Naslund Nov 1 '12 at 1:53
I think "practical" should be understood as any significant speed-up over naive and straightforward methods like testing if each number is prime. Assuming Cramér's conjecture and using AKS to test each number, it will take polynomial time (in $\log{n}$) to find the next prime this way. But since we don't know if Cramér's conjecture is true, the challenge is to find a method that can be shown to run in polynomial time regardless. Does that seem like a reasonable position to take on "practicality" here? As for "formula" I think it should be understood as any algorithm. –  Dan Brumleve Nov 1 '12 at 4:07

$\lfloor A^{3^n}\rfloor$ is prime for all positive integers $n$.

While "easy", it does not translate into any practical method.

-
But its value is not even known unless the Riemann hypothesis is true. –  asmeurer Dec 16 '12 at 6:58

There was an (I think) interesting article in AMM a while back which noted that if you take a product of consecutive primes $\pi_{n=1}^k p_n$ and divide it into two smaller products $\pi_1=\pi_{n=1}^m p_n$ and $\pi_2 = \pi_{n=m+1}^k p_n,$ if you subtract the two products the difference $d = |\pi_2 - \pi_1|$ will be prime if the difference is small enough (and maybe there were some other requirements).

Ah. The article is by Thompson, American Mathematical Monthly, vol. 60 no. 3 (1953), A Method for Finding Primes. I don't have access to it.

For example (only), $11\cdot7 - 2\cdot3\cdot5 = 47,$ which is evidently prime because it is not a product of any primes less than $11$, and $11\cdot13$ is already too big. This is the general idea.

It too is impractical.

-
Using an asterisk for ordinary multiplication within $\TeX$ is bizarre and uncouth. Once upon a time, on typewriters, one would write 4x3, using the letter x. But in programming languages, one wanted that to be available for use as a variable, and one was limited to the characters on the keyboard, so the asterisk was used as a workaround. But in $\TeX$, one can write $4\times3$ or $4\cdot3$ or $4\otimes3$ or lots of other versions. To use an asterisk then is to eat mashed potatoes with your fingers when silverware is available. (I changed it to \cdot in this posting.) –  Michael Hardy Nov 1 '12 at 4:09
1953 --- yes, that is a while back. Similar topics were dealt with somewhat more recently by Guy, Lacampagne, and Selfridge in a paper entitled, Primes at a Glance. Mathematics of Computation, Vol. 48, No. 177, Jan., 1987. –  Gerry Myerson Nov 1 '12 at 4:48
@GerryMyerson: Finally got around to looking at Primes at a Glance. The authors "believe strongly" that they have whittled things down to finite possibilities for given N. Not exactly a revolution since 1953, and another vote for your answer above. Thanks for the reference. –  daniel Nov 4 '12 at 13:59

You could always use a prime-generating polynomial. There exists a polynomial in $10$ variables such that the set of primes is precisely the positive values of the polynomial as the variables ranges through the non-negative integers. Working with the polynomial might be a bit troublesome though since it's degree is $\sim10^{45}$. Alternatively there is also a polynomial in $26$ (lucky we have that many alphabets) variables with the same properties given here

$$(k+2) (1 - [wz + h + j - q]^2 - [(gk + 2g + k + 1)(h + j) + h - z]^2 - [16(k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2]^2 - [2n + p + q + z - e]^2 - [e^3(e + 2)(a + 1)^2 + 1 - o^2]^2 - [(a^2 - 1)y^2 + 1 - x^2]^2 - [16r^2y^4(a^2 - 1) + 1 - u^2]^2 - [n + l + v - y]^2 - [(a^2 - 1)l^2 + 1 - m^2]^2 - [ai + k + 1 - l - i]^2 - [((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2]^2 - [p + l(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m]^2 - [q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x]^2 - [z + pl(a - p) + t(2ap - p^2 - 1) - pm]^2)$$

-
The catch is that if you just plug in some numbers the chances are you don't get a positive value, so you don't get a prime. –  Gerry Myerson Nov 1 '12 at 1:47
@GerryMyerson I do agree it is not at all practical. –  EuYu Nov 1 '12 at 1:50

You could just use the sieve of Eratosthenes and get all of them.

Euclid proposed this method: Take any finite set of primes, multiply them, add $1$, and then (the hard part) factor the result. It's easy to prove (and Euclid did prove) that all of the resulting primes fail to be in the set you started with. Therefore, no matter how large a finite set of primes you start with, there are still more primes than that.

But this isn't really practical, because of "the hard part", factoring.

-
It's not clear if you are really suggesting this, but $p_n\# + 1$ ($n$ primorial plus $1$) is not always composite or prime. For example, $p_{10}\# + 1$ is composite and $p_{11}\# + 1$ is prime. Maybe someone's discovered a pattern for when this happens, but I've never heard of it. –  asmeurer Dec 16 '12 at 7:02
@asmeurer : As I said, there is the hard part: factoring. $(2\cdot3\cdot5\cdot7\cdot11\cdot13) + 1$ $=30031$ $=59\cdot509$. To start with $30031$ and come up with $59\cdot509$ would have taken me at least ten minutes by hand---maybe more. But read carefully: I didn't say the smallest $n$ primes or anything like that (which "primorial" involves); I said any finite set of primes. And that's what Euclid said too. –  Michael Hardy Dec 16 '12 at 19:08
Oh, well then you're not really saying anything at all. All you're saying is, "if you factor numbers, you can tell if they're prime," which is obvious. There's no need for primorial tricks, which don't get you anything reliable anyway. Just pick bigger numbers if you want bigger numbers :) –  asmeurer Dec 16 '12 at 19:45
@asmeurer : No---you're not reading very well. I'm saying if you take any finite set of prime numbers, then multiply them, then add $1$, then factor the resulting numbers, then the prime numbers that you get will NOT be within the finite set you started with. And that proves you'll never run out of prime numbers. In other words, I'm reminding people what Euclid said, or acquainting them with it if they didn't already know. –  Michael Hardy Dec 17 '12 at 0:44
Oh I get it. You're guaranteed to find a new prime each time, either as the number or as one of its factors. –  asmeurer Dec 17 '12 at 2:29

$$n^2 + n+ 41$$ gives a set of primes for 0 ≤ n < 40 .

This is called euler's prime generating polynomial.

Euler also told that $$n^2 - n+ 41$$ gives primes for n from 0 to 40.

Surprisingly the terms which result on substituting number's from 0 to 40 , gives numbers which differ by consecutive even term 2,4,6,8........ So this feature can be used to primes(off course only within this range) by starting from 41 and adding even terms to successive terms in prime number series .

This is a method to get primes within this limit , despite the 6K+1 and 6K-1 method to get primes (but this also gives composite numbers at times like for eg. k=8 , 6k+1 gives 49 which is not prime ).

Refer http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html for more such polynomials and idea behind such polynomials .

-
If n is 41, or any multiple of 41, by looking at the polynomial it's obvious we'll have a multiple of 41. So what if we use only n that are not multiples of 41 - does the polynomial produce only primes? –  DarenW Nov 1 '12 at 7:07
No , there after the prime number series breaks. Even for the very next number 42 it breaks . This series is just an example . There are many other prime generating polynomials like for example  2n^2 + 11 && holds till n=10 .Refer mathworld.wolfram.com/Prime-GeneratingPolynomial.html . I will update this page in my answer too so that other will also benefit . –  Harish Kayarohanam Nov 1 '12 at 8:47