wu :: forums
wu :: forums - Proving Primality like Euler

Welcome, Guest. Please Login or Register.
Jul 6th, 2022, 3:50pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: towr, william wu, Grimbal, SMQ, Icarus, Eigenray)
   Proving Primality like Euler
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Proving Primality like Euler  (Read 1181 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Proving Primality like Euler  
« on: Sep 26th, 2008, 3:54am »
Quote Quote Modify 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: male
Posts: 2084
Re: Proving Primality like Euler  
« Reply #1 on: Sep 26th, 2008, 5:20am »
Quote Quote Modify Modify

I suspect the fact that it's Mersenne (2147483647 = 2^31 - 1) is relevent. Wink
 
--SMQ
IP Logged

--SMQ

Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Proving Primality like Euler  
« Reply #2 on: Sep 26th, 2008, 7:33am »
Quote Quote Modify 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.  Wink
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Proving Primality like Euler  
« Reply #3 on: Sep 26th, 2008, 9:22am »
Quote Quote Modify 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: male
Posts: 2276
Re: Proving Primality like Euler  
« Reply #4 on: Sep 26th, 2008, 11:36pm »
Quote Quote Modify 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: male
Posts: 1948
Re: Proving Primality like Euler  
« Reply #5 on: Sep 27th, 2008, 1:35am »
Quote Quote Modify Modify

Well, I won't spoil anybody's fun, but this problem (unanswered) is related.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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