Prime Producing Linear Polynomials

An example of a famous prime producing polynomial is \(n^2-n+41 \) which produces primes for values of \(n\) from 1 to 40. These primes are shown below:

41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601

Figure 1 is an excerpt relating to this polynomial from an interesting article on prime-generating polynomials:

Figure 1

Figure 2 shows a table of record prime producing polynomials taken from MathWorld:

Figure 2

However, prime producing linear polynomials get less attention than the above quadratic, cubic and higher order polynomials. Today I turned 25410 days old and discovered that the linear polynomial \(25410 \, n+1 \) has some interesting prime producing qualities. Specifically, it produces primes for values of \(n\) from 1 to 6: 25411, 50821, 76231, 101641, 127051, 152461. As it turns out, 25410 is the first coefficient of \(\ a*n+1\) to produce six primes in a row. The next such number is 26040.

OEIS A237190 displays a list of coefficients of of \(\ a*n+1\) that produce five primes in a row:

10830, 25410, 26040, 88740, 165900, 196560, 211050, 224400, 230280, 247710, 268500, 268920, 375480, 377490, 420330, 451410, 494340, 512820, 592620, 604170, 735750, 751290, 765780, 799170, 808080, 952680, 975660, 1053690, 1064190, 1132860, 1156170, 1532370, 1559580

As can be seen, 10830 is the first coefficient with this property. The OEIS entry also provides a list of the first 1000 such coefficients and this is a good starting point when trying to find coefficients that produce six, seven, eight or more primes in a row. With a little manipulation in a spreadsheet, the OEIS data can be pasted directly into a list set up on SageMathCell.

Of the first 1000 coefficients that produce five primes, only the following go on to produce seven primes in a row (in the range 1 to 247289070): 

512820, 8224860, 22240680, 24462900, 26486460, 62871480, 93784530, 99597960, 139819680, 196474950

Of these only the following go on to produce eight primes in a row: 

512820, 22240680, 26486460, 99597960

All four of the above fail to produce a ninth prime. Thus 512820 is the smallest coefficient that will produce eight primes in a row. In terms of primes produced over a given range and not sequentially, it would seem that 15213870 is the most prolific. It produces 40 primes between \(n+1 \) and \(100 \,n+1\) whereas 512820 produces only 33 in the same range.

What do these numbers have in common. To begin with they are all divisible by 30 and are highly factorable. The following table shows the factorisation and number of divisors for the numbers in OEIS A237190:

Figure 3

It would seem that by adding 1 to multiples of such highly factorisable numbers increases the odds of generating a prime number. Interestingly, for the 1000 coefficients mentioned earlier, the polynomial \(25410 \, n+41\) produces a record 41 primes in the range from 1 to 100, more than for any other coefficient. This naturally leads to an investigation of polynomials of the form \(25410 \, n+p\) where \(p\) is prime. Here is a table of what showed up for primes from 2 to 97:

Figure 4

Clearly \(25410 \, n+97\) wins that race and in fact holds the record for all primes below 1000. For primes up to 100000, \(25410 \, n+5471\) takes the lead with 48 primes and only surrenders it to \(25410 \, n+982231\) with 49 primes when considering primes up to one million. Below are the 49 primes generated by \(25410 \, n+982231\) as n ranges from 1 to 100:

Figure  5

Figure 6

I must say that SageMath makes it incredibly easy to investigate matters such as this. Interestingly, of all the possible coefficients from 1 to 999,999, it is \(25410 \, n+982231\) that produces the highest score of 49 primes out of 100. I was beginning to start to think that this might be something of a record until I went back to \(\ a*n+41\) and thought I'd test all the numbers up to 999,999. The table in FIGURE 6 shows the surprising result. 

The factorisations again show the same pattern as with the earlier numbers:

• 6 = 2 * 3
• 12 = 2 * 2 * 3
• 30 = 2 * 3 * 5
• 60 = 2 * 2 * 3 *5
• 210 = 2 * 3 * 5 * 7

Testing with other primes between 2 and 9999 and coefficients from 1 to 9999 (trying upper bounds of 999999 seemed to overwhelm the SAGE server) showed the best result was with the unpretentious \( 6 \,n+5 \) that produces a total of 56 primes between \(n=1\) and \(n=100\).

However, this 56% hit rate for primes when n is between 1 and 100 is not sustained. For example, setting lower and upper bounds of 4000 and 5000 for \( 6 \,n+5 \) generates 289 primes between 24005 and 30005. This is an average of 289/1000 or about 28.9%.

on August 30th 2021

See related post titled Linear Prime Chains uploaded on December 21st 2022.