Prime Producing Polynomials

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

Consider first, that n2 + n is always even, and so for n2 + 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 n2 + n º 0, 2, 0 (mod 3), respectively. Hence if x º 2 (mod 3), n2 + 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 n2 + n + x is never divisible by 2 or 3.

Now consider p = 5. Then n º 0, 1, 2, 3 or 4 (mod 5) gives n2 + n º 0, 2, 1, 2, 0 (mod 5) respectively (the symmetric nature of this sequence as usual is no accident). Hence, to ensure that n2 + 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 n2 + 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 n2 + n º 0, 2, 6, 5, 6, 2, 0 (mod 7), and so for n2 + 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 n2 + 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 n2 + 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 an2 ± 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 an2 ± x is not divisible by any prime up to a certain limit. The smallest survivors x for each of
an2 ± x for a = 2, 4, 6 and 10, after applying the standard condition for each prime, are as follows:

 p\form 2n2 + x 4n2 + x 6n2 + x 10n2 + x 2n2 - x 4n2 - x 6n2 - x 10n2 - x 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 107.

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 an2 ± 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 an2 +x, there is particular interest in sequences starting at n = 0, for which there are results from algebraic number theory. For instance, the case 2n2 +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 an2 +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 2n2 + 29 for n = 0 to n = 28 cannot be bettered by any other value of x when a = 2. However, for 4n2 +163, there is a run of 19 primes starting at n = 0. For a = 6, the 17 values of
6n2 + 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 8n2 + 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
2n2 - 181 has a run of length 18 starting at n = 10 and 2n2 - 199 has a run of length 17 starting at n = 11; for a = 4, where 4n2 - 227 has a run of 13 primes starting at n = 8; for a = 6, where 6n2 - 2843 has a run of length 12 starting at n = 50; for a = 8, where 8n2 - 199 has a run of length 19 starting at n = 28; and for a = 10, where 10n2 - 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 2n2 + 144251. The best available is a score of 706 by 2n2 - 1584n + 98621. However, this includes counting negative values of primes, which is something I try to avoid.