Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!ames!ucbcad!ucbvax!hplabs!sdcrdcf!ism780c!tim
From: tim@ism780c.UUCP (Tim Smith)
Newsgroups: sci.crypt
Subject: Re: Spacing of Prime Numbers
Message-ID: <6212@ism780c.UUCP>
Date: Fri, 8-May-87 17:02:11 EDT
Article-I.D.: ism780c.6212
Posted: Fri May  8 17:02:11 1987
Date-Received: Sun, 10-May-87 01:15:15 EDT
References: <1392@phred.UUCP>
Reply-To: tim@ism780c.UUCP (Tim Smith)
Organization: Interactive Systems Corp., Santa Monica CA
Lines: 30

>           The May issue of DISCOVER  magazine  presented a cute problem as
>  part of its brain teaser section  on  the  last page of the magazine. The
>  question was (I'm paraphrasing it):
>   
>           Prove there is a  sequence  of at least one million
>           consecutive integers, none of whom are prime.

If that were not true, than the prime number theorem would be false.
Roughly, the prime number theorem says that there are about N/ln(N)
primes less than N ( or that the Nth prime is about N*ln(N), or that
primes near N are about ln(N) apart ).

So when you consider numbers around exp(10**6), primes will be spaced
about a million apart.

Since exp(N) < N!, it is very likely that there are a million consecutive
composites well before 1000003!/2.

By the way, you can show with high school level math that there exits
positive constants A and B such that

	AN/ln(N) < pi(N) < BN/ln(N)

where pi(N) is the number of primes less than N.  This is enough to
solve the above problem.  For an elementary proof of this, see Yaglom
and Yaglom, "Challenging Mathematical Problems with Elementary Solutions,
Volume 2".
-- 
Tim Smith		"Learn to juggle while it's still legal"
sdcrdcf!ism780c!tim