Author 
Topic: Proving Primality like Euler (Read 1202 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


Proving Primality like Euler
« on: Sep 26^{th}, 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 26^{th}, 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 26^{th}, 2008, 7:33am » 
Quote Modify

on Sep 26^{th}, 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 26^{th}, 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 26^{th}, 2008, 9:51am by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Proving Primality like Euler
« Reply #4 on: Sep 26^{th}, 2008, 11:36pm » 
Quote Modify

on Sep 26^{th}, 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 27^{th}, 2008, 1:35am » 
Quote Modify

Well, I won't spoil anybody's fun, but this problem (unanswered) is related.


IP Logged 



