wu :: forums « wu :: forums - Proving Primality like Euler » Welcome, Guest. Please Login or Register. Sep 23rd, 2023, 9:32pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: towr, SMQ, Grimbal, Eigenray, Icarus, william wu)    Proving Primality like Euler « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Proving Primality like Euler  (Read 1198 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 »