20151014, 14:28  #34 
"Robert Gerbicz"
Oct 2005
Hungary
1,531 Posts 

20151014, 14:40  #35 
Aug 2002
2^{3}×1,051 Posts 
Vaguely related?
(Even if it isn't related, it sure is presented in an entertaining way.) 
20151014, 14:49  #36 
Aug 2002
Buenos Aires, Argentina
2×3^{2}×79 Posts 
You can read more about that on http://mathworld.wolfram.com/PrimeG...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(14*41)) / 2 (mod p) The argument of the square root is the discriminant: 14*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. 
20151014, 15:11  #37 
Aug 2002
Buenos Aires, Argentina
2·3^{2}·79 Posts 
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.
Last fiddled with by alpertron on 20151014 at 15:12 
20151014, 18:30  #38  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Q(sqrt(D)) must have class number 1 (i.e. the imaginary quadratic field must be a UFD). There are only finitely many such. 

20151014, 18:52  #39 
If I May
"Chris Halsall"
Sep 2002
Barbados
23×443 Posts 

20151014, 21:06  #40 
Nov 2003
2^{2}×5×373 Posts 
negative, misplaced modifier
Last fiddled with by R.D. Silverman on 20151014 at 21:06 
20151014, 21:35  #41 
If I May
"Chris Halsall"
Sep 2002
Barbados
10011111001101_{2} Posts 

20151014, 22:04  #42 
If I May
"Chris Halsall"
Sep 2002
Barbados
23×443 Posts 

20151014, 23:54  #43 
If I May
"Chris Halsall"
Sep 2002
Barbados
23715_{8} Posts 

20151015, 01:40  #44 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10011010001101_{2} Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Official AVX512 programming thread  ewmayer  Programming  31  20161014 05:49 
Official Peeved Pets Thread  Prime95  Lounge  32  20151002 04:17 
Official 'Let's move the hyphen!' thread.  Flatlander  Lounge  29  20130112 19:29 
Is MM127 Prime? Just a Poll  jinydu  Miscellaneous Math  57  20081108 17:48 
Official Odd Perfect Number thread  ewmayer  Math  14  20081023 13:43 