Prime Producing Polynomials

There is a famous old formula n^{2} + n + 41, that gives a prime for all values of n between 0 and 39, before breaking down for n = 40 (40^{2} + 40 + 41 = 1681 = 41*41 and 41^{2} + 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^{2} + 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^{2} + 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^{2} + n + x is not divisible by a particular prime p.

Consider first, that n^{2} + n is always even, and so for n^{2} + 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^{2} + n º 0, 2, 0 (mod 3), respectively. Hence if x º 2 (mod 3), n^{2} + 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^{2} + 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^{2} + 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^{2} + 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^{2} + 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^{2} + n º 0, 2, 6, 5, 6, 2, 0 (mod 7), and so for n^{2} + 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^{2} + n + x for 0 £ n £ N. We find that :

v(11,1000) = 288

v(17,1000) = 366

v(41,1000) = 582

v(101,1000) = 453

v(137,1000) = 339

v(167,1000) = 285

Are there values that beat x = 41 ? Since n^{2} + 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 :

v(19421,1000) = 558

v(27941,1000) = 600

v(55661,1000) = 621

v(72491,1000) = 611

v(237761,1000) = 522

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 :

v(41,10000) = 4149

v(19421,10000) = 4024

v(27941,10000) = 4466

v(55661,10000) = 4545

v(72491,10000) = 4534

v(333491,10000) = 4669

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

v(601037,1000) = 551

v(5237651,1000) = 487

v(9063641,1000) = 446

v(601037,10000) = 4605

v(5237651,10000) = 4520

v(9063641,10000) = 4186

Increasing the search limit again, we obtain the counts :

v(41,100000) = 31985

v(27941,100000) = 35151

v(55661,100000) = 35886

v(72491,100000) = 35625

v(333491,100000) = 36592

v(601037,100000) = 36308

v(5237651,100000) = 36677

v(9063641,100000) = 34693

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^{2} ± 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^{2} ± x is not divisible by any prime up to a certain limit. The smallest survivors x for each of

an^{2} ± x for a = 2, 4, 6 and 10, after applying the standard condition for each prime, are as follows:

p\form |
2n |
4n |
6n |
10n |
2n |
4n |
6n |
10n |

3 |
5 |
1 |
1 |
1 |
1 |
5 |
1 |
5 |

5 |
11 |
7 |
7 |
1 |
1 |
17 |
7 |
11 |

7 |
11 |
37 |
13 |
13 |
19 |
17 |
23 |
11 |

11 |
29 |
37 |
13 |
13 |
31 |
17 |
23 |
23 |

13 |
29 |
37 |
17 |
19 |
181 |
83 |
23 |
71 |

17 |
29 |
37 |
523 |
19 |
181 |
167 |
53 |
137 |

19 |
29 |
163 |
937 |
307 |
199 |
167 |
53 |
1373 |

23 |
29 |
163 |
1223 |
1861 |
199 |
227 |
53 |
3551 |

29 |
4859 |
163 |
1613 |
1861 |
199 |
2273 |
4657 |
3551 |

31 |
5639 |
163 |
3923 |
1861 |
199 |
5297 |
4657 |
3551 |

37 |
5651 |
163 |
3923 |
4297 |
23659 |
5297 |
8297 |
9563 |

41 |
5651 |
26293 |
8447 |
14857 |
32191 |
69467 |
10487 |
12329 |

43 |
5651 |
30493 |
41597 |
16183 |
119131 |
69467 |
14947 |
21569 |

47 |
23669 |
30493 |
41597 |
16183 |
119131 |
116387 |
31607 |
54959 |

53 |
41609 |
30493 |
41597 |
16183 |
119131 |
214037 |
31607 |
54959 |

59 |
41609 |
30493 |
41597 |
835141 |
215011 |
214037 |
68693 |
67169 |

61 |
144251 |
30493 |
41597 |
2144491 |
215011 |
2004917 |
118057 |
303857 |

67 |
7811801 |
106177 |
4674073 |
2144491 |
* |
5472953 |
118057 |
303857 |

71 |
9636461 |
106177 |
4674073 |
7851553 |
* |
8062073 |
118057 |
4108721 |

73 |
* |
2430943 |
4674073 |
7851553 |
* |
8062073 |
140897 |
* |

79 |
* |
* |
* |
8563561 |
* |
* |
140897 |
* |

where * indicates that the smallest survivor is in excess of 10^{7}.

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^{2} ± x for n between 0 and N, and in the negative sign case, be restricted to positive values. Then we have :

w(2,+,29,1000) = 497 w(2,+,4859,1000) = 433 w(2,+,5639,1000) = 472 w(2,+,5651,1000) = 518 w(2,+,23669,1000) = 585 w(2,+,41609,1000) = 602 w(2,+,144251,1000) = 631 w(2,+,7811801,1000) = 403 w(2,+,9636461,1000) = 428 |
w(2,- ,19,1000) = 278 w(2,- ,31,1000) = 324 w(2,- ,181,1000) = 515 w(2,- ,199,1000) = 587 w(2,- ,23659,1000) = 457 w(2,- ,32191,1000) = 411 w(2,- ,119131,1000) = 426 w(2,- ,215011,1000) = 399 |

w(4,+,37,1000) = 363 w(4,+,163,1000) = 525 w(4,+,26293,1000) = 500 w(4,+,30493,1000) = 533 w(4,+,106177,1000) = 595 w(4,+,2430943,1000) = 516 |
w(4,- ,17,1000) = 378 w(4,- ,83,1000) = 324 w(4,- ,167,1000) = 412 w(4,- ,227,1000) = 475 w(4,- ,2273,1000) = 414 w(4,- ,5297,1000) = 496 w(4,- ,69467,1000) = 422 w(4,- ,116387,1000) = 419 w(4,- ,214037,1000) = 370 |

w(6,+,17,1000) = 392 w(6,+,523,1000) = 377 w(6,+,937,1000) = 363 w(6,+,1223,1000) = 428 w(6,+,1613,1000) = 420 w(6,+,3923,1000) = 489 w(6,+,8447,1000) = 484 w(6,+,41597,1000) = 577 w(6,+,4674073,1000) = 422 |
w(6,- ,23,1000) = 309 w(6,- ,53,1000) = 408 w(6,- ,4657,1000) = 419 w(6,- ,8297,1000) = 437 w(6,- ,10487,1000) = 432 w(6,- ,14947,1000) = 452 w(6,- ,31607,1000) = 442 w(6,- ,68693,1000) = 439 w(6,- ,118057,1000) = 474 w(6,- ,140897,1000) = 467 |

w(8,+,29,1000) = 440 w(8,+,4859,1000) = 387 w(8,+,5639,1000) = 420 w(8,+,5651,1000) = 472 w(8,+,23669,1000) = 540 w(8,+,41609,1000) = 546 w(8,+,144251,1000) = 587 w(8,+,7811801,1000) = 413 w(8,+,9636461,1000) = 440 |
w(8,- ,19,1000) = 264 w(8,- ,31,1000) = 283 w(8,- ,181,1000) = 476 w(8,- ,199,1000) = 535 w(8,- ,23659,1000) = 437 w(8,- ,32191,1000) = 422 w(8,- ,119131,1000) = 444 w(8,- ,215011,1000) = 444 |

w(10,+,13,1000) = 398 w(10,+,19,1000) = 473 w(10,+,307,1000) = 369 w(10,+,1861,1000) = 411 w(10,+,4297,1000) = 464 w(10,+,14857,1000) = 494 w(10,+,16183,1000) = 543 w(10,+,835141,1000) = 447 w(10,+,2144491,1000) = 510 w(10,+,7851553,1000) = 451 w(10,+,8563561,1000) = 444 |
w(10,- ,71,1000) = 346 w(10,- ,137,1000) = 444 w(10,- ,1373,1000) = 369 w(10,- ,3551,1000) = 403 w(10,- ,9563,1000) = 396 w(10,- ,12329,1000) = 448 w(10,- ,21569,1000) = 464 w(10,- ,54959,1000) = 429 w(10,- ,67169,1000) = 457 w(10,- ,303857,1000) = 449 |

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^{2} +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^{2} +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^{2} +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^{2} + 29 for n = 0 to n = 28 cannot be bettered by any other value of x when a = 2. However, for 4n^{2} +163, there is a run of 19 primes starting at n = 0. For a = 6, the 17 values of

6n^{2} + 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^{2} + 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^{2} - 181 has a run of length 18 starting at n = 10 and 2n^{2} - 199 has a run of length 17 starting at n = 11; for a = 4, where 4n^{2} - 227 has a run of 13 primes starting at n = 8; for a = 6, where 6n^{2} - 2843 has a run of length 12 starting at n = 50; for a = 8, where 8n^{2} - 199 has a run of length 19 starting at n = 28; and for a = 10, where 10n^{2} - 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^{2} + 144251. The best available is a score of 706 by 2n^{2} - 1584n + 98621. However, this includes counting negative values of primes, which is something I try to avoid.