wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Proving Primality like Euler
        
(Message started by: Barukh on Sep 26^th, 2008, 3:54am)

Title: Proving Primality like Euler
Post by Barukh on Sep 26^th, 2008, 3:54am

In year 1772, Euler proved that the number N = 2147483647 is prime. He used trial division method.

According to Prime Number Theorem (http://en.wikipedia.org/wiki/Prime_number_theorem#Statement_of_the_theorem), there are more than 4000 prime numbers less than http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifN.

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?

Title: Re: Proving Primality like Euler
Post by SMQ on Sep 26^th, 2008, 5:20am

[hide]I suspect the fact that it's Mersenne (2147483647 = 2^31 - 1) is relevent.[/hide] ;)

--SMQ

Title: Re: Proving Primality like Euler
Post by Barukh on Sep 26^th, 2008, 7:33am

on 09/26/08 at 05:20:56, SMQ wrote:

[hide]I suspect the fact that it's Mersenne (2147483647 = 2^31 - 1) is relevent.[/hide]

Right. Actually, I thought to ,make this observation my first hint. ;)

Title: Re: Proving Primality like Euler
Post by Eigenray on Sep 26^th, 2008, 9:22am

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.

Title: Re: Proving Primality like Euler
Post by Barukh on Sep 26^th, 2008, 11:36pm

on 09/26/08 at 09:22:53, 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.

Title: Re: Proving Primality like Euler
Post by Eigenray on Sep 27^th, 2008, 1:35am

Well, I won't spoil anybody's fun, but [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1205617005]this problem[/link] (unanswered) is related.