Prime Producing Polynomials

There is a famous old formula n² + n + 41, that gives a prime for all values of n between 0 and 39, before breaking down for n = 40 (40² + 40 + 41 = 1681 = 41*41 and 41² + 41 + 41 = 1763 = 41*43). However, if we keep going, we find that the sequence of numbers given by this formula continues to provide a regular supply of primes with a density much higher than we would normally expect. In particular, for 0 £ n £ 1000, there are 582 such primes, which is by far the highest score for any x < 100.

Let us consider the more general formula n² + n + x for x > 0. There are two obvious questions to ponder: what is so special about x = 41 that there are so many primes in the sequence ?; are there other numbers that show the same tendency ? It is no accident that even for composite values of n² + n + 41, no factor less than 41 can be found. This suggests that there are divisibility patterns involved, and that we should be able to find values of x such that n² + n + x is not divisible by a particular prime p.

Consider first, that n² + n is always even, and so for n² + n + x to be prime, we at least required that x is odd (except for the trivial case x = 2 and n = 0). This provides us with the simple restriction, that x º 1 (mod 2).

Now consider divisibility by 3. We have n º 0, 1 or 2 (mod 3), and this provides us with the fact that n² + n º 0, 2, 0 (mod 3), respectively. Hence if x º 2 (mod 3), n² + n + x is never divisible by 3.

Combining the two conditions x º 1 (mod 2) and x º 2 (mod 3), we get x º 5 (mod 6). If this holds, then n² + n + x is never divisible by 2 or 3.

Now consider p = 5. Then n º 0, 1, 2, 3 or 4 (mod 5) gives n² + n º 0, 2, 1, 2, 0 (mod 5) respectively (the symmetric nature of this sequence as usual is no accident). Hence, to ensure that n² + n + x is never divisible by 5, we require
n º 1 or 2 (mod 5).

If we combine this condition with the previous, we obtain x º 11 or 17 (mod 30).

By simply considering the first 3 primes, we have managed to reduce the number of x for which n² + n + 1 can never be divisible by 2, 3, or 5 to 1 out of every 15. Elsewhere, it is shown that if a number survives trial division even to a relatively small limit, this substantially increases the likelihood that it is prime.

Continuing for p = 7, n º 0 to 6 (mod p) provides n² + n º 0, 2, 6, 5, 6, 2, 0 (mod 7), and so for n² + n + x never to be divisible by 7, we require x º 3, 4 or 6 (mod 7). Combining this with the previous conditions, we obtain x º 11, 17, 41, 101, 137 or 167 (mod 210) never divisible by either 2, 3, 5 or 7. We can now see where our original value x = 41 fits in.

Let v(x,N) be the number of primes of the form n² + n + x for 0 £ n £ N. We find that :

Are there values that beat x = 41 ? Since n² + n + 41 is divisible by 41 whenever n is divisible by 41, let us continue our procedure as far as p = 41.

For p = 11, we find that x cannot be divisible by 11 whenever x º 1, 4, 6, 7, or 8 (mod 11). the analogous results for
p = 13 to p = 41 are :

For p = 13 : x º 2, 3, 4, 5, 8, 12 (mod 13)

For p = 17 : x º 1, 2, 3, 6, 7, 8, 10, 16 (mod 17)

For p = 19 : x º 2, 3, 6, 9, 10, 11, 12, 14, 16 (mod 19)

For p = 23 : x º 1, 7, 8, 9, 10, 12, 14, 15, 18, 19, 22 (mod 23)

For p = 29 : x º 1, 3, 4, 5, 7, 8, 10, 11, 12, 14, 19, 20, 24, 25 (mod 29)

For p = 31 : x º 2, 5, 9, 10, 12, 13, 15, 16, 17, 18, 22, 24, 26, 27, 28 (mod 31)

For p = 37 : x º 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 20, 22, 23, 26, 30, 33, 34, 36 (mod 37)

For p = 41 : x º 1, 2, 3, 4, 5, 7, 9, 12, 14, 16, 17, 18, 19, 20, 24, 25, 28, 34, 37, 38 (mod 41)

For p = 11 and 13, the smallest survivor is 17, and then for the primes between 17 and 37, the smallest survivor is 41. Searching for values of x that satisfy all of the above conditions, the first few values are 19421, 27941, 55661, 72491 and 237761. These provide the following counts :

Our original value x = 41 provides the highest score for v(x,1000) for any x < 27941. For high x values, the counts gradually drop off, affected by the increase in the number of primes available as factors, an effect cancelled out if we increase the limit N.

