Consecutive Composite Numbers

Date: 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.