Consecutive Composite NumbersDate: 07/05/2002 at 18:26:32 From: Cynthia Watanabe Subject: Composite and Prime Numbers The following puzzle is from "Litton's Problematical Recreations," published in 1971: Find 1000 consecutive nonprime numbers. It would take too long to write out the primes looking for a "gap" of 1000. The answer begins: 1001! + 2, 1001! + 3, ..., 1001! + 1000. n! + A is divisible by A as long as A>1 and A<(n+1). I couldn't test this, because 1001! is too large for my graphing calculator. I tried 11! + 2, 11! + 3, ... but it failed at 11! + 5, since this sum is not divisible by 5; but then, I think I'm into an altogether different problem here. I was thinking that perhaps there would be a "gap" of 10 between two prime numbers. That is, 11! would precede a gap of 10. My next attempt to find an answer involved looking for information on primes on the Internet. One site, http://www.trnicely.net/ had information on "first occurences of gaps" between prime numbers. I found a gap of 1000 discovered by Bertil Nyman to be located "following the prime 22,439,962,446,379,651." Is this related to the above answer given by the book? Where do I look for an explanation of the book's answer as well as how to find "gaps" such as those provided by Mr. Nicely's website? I'd like to give this puzzle to my students next year. I'd also like to be able to explain how the answer is derived. Thanks. Date: 07/06/2002 at 13:15:40 From: Doctor Paul Subject: Re: Composite and Prime Numbers Finding the first occurence of n consecutive composite integers is obtained by trial and error. Mr. Nicely's website undoubtedly uses computers and brute force to search for gaps between prime numbers. The answer the book gave is the classic answer to this problem. For any positive integer n, we can always find n consecutive composite integers in the method the book suggested. I think you'll be better off if you put your calculator down and just try thinking about what the book is doing. The book claims that every one of the numbers 1001! + 2, 1001! +3, ... , 1001! + 1000 is composite. There are only 999 numbers in this sequence. We actually need to consider the following 1000 numbers: 1001! + 2, 1001! +3, ... , 1001! + 1000, 1001! + 1001 If the book claims that the numbers are composite, then either there exists some nontrivial factorization of every number on the list, or the book is wrong. And I'll tell you that the book isn't wrong. Each of the numbers on the list can be factored as follows: Consider 1001! + k, where 2 <= k <= 1001. Then k can be factored out of both terms in the sum as follows: 1001! + k = k * ([1*2*3*...*(k-1)*(k+1)*...*999*1000*1001] + 1) Thus 1001! + k is composite for 2 <= k <= 1001. One final thing to notice about this problem is that the "classic answer" tells us that there always exists a sequence of n consecutive composite integers for any n. But it doesn't guarantee that the sequence it generates will be the first time that n such composite integers occur. The factorial terms grow so large so quickly that it would seem reasonable to think that the first occurrence of n consecutive composite integers will not use the factorial method described above. There's more about prime gaps here: http://mathworld.wolfram.com/PrimeGaps.html I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 07/10/2002 at 12:20:19 From: Cynthia Watanabe Subject: Thank you (Composite and Prime Numbers) Dear Doctor Paul, Thanks for your explanation. That and a little time for contemplation helped. Thank goodness for the distributive property! I will definitely share this puzzle, your explanation, and this website with my students next year. Cynthia P.W. Watanabe. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/