mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2015-10-14, 14:28   #34
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

156210 Posts
Default

See: http://mathworld.wolfram.com/LuckyNumberofEuler.html
R. Gerbicz is offline   Reply With Quote
Old 2015-10-14, 14:40   #35
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

845110 Posts
Default

Vaguely related?



(Even if it isn't related, it sure is presented in an entertaining way.)
Xyzzy is offline   Reply With Quote
Old 2015-10-14, 14:49   #36
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

144610 Posts
Default

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 is offline   Reply With Quote
Old 2015-10-14, 15:11   #37
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×3×241 Posts
Default

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 2015-10-14 at 15:12
alpertron is offline   Reply With Quote
Old 2015-10-14, 18:30   #38
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-10-14, 18:52   #39
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22×7×373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
There are only finitely many such.
Would that not be better written as "There are only so many finitely defined"?
chalsall is offline   Reply With Quote
Old 2015-10-14, 21:06   #40
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by chalsall View Post
Would that not be better written as "There are only so many finitely defined"?
negative, misplaced modifier

Last fiddled with by R.D. Silverman on 2015-10-14 at 21:06
R.D. Silverman is offline   Reply With Quote
Old 2015-10-14, 21:35   #41
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22·7·373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
negative, misplaced modifier
Please further define.
chalsall is offline   Reply With Quote
Old 2015-10-14, 22:04   #42
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22·7·373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
negative, misplaced modifier
Still awaiting....
chalsall is offline   Reply With Quote
Old 2015-10-14, 23:54   #43
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22×7×373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
negative, misplaced modifier
Mr. Silverman.

As you seem to take great joy in challenging others, might you please answer questions presented to you?
chalsall is offline   Reply With Quote
Old 2015-10-15, 01:40   #44
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

7·1,423 Posts
Default

Quote:
Originally Posted by chalsall View Post
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.
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Official AVX-512 programming thread ewmayer Programming 31 2016-10-14 05:49
Official Peeved Pets Thread Prime95 Lounge 32 2015-10-02 04:17
Official 'Let's move the hyphen!' thread. Flatlander Lounge 29 2013-01-12 19:29
Is MM127 Prime? Just a Poll jinydu Miscellaneous Math 57 2008-11-08 17:48
Official Odd Perfect Number thread ewmayer Math 14 2008-10-23 13:43

All times are UTC. The time now is 10:34.


Wed May 18 10:34:24 UTC 2022 up 34 days, 8:35, 0 users, load averages: 1.54, 1.28, 1.26

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