Official 'exchange of inanities' thread [Was: mm127 is prime, cuz I say so]

[R. Gerbicz]

See: http://mathworld.wolfram.com/LuckyNumberofEuler.html

[Xyzzy]

Vaguely related?



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

[alpertron]

You can read more about that on http://mathworld.wolfram.com/Prime-G...olynomial.html . 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.

[alpertron]

You can see on http://www.alpertron.com.ar/ULAM.HTM, 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.

[R.D. Silverman]

Originally Posted by R. Gerbicz

Good question, it was an olympiad problem in 1987, see: http://www.artofproblemsolving.com/w...lems/Problem_6
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.

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.

[chalsall]

Originally Posted by R.D. Silverman

There are only finitely many such.

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

[R.D. Silverman]

Originally Posted by chalsall

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

negative, misplaced modifier

[chalsall]

Originally Posted by R.D. Silverman

negative, misplaced modifier

Please further define.

[chalsall]

Originally Posted by R.D. Silverman

negative, misplaced modifier

Still awaiting....

[chalsall]

Originally Posted by R.D. Silverman

negative, misplaced modifier

Mr. Silverman.

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

[LaurV]

Originally Posted by chalsall

Mr. Silverman. <snip>

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.