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 |
A228183 | Semiprimes generated by the Euler polynomial \(n^2 + n + 41\). |
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 |
Figure 6 |
- 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 |
As can be seen in Figure 7, the Euler polynomial does a great job in churning out primes and semiprimes.