Prime-generating functions

A few weeks ago I heard someone casually refer to ‘that formula of Euler’s that generates primes’. I hadn’t heard of this, but it turns out that in 1772 Euler produced this formula:

\[ f(x) = x^2 + x + 41\text{.} \]

Using this, \(f(0)=41\), which is prime. \(f(1)=43\), which is also prime. \(f(2)=47\) is another prime. In fact this sequence of primes continues for an incredible forty integer inputs until \(f(40)=41^2\). It might generate more primes for higher inputs, but what’s interesting here is the uninterrupted sequence of forty primes.

This got me wondering. Clearly \(f(0)\) is prime because 41 is prime, so that much will work for any function

\[ f(x) = x^2 + x + p \]

for prime \(p\), since \(f(0)=0^2+0+p=p\). Are there other values of \(p\) that generate a sequence of primes? Are there any values of \(p\) that generate longer sequences of primes?

I wrote some code to investigate this. Lately, I’ve taken to writing C++ when I need a bit of code, for practice, so I wrote this in C++.

I figured the cases where \(f(0)\) is prime but \(f(1)\) isn’t weren’t that interesting, since \(f(0)\) is trivially prime. In fact, \(f(x)=x g(x)+p=p\) when \(x=0\) for any prime \(p\), but saying so doesn’t seem worth the effort.

So I kept track of the primes \(p\) whose functions \(f(x)=x^2+x+p\) generate more than one prime, and the lengths of the sequences of primes generated by each of these. This produced a pair of integer sequences.

I put the primes that work into the OEIS and saw that I had generated a list of the smaller twin in each pair of twin primes. I was momentarily spooked by this, until I realised it was obvious. Since \(f(0)=p\) and \(f(1)=1^2+1+p=p+2\), any prime this works for will generate at least a twin prime pair \(p,p+2\).

What about the lengths of the sequences of consecutive primes generated? The table below shows the sequences of consecutive primes generated for small values of \(p\). Most primes that generate a sequence produce just two, and \(p=41\) definitely stands out by generating forty.

\(p\)\(f(x)\)Primes generatedNumber of consecutive primes generated3\(x^2+x+3\)3, 525\(x^2+x+5\)5, 7, 11, 17411\(x^2+x+11\)11, 13, 17, 23, 31, 41, 53, 67, 83, 1011017\(x^2+x+17\)17, 19, 23, 29, 37, 47, 59, 73, 89, 107, 127, 149, 173, 199, 227, 2571629\(x^2+x+29\)29, 312

I was pleased to see this sequence of lengths of primes generated was not in the OEIS. So I submitted it, and it is now, along with the code I wrote. (I discovered along the way that the version where sequences of length one are included was already in the database.)

Anyway, I amused myself by having some C++ code published, and by citing Euler in a mathematical work. Enjoy: A371896.