🚀 go-pugleaf

> 
>  This may not be news to readers  of this group, but I thought the follow-
>  ing tidbit was interesting. 
>   
>           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 you like this sort of stuff see the book

        Number Theory in Science and Communication
         by M.R. Schroeder

>           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

In article <6212@ism780c.UUCP> tim@ism780c.UUCP (Tim Smith) writes:
]>           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.

This is killing a fly with a nuclear device.
1000001! + n is divisible by n for 2<=n<=1000001.
----
Greg

In article <1392@phred.UUCP>, johns@phred.UUCP (John Stice) writes:
> The May issue of DISCOVER magazine [asks]

> Prove there is a sequence of at least one million consecutive
> integers, none of whom are prime.

> [proof, involving 1000003 factorial]

> I had always guessed primes were more closely spaced than that.  (But
> then, number theory is not my forte.)

Note that the number in question (1000003!) has over five and a half
*million* digits (I obtained this by summing logarithms from 1 to
1000003; the result printed as 5.56573e+06).  I somehow don't think
that a run of a million composite numbers is too exceptional when
you're that far out.

					der Mouse

				(mouse@mcgill-vision.uucp)

|Note that the number in question (1000003!) has over five and a half
|*million* digits (I obtained this by summing logarithms from 1 to
|1000003; the result printed as 5.56573e+06).  I somehow don't think

Stirling's approximation would have given you the answer faster.

	Ken

In article <1938@husc6.UUCP>, greg@endor.harvard.edu (Greg) writes:
> >           Prove there is a  sequence  of at least one million
> >           consecutive integers, none of whom are prime.
>
> 1000001! + n is divisible by n for 2<=n<=1000001.

I'm confused.  How does this prove that there's a million consecutive
composite numbers?  All I see is that there's a composite number with
a million consecutive factors.

-- 
		-ed falk, sun microsystems, falk@sun.com
terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.