johns@phred.UUCP (04/28/87)
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.
The answer is surprisingly easy:
----------------------(Spoiler Follows)----------------------------
Let M = (3 * 4 * 5 * ... * 1,000,003) = (1,000,003!) / 2
Then the consecutive sequence of one million integers consisting of:
M3 = (M + 3) (that's "M sub three", not "M times three")
M4 = (M + 4)
M5 = (M + 5)
... etc, etc up to M1000003 = (M + 1,000,003)
contains no primes because 3 is a factor of M3, 4 is a factor of M4, and
so on, and so on... until 1000003 is a factor of M1000003.
I had always guessed primes were more closely spaced than that.
(But then, number theory is not my forte.)
BTW, DISCOVER is a great magazine for explaining technical
subjects using language almost anyone can understand. It's usually good
reading for subjects outside one's specialty. (Such as number theory,
for me).
John Stice.............
usual disclaimers apply..... etc.hofbauer@utcsri.UUCP (05/01/87)
> > 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
tim@ism780c.UUCP (Tim Smith) (05/09/87)
> 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
greg@endor.harvard.edu (Greg) (05/09/87)
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.
----
Gregmouse@mcgill-vision.UUCP (der Mouse) (05/13/87)
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)
ken@rochester.ARPA (Ken Yap) (05/24/87)
|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
falk@sun.uucp (Ed Falk) (05/24/87)
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.
billc@prism.UUCP (06/01/87)
==/* Written 2:39 am May 24, 1987 by falk@sun.UUCP in prism:sci.crypt */
==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.
1000001! is indeed a number with a million consecutive factors.
So how does this help us, you ask? The point is that for any
number between one and one million, call it n, 1000001!
can be written as c*n, where c is 1000001!/n. Thus, 1000001! + n
can be written as (c+1) * n. That means that 1000001! + n is
not a prime. Now that's for any of a million consecutive n's!
Thus we've created a string of one million composites.
This method can be used to prove that for any number n,
a string of consecutive composites can be found. (This
is the principle of mathematical induction. See a good
reference like Calculus Vol. I by Tom Apostol.)
----
Bill Callahan billc@mirror.TMC.COM
{mit-eddie, ihnp4, wjh12, cca, cbosgd, seismo}!mirror!billc
Mirror Systems 2067 Massachusetts Avenue, Cambridge, MA 02140
Telephone: 617-661-0777franka@mmintl.UUCP (06/09/87)
In article <201000001@prism> billc@prism.UUCP writes: |That means that 1000001! + n is not a prime. Now that's for any of a |million consecutive n's! Thus we've created a string of one million |composites. (This is the principle of mathematical induction.) No, this is *not* the principle of mathematical induction. -- Frank Adams ihnp4!philabs!pwa-b!mmintl!franka Ashton-Tate 52 Oakland Ave North E. Hartford, CT 06108