Are there infinitely many integer values $n$ such that $q(n)$ is a prime number? Numerical evidence points to a yes answer.

This is similar to Landau's 4th problem from 1912. (The conjecture that there are infinitely many primes $p$ of the form $p=n^2+1 $?) Of course, Landau did not have a computer. Given n a positive number, for what values of $n$ is $q(n)=n^2 + n + 41 $ a prime number? This is known as Prime-Generating Polynomial.

see link https://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

also Wikipedia


also my document on this quadratic polynomial


There are 3 .pdf files hosted at mersenne.org. I characterize all the cases when n^2 + n + 41 can be a composite number. Assuming positive integer n.

I show a data table, graph, and curve fit to characterize all the cases when this trinomial is a composite number, up to a certain numerical limit.

Also, I have found some algebraic factorizations for q(n)


A leading question is, "If we can know whenever n^2+n+41 is composite, what does that tell up about when that trinomial is a prime number?"

Let me know if there are any questions.


  • 14
    $\begingroup$ This is an open problem. $\endgroup$
    – Wojowu
    Jun 15 at 9:17
  • 4
    $\begingroup$ How can numerical evidence point to something in this case? $\endgroup$
    – markvs
    Jun 15 at 13:15
  • 9
    $\begingroup$ The Bunyakovsky conjecture en.wikipedia.org/wiki/Bunyakovsky_conjecture says that, if $f(n)$ is an irreducible polynomial with positive leading term and there is no modulus $M$ for which $f(n)$ is identically $0 \bmod M$, then $f(n)$ is prime infinitely often. The polynomial $n^2+n+41$ satisfies these criteria. But there is no polynomial of degree $\geq 2$ for which the Bunyakovsky conjecture has been proved. $\endgroup$ Jun 15 at 13:44
  • 4
    $\begingroup$ @MarkSapir One can make a conjectural asymptotic for the number of $n< X$ with $n^2+n+41$ prime, find numerical evidence that this asymptotic holds, and observe that this asymptotic predicts that there are infinitely many prime values. $\endgroup$
    – Will Sawin
    Jun 21 at 0:37
  • 3
    $\begingroup$ Furthermore the method I suggested in this case, of first make a prediction based on the best available heuristics, then use numerics to check how well the heuristics seem to hold in this case, would not run into trouble in the 4n+1 vs. 4n+3 case anyways. $\endgroup$
    – Will Sawin
    Jun 28 at 18:40

Since the ring of integers of $\mathbb{Q}[\sqrt{-163}]$ is a PID, it follows that a rational prime $p \neq 163$ may be expressed in the form $x^{2} + xy + 41y^{2}$ for rational integers $x$ and $y$ if and only if $p$ is a quadratic residue (mod $163$).(This is well-known). But, as you point out yourself, your question is comparable to asking how many primes $p$ have the form $n^{2} +1$ for integer $n$, which is well known to be open and Wojowu confirms in comments that your question is open too.

Later edit: I find it mildly interesting that the prime $p$ is expressible in this way (ie $p = n^{2}+n+41$) if and only if $p$ is expressible as the sum of four integer squares in one of the following ways: If $n$ is odd, we find that $p = \left( \frac{n-9}{2} \right)^{2} + \left( \frac{n+1}{2} \right)^{2} +\left( \frac{n+1}{2} \right)^{2} + \left( \frac{n+9}{2} \right)^{2}$ and if $n$ is even we find that $p = \left( \frac{n-8}{2} \right)^{2} + \left( \frac{n}{2} \right)^{2} +\left( \frac{n}{2} \right)^{2} + \left( \frac{n+10}{2} \right)^{2}.$

Even later edit: For any prime $p \neq 41$ which is a quadratic residue (mod $163$), there is a unique integer $h$ with $1 \leq h \leq \frac{p-1}{2}$ such that $p$ divides $h^{2}+h+41$, and then $p$ is necessarily the largest prime divisor of $h^{2}+h+41.$ An inductive argument of a type which dates back to Euler and/or Fermat then shows that $p$ is necessarily of the form $x^{2}+xy+41y^{2}$ for integers $x$ and $y$, and allows you to explicitly determine $x$ and $y$, given such an expression for the other (smaller) prime divisors $q$ of $h^{2}+h+41$ (all of which are also necessarily quadratic residues (mod $163$)).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.