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.

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