Continuing for p = 43 and p = 47, the additional conditions on x are :

for p = 43 : x º 3, 4, 6, 8, 9, 12, 15, 17, 20, 21, 22, 24, 25, 26, 27, 28, 32, 34, 35, 36, or 42 (mod 43), and

for p = 47 : x º 1, 2, 7, 13, 14, 15, 16, 18, 19, 20, 21, 24, 26, 28, 29, 30, 33, 36, 37, 39, 40, 44 or 46 (mod 47)

The smallest survivor at p = 43 remains 19421, but then moves up to x = 333491 at p = 47. Increasing the range of n, we obtain the counts :

If we move to p = 53, the condition is

x º 1, 5, 6, 7, 8, 9, 10, 13, 14, 17, 18, 19, 20, 21, 22, 26, 28, 32, 35, 37, 38, 42, 43, 45, 48 or 52 (mod 53)

and the the smallest survivor is x = 601037, which remains the smallest survivor after application of the p = 59 condition.

For p = 61, the same process results in a smallest survivor of x = 5237651, and for p = 67, a smallest survivor of
x = 9063641. For comparison, we have

Increasing the search limit again, we obtain the counts :

At p = 71, the smallest survivor is 12899891.

At p = 73 and 79, the smallest survivor is 24073871.

At p = 83, the smallest survivor is 28537121.

At p = 89, 97, 101 and 103, the smallest survivor is 67374467.

At p = 107, the smallest survivor is 146452961.

For interest, v(12899891,100000) = 36836, which is the highest to that point. However, a truer picture requires increasing the limit on n to one million.

Note that other values of x which score relatively highly can be obtained by applying all but one or two of the above conditions for small primes, e.g. not enforcing the p = 11 condition.

Another form of interest is an² ± x (x > 0). In this case, whenever a is odd, every second term is divisible by 2, so we shall restrict ourselves to the case a even. In an exactly analogous way to the above, for each a we can apply modular conditions on x so that an² ± x is not divisible by any prime up to a certain limit. The smallest survivors x for each of
an² ± x for a = 2, 4, 6 and 10, after applying the standard condition for each prime, are as follows:

where * indicates that the smallest survivor is in excess of 10⁷.

I have missed out a = 8 in the above as this case has exactly the same divisibility pattern has for a = 2. Of course, since the actual formula is different, this does not mean that the same primes are found.

Let w(a,± ,x,N) be the count of primes of the form an² ± x for n between 0 and N, and in the negative sign case, be restricted to positive values. Then we have :

In the negative cases, for large x, fewer and fewer of the possible values are positive, so the counts drop off unless a higher limit is chosen.

As well as counting the number of primes generated by these formulae, it is also worthwhile to look for sequences of consecutive values of n that all give primes. For an² +x, there is particular interest in sequences starting at n = 0, for which there are results from algebraic number theory. For instance, the case 2n² +x is prime for all n from 0 to x- 1 for the values x = 3, 5, 11 and 29, and no others. Similar results exist for a > 2. Hence an² +x is prime for all n from 0 to x- 1 for a = 4 and x = 3 or 7, a = 6 and x = 5, 7, 13, or 17, a = 10 for x = 3, 7, 13 and 19. The a = 8 case does not appear to have any such x. The 29 consecutive prime values of 2n² + 29 for n = 0 to n = 28 cannot be bettered by any other value of x when a = 2. However, for 4n² +163, there is a run of 19 primes starting at n = 0. For a = 6, the 17 values of
6n² + 17 for n = 0 to n = 16 seem to be best possible. For a = 8, there is a run of 15 prime values of the form 8n² + 29 starting at n = 0. For a = 10, the x = 19 sequence starting at n = 0 seems to be the longest possible.

In the negative case, there is no special case for sequences starting at n = 0. However, the best are : for a = 2, where
2n² - 181 has a run of length 18 starting at n = 10 and 2n² - 199 has a run of length 17 starting at n = 11; for a = 4, where 4n² - 227 has a run of 13 primes starting at n = 8; for a = 6, where 6n² - 2843 has a run of length 12 starting at n = 50; for a = 8, where 8n² - 199 has a run of length 19 starting at n = 28; and for a = 10, where 10n² - 137 has a run of length 12 starting at n = 28.

The best score for n = 0 to 1000 of the formulae considered above is 631 achieved by 2n² + 144251. The best available is a score of 706 by 2n² - 1584n + 98621. However, this includes counting negative values of primes, which is something I try to avoid.

URL : www.glasgowg43.freeserve.co.uk/primpoly.htm