From: Bob Silverman Subject: Math anyone? Date: Tue, 28 Mar 2000 15:17:30 GMT Newsgroups: sci.math Summary: [missing] Once again, in the hope of stirring some serious discussion, allow me to present a problem: The Prime Number Theorem States that the number of primes less than N as N --> oo is asymptotically N/log N. Alternately, the probability that a random integer near N is prime is 1/log N. Mertens' Theorem states product over primes p less than M of (1-1/p) is asymptotically exp(-gamma)/log M. Now consider a random integer near K, for large K. The probability that this integer is prime is the probability that it is not divisible by 2,3,5, ..... sqrt(K). This, by Merten's theorem is exp(-gamma)/log (sqrt(K)) = 2 exp(-gamma)/log K. But by the prime number theorem the numerator of this expression should be 1, not 2 exp(-gamma) (approx 1.123) Explain the discrepancy! This discrepancy is (IMO) a wonderful way to introduce (1) Why there is no proof of PNT by sieve methods (2) A major obstacle to proof of Goldbach, the twin prime conjecture, Schinzel's conjecture, etc. -- Bob Silverman "You can lead a horse's ass to knowledge, but you can't make him think" Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: ca314159 Subject: Re: Prime Numbers Date: Tue, 03 Oct 2000 20:19:33 GMT Newsgroups: sci.math In article <8raa0k$d8c$1@mirv.comms.unsw.edu.au>, "Sébastien-Jérôme Hew" wrote: > A well-known one is the sieve of Eratosthenes. > > Sébastien Hew. > > Pablo Arvizu wrote in message > news:39D8A4D4.F4F6F395@usa.alcatel.com... > > Do you know of an algorithm to check if a number is prime? > > > > Thanks for your help > > > > Pablo > > > Geometric sieve: http://www.informatik.uni-stuttgart.de/ifi/ti/personen/Matiyasevich/Jour nal/Sieve/Sieve.html The idea is new to me, but it shows how primes can be located geometrically by chords of a parabola. I'd like to hear more about this one if anyone has run into it before. Sent via Deja.com http://www.deja.com/ Before you buy.