Prime Generating Functions

. . . the source of all great mathematics is the special case, the concrete example. It is frequent in mathematics that every instance of a concept of seemingly generality is, in essence, the same as a small and concrete special case.

Paul R. Halmos

Glad you came by. I wanted to let you know I appreciate your spending time here at the blog very much. I do appreciate your taking time out of your busy schedule to check out Math1089!

The prime numbers have challenged and perplexed the greatest mathematicians for years. Paul Erdös once said “it will be another million years, at least, before we understand the primes”.

Of course, there are infinitely many primes and the main point of discussion “Is there any formula for generating prime numbers?” In fact, our task is to find a function f : W → P, where W is the set of whole numbers and P is some infinite subset of the set of all primes.

There is no formula for generating prime numbers and so there are no functions that can generate them all. Here, generating function mean a function that gives us all the prime numbers, which is same as to find a way to tell instantly if a number is prime or not.

Euler found a beautiful and simple quadratic polynomial formula P(n) = n² + n + 41 that take a prime values for the integers 0, 1, 2, 3, . . . , 39. The primes generated are 41, 43, 47, 53, 61, 71, . . . , 1601.

Thus, it produces 40 primes before yielding a composite result 1681 = 41² (the smallest composite number for this formula) when n = 40. Also, P(41) = 41 × 42 + 41 = 41 × 43.

If 41 divides n, it divides P(n) too. Furthermore, since P(n) can be written as n(n + 1) + 41, if 41 divides (n + 1) instead, it also divides P(n).

Another close formula to the above is Q(n) = n²  ̶ n + 41 that take a prime values for the integers 0, 1, 2, 3, . . . , 40. The primes generated are 41, 41, 43, 47, 53, 61, . . . , 1601.

Thus, it produces 41 primes before yielding a composite result 1681 = 41² (the smallest composite number for this formula) when n = 40. Note that Q(n) gives the same 40 primes as P(n) for n = 1, 2, . . . , 40.

We now consider the expression R(n) = n²  ̶ 79n + 1601, where n is a whole number. By transforming the formula to R(n) = (n  ̶ 40)² + (n  ̶ 40) + 41, primes are obtained for 80 consecutive integers corresponding to the 40 primes given by the above formula.

The formula S(n) = 2n² + 11 can generate primes for n = 0, 1, . . . , 10 and it can produce 11 distinct primes. Another close formula to the above T(n) = 2n² + 29 produce primes for n = 0, 1, . . . , 28 and it can produce 29 distinct primes.

We now consider the expression U(n) = 103n²  ̶ 3945n + 34381, where n is a whole number. This formula found in 1988, produces 43 distinct prime values for n = 0, 1, 2, . . . , 42.

The formula V(n) = 36n²  ̶ 810n + 2753, where n is a whole number primes produces 45 prime values.

Of course, there are many more such functions which can produce a few prime numbers.

Your suggestions are eagerly and respectfully welcome! See you soon with a new mathematics blog that you and I call “Math1089 – Mathematics for All!“.