2

Euler famously discovered the polynomial $f(n) = n^2 + n + 41$, which generates prime numbers for $n = 0,1,2,3,…,40$, but not $n = 41$ ($41^2 + 41 + 41$ is obviously divisible by $41$).

Hearing of this result made me curious to see if there was a polynomial that could generate all possible primes. However, I learned that it has been proven that no polynomial $f(n) = a_n x^n + … + a_1 x +a_0$ can return primes for all $n$ (proven informally by Richard E. Borcherds in his first number theory lecture, 13:44-16:45). This is quite a disappointing result, especially since Euler’s seems to come pretty close.

Regardless, I am curious to see if there are any other similar examples of known polynomials that generate primes for integers within a given interval. Are there any other examples of polynomials like Euler’s that generate a large number of primes?

Finally, if more of these kinds of polynomials do exist, how would one go about looking for them?

Mailbox
  • 896
  • 2
    This is too vague. You can fit a polynomial through any set of values (with distinct $x$ coordinates). In particular, you can have $f(0)=2,f(1)=3,f(2)=5, \cdots$ for as many prime values as you like (though of course the degree will be large). – lulu Dec 04 '22 at 01:17
  • 2
    $f(40)=40^2+40+41=40(40+1)+41=(40)(41)+41=(40+1)(41) $ is not prime. – Gerry Myerson Dec 04 '22 at 01:28
  • this question may be relevant. – lulu Dec 04 '22 at 01:28
  • This is a duplicate. In fact the proof that a nonconstant polynomial $f(n)$ with ineteger coefficients cannot be prime for every positive integer $n$ , is quite easy , and Euler surely knew that. Moreover, it has particular reasons that the mentioned polynomial produces so many primes. It surely can be beaten, but the resulting polynomials will be cumbersome (large degree and coefficients). – Peter Dec 04 '22 at 11:10
  • Not sure what you mean with "Euler came close". It is impressing that the polynomial produces primes for every nonnegative integer $n\le 39$ , but "close to the desired infinite chain" is quite far-fetched. As lulu pointed out , this record can be beaten as far as we want, but what makes this expression remarkable is that it is very simple. – Peter Dec 04 '22 at 11:17
  • The "magic" polynomial generating immediately infinite many prime numbers (if it would exist) would end the hunt for ever larger primes , so the impossibility to build up such a polynomial has also an advantage. – Peter Dec 04 '22 at 11:22
  • 1
    Do you want $f$ to have all-integer coefficients, or would rational coefficients be acceptable? – Dan Dec 05 '22 at 20:27
  • The identity function $f(n) = n$ generates every possible prime number. Of course, it generates every possible composite number too. – Dan Dec 05 '22 at 20:49
  • @Dan Both work! – Mailbox Dec 06 '22 at 01:07

1 Answers1

1

https://mathworld.wolfram.com/Prime-GeneratingPolynomial.html is a resource you might try looking at. A few take aways :

  • Constant term must be prime.
  • Constant term will be a fail index so it must be large.
  • almost all primes are odd, odd numbers have representation in odd bases with an odd number of odd digits.
  • etc.
Roddy MacPhee
  • 859