See: [url]http://mathworld.wolfram.com/LuckyNumberofEuler.html[/url]

Vaguely related?

[YOUTUBE]3K-12i0jclM[/YOUTUBE]

(Even if it isn't related, it sure is presented in an entertaining way.)

You can read more about that on [url]http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html[/url] . But understanding it requires knowledge about Number Theory.

It is interesting to notice that this polynomial generates a lot more primes than random polynomials. This is because the values given by the Euler polynomial are never divisible by 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 or 37.

In the case p=2 this is easy to see because f(x) = x^2+x+41 is always odd, so f(x) is never multiple of 2.

For the other cases you can use the quadratic formula: x = (-1+/- sqrt(1-4*41)) / 2 (mod p)

The argument of the square root is the discriminant: 1-4*41 = -163 (RDS mentioned this a few posts back).

This discriminant must be a square mod p, otherwise we cannot extract the square root mod p and f(x) will not be multiple of p. By using the Jacobi symbol we can check this quickly and find that -163 is not a quadratic residue mod 3, 5, 7, 11, 13, 17, 19, 23, 29 or 37.

Since most composite numbers are divisible by small primes and f(x) is never divisible by the numbers shown above, we can conclude that the density of primes is greater for this polynomial. This can be checked experimentally.

In general, for most irreducible quadratic polynomial f(x) it can be shown that about half of the primes up to some bound cannot be divisors of f(x), so the density of primes is much greater than for linear polynomials. This is the explanation for the Ulam spiral. Euler polynomial is better yet in terms of density of primes, because of the set of primes not dividing the polynomial shown above.

You can see on [url]http://www.alpertron.com.ar/ULAM.HTM[/url], the Ulam spiral with the polynomials that generate the diagonals and the prime numbers less than 100 that cannot divide these polynomials. You will notice that when these prime numbers are small, the diagonals have greater density of prime numbers (there are more green dots) on the spiral.

[QUOTE=R. Gerbicz;412652]Good question, it was an olympiad problem in 1987, see: [url]http://www.artofproblemsolving.com/wiki/index.php/1987_IMO_Problems/Problem_6[/url]
So if we know that the above f(x)=x^2+x+41 is prime for f(0),f(1),f(2),f(3) then we know that it is also prime for f(4),..,f(39).
As I can remember there is a proof that there is only a finitely many such n value for that we can apply the statement, and we know all of them.[/QUOTE]

Let the discriminant of such a polynomial be -D. To have a long sequence of consecutive primes
Q(sqrt(-D)) must have class number 1 (i.e. the imaginary quadratic field must be a UFD). There
are only finitely many such.

[QUOTE=R.D. Silverman;412689]There are only finitely many such.[/QUOTE]

Would that not be better written as "There are only so many finitely defined"?

[QUOTE=chalsall;412691]Would that not be better written as "There are only so many finitely defined"?[/QUOTE]

negative, misplaced modifier

[QUOTE=R.D. Silverman;412707]negative, misplaced modifier[/QUOTE]

Please further define.

[QUOTE=R.D. Silverman;412707]negative, misplaced modifier[/QUOTE]

Still awaiting....

[QUOTE=R.D. Silverman;412707]negative, misplaced modifier[/QUOTE]

Mr. Silverman.

As you seem to take great joy in challenging others, might you please answer questions presented to you?

[QUOTE=chalsall;412722]Mr. Silverman. <snip>[/QUOTE]
Chris, that is your fault, you don't know how to make Mr. Silverman reply to your posts. You should say (in reply to the post with discriminant):
"Mr. Silverman, I bet you didn't know that, you just read it in the R. Gerbicz's link in post #34"
I bet he would reply to that immediately. :razz: