wu :: forums « wu :: forums - Proving Primality like Euler » Welcome, Guest. Please Login or Register. Apr 20th, 2024, 7:22am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    putnam exam (pure math) (Moderators: Eigenray, SMQ, towr, Icarus, william wu, Grimbal)    Proving Primality like Euler « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Proving Primality like Euler  (Read 1201 times) Barukh Uberpuzzler     Gender: Posts: 2276 Proving Primality like Euler   « on: Sep 26th, 2008, 3:54am » Quote Modify In year 1772, Euler proved that the number N = 2147483647 is prime. He used trial division method.   According to Prime Number Theorem,  there are more than 4000 prime numbers less than N.     However, Euler managed to do this by less than 400 divisions!   Can you reproduce the line of thought that allowed Euler to reduce so drastically the amount of necessary work?   IP Logged SMQ wu::riddles Moderator Uberpuzzler     Gender: Posts: 2084 Re: Proving Primality like Euler   « Reply #1 on: Sep 26th, 2008, 5:20am » Quote Modify I suspect the fact that it's Mersenne (2147483647 = 2^31 - 1) is relevent.   --SMQ IP Logged --SMQ Barukh Uberpuzzler     Gender: Posts: 2276 Re: Proving Primality like Euler   « Reply #2 on: Sep 26th, 2008, 7:33am » Quote Modify on Sep 26th, 2008, 5:20am, SMQ wrote: I suspect the fact that it's Mersenne (2147483647 = 2^31 - 1) is relevent. Right. Actually, I thought to ,make this observation my first hint.   IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: Proving Primality like Euler   « Reply #3 on: Sep 26th, 2008, 9:22am » Quote Modify Wouldn't Euler have checked only 157 84 primes?  But then there's a simple method that uses 373 trial divisions, without having to test the trial divisors for primality.  Making it only slightly more complicated, we can bring that down to 198. « Last Edit: Sep 26th, 2008, 9:51am by Eigenray » IP Logged Barukh Uberpuzzler     Gender: Posts: 2276 Re: Proving Primality like Euler   « Reply #4 on: Sep 26th, 2008, 11:36pm » Quote Modify on Sep 26th, 2008, 9:22am, Eigenray wrote: Wouldn't Euler have checked only 157 84 primes? I don't know...   Quote: But then there's a simple method that uses 373 trial divisions, without having to test the trial divisors for primality. That's what Euler did. I believe somebody will elaborate on this. IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: Proving Primality like Euler   « Reply #5 on: Sep 27th, 2008, 1:35am » Quote Modify Well, I won't spoil anybody's fun, but this problem (unanswered) is related. IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board