8
$\begingroup$

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.

  • 0
    @$E$ricNaslund Thanks for sharing that, good reading.2012-11-01

7 Answers 7

6

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.

  • 1
    @lovers Googling "Rowland sequence" will provide many resources on computing the sequence as well as the shortcut method. [Here](http://programmingpraxis.com/2010/11/12/rowlands-prime-generating-function/2/) is a site which has sample code and a [pdf](http://www.uam.es/personal_pdi/ciencias/fchamizo/posgrado/charla_serafin.pdf) which explores the sequence in depth.2012-11-01
5

There is no known formula which

  1. produces infinitely many primes, and

  2. produces only primes, and

  3. is practical.

  • 0
    I wrote a follow-up question: http://math.stackexchange.com/questions/227363/is-there-a-polynomial-time-algorithm-to-find-a-prime-larger-than-n2012-11-02
3

How about using Mills' constant?

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

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

1

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.

  • 0
    @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.2012-11-04
0

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

  • 0
    @GerryMyerson I do agree it is not at all practical.2012-11-01
0

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.

  • 0
    Oh I get it. You're guaranteed to find *a* new prime each time, either as the number or as one of its factors.2012-12-17
0

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

Please refer http://en.wikipedia.org/wiki/Formula_for_primes#Prime_formulas_and_polynomial_functions

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 .

  • 0
    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 http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html . I will update this page in my answer too so that other will also benefit .2012-11-01