Cast for two

Wednesday, January 15, 2014

Euler : great talk by William Dunham

Having a Google Chrome Cast at home increased my longform consumption on Youtube dramatically. For instance, I discovered this talk about the great mathematician Euler by William Dunham:

I learned from it that there's a simple polynomial discovered by Euler that generates 40 consecutive primes: $ \forall n \in [0,40] : x^2+ x+ 41$ is a prime number.
You can check it by running following Python code:
You may wonder if there are other polynomials that generate primes. The article "Prime Generating Polynomials" claims that the polynomial $(x^5 - 133x^4 + 6729x^3 - 158379x^2 + 1720294x - 6823316)/4$ generates 57 consecutive primes for $x \in [0,56]$. Also the Wolfram article " Prime-Generating Polynomial indicates that polynomial as a winner. There are of course formula's to generate prime numbers but i think the Euler polynomial is the fastest.
The solution to Euler problem 27 is also interesting. A second degree polynomial generates 71 primes (but they are not consecutive). The polynomial $x^2 - 61x + 971$ generates 71 primes for $ x \in [0,70]$. This is the longest solution when the absolute values of the coefficients are restricted to thousand. If we drop that restriction, an even stronger polynomial is found : $x^2 -79 x + 1601$ generates 80 primes. Remark that the generated primes are not unique. For example the numbers 1601, 41, 197, 797, 1373, 1523 are generated twice. From the 80 primes generated, 40 are unique. I think Euler would not have been impressed.