The Euler Polynomial

I've made mention of the Euler polynomial \(n^2+n+41\) before in a post titled Prime Producing Linear Polynomials back in August 28th 2018, that contained the snippet shown in Figure 1. This polynomial is quadratic and not linear of course.

Figure 1

I was reminded of this polynomial again today because my diurnal age of 26447 days featured in OEIS A228183:

A228183

Semiprimes generated by the Euler polynomial \(n^2 + n + 41\).

The sequence runs:

1681, 1763, 2021, 2491, 3233, 4331, 5893, 6683, 6847, 7181, 7697, 8051, 8413, 9353, 10547, 10961, 12031, 13847, 14803, 15047, 15293, 16043, 16297, 17071, 18673, 19223, 19781, 20633, 21797, 24221, 25481, 26123, 26447, ...

This reminded me that the Euler polynomial is not only an excellent producer of primes, at least initially, but also an excellent generator of semiprimes. Up until \(n=420\), the polynomial produces only primes and semiprimes: 280 primes and 138 semiprimes or 67% and 33%. This ratio is very close to 2/3 and 1/3 and so primes are produced twice as often as semiprimes. In this range, it should be noted that \(n=40\) produces 1681 which is \(41^2\) and thus not technically a semiprime because both factors are the same.

If we extend our range to one million, these percentages alter significantly. We find that there are 261080 primes and 458947 semiprimes and thus primes constitute 26.1% while semiprimes constitute 45.9%. About 28% of the numbers generated clearly have three or more factors and, as mentioned earlier, the run of primes and semiprimes stops with \(n=420) because here we encounter the first sphenic number, that is a number with three distinct prime factors. See Figure 2.

Figure 2

Looking at Figure 2, it can be seen that while the primes and semiprimes still abound, the first two sphenic numbers make their appearance when \(n=420\) and \(n=431\). In fact, up to \( n=1000\), there are only 22 sphenic numbers. See Figure 3.

Figure 3

The first number with four distinct prime factors occurs with \(n=2911\) where the generated number of 8476873 = 41 x 47 x 53 x 83. In the range up to 10,000, there are only 21 such numbers. See Figure 4.

Figure 4

The first number with five distinct prime factors does not occur until \(n=38913\) where the generated number 1514260523 = 43 x 47 x 61 x 71 x 173. In the range up to 100,000, there are only 18 such numbers. See Figure 5.

Figure 5

The first number with six distinct prime factors does not occur until \(n=707864\) generates the number 501072150401 = 41 x 43 x 47 x 53 x 71 x 1607. In the range up to one million, there are only five such numbers. See Figure 6.

Figure 6

Up to one million, there is a total of 6627 numbers containing squares e.g. for \(n=999786\), the number generated is 999573045623 = 47 x 47  x 97 x 4664951. These sorts of numbers constitute only 0.6627% of the total. 

In the range up to 100,000, the breakdown is as follows (permalink):

• 31984 prime numbers
• 47937 semiprimes
• 17741 sphenic numbers
• 1661 numbers with four distinct prime factors
• 18 numbers with five distinct prime factors
• 659 numbers that are not square free.

Figure 7 compares these 100,000 numbers which range from \(43\) to \(100000^2+100000+41\) to the first 100,000 numbers which is perhaps not entirely fair but it does provide some basis for comparison. The striking difference in the proportions of numbers containing squares is clearly evident.

Figure 7

As can be seen in Figure 7, the Euler polynomial does a great job in churning out primes and semiprimes.