What is the first set of consecutive positive integers such that every number has a common factor greater than 1 with at least one other number in the set?

The first thought is that the set must lie wholly between two successive primes, as any prime within the set would require at least twice itself also to be in the set, and by the time it got to that, there'd be more primes, requiring ever larger expansion of the set.

Initially the program below considered only those sets that extended starting at one unit higher than a prime and ended one unit lower than the next prime, resulting in the set of consecutive numbers between 27828 and 27846.  Then I realized that there might be some sets between smaller primes that can be made to fit the criterion by excluding some numbers at one end or the other that require otherwise unneeded (and absent) factors from the rest of the group.  So I added the checking of all subranges within each range between successive primes.  This indeed resulted in a lower sequence, which is therefore the solution: the numbers between 2184 and 2200 inclusive.

The check for validity of a set is to check the smallest prime divisor of each number in the set and verify that if that divisor is subtracted from the number, or alternatively, added, that the difference or sum is still within the range of the set, and so there's a common factor.

number  prime factors
2179    2179
2180    2  2  5  109
2181    3  727
2182    2  1091
2183    37  59              The 37 would disqualify the set.
2184    2  2  2  3  7  13   Start of first valid set.
2185    5  19  23
2186    2  1093
2187    3  3  3  3  3  3  3
2188    2  2  547
2189    11  199
2190    2  3  5  73
2191    7  313
2192    2  2  2  2  137
2193    3  17  43
2194    2  1097
2195    5  439
2196    2  2  3  3  61
2197    13  13  13
2198    2  7  157
2199    3  733
2200    2  2  2  5  5  11   End of first valid set.
2201    31  71              The 31 would disqualify the set.
2202    2  3  367
2203    2203

    5   P1=2
   10   while P1<99999999
   15    Prev=P1
   20    P1=nxtprm(P1)
   38    for St=Prev+1 to P1-2:for Nd=St+2 to P1-1
   39     Good=1
   40     for N=St to Nd
   42       Pd=prmdiv(N)
   52       if N-Pd<St and N+Pd>Nd then Good=0
   60     next
   70     if Good=1 then print St,Nd:Ct=Ct+1:if Ct @ 42=0 then print:stop
   75    next:next
   80   wend

Here are the beginnings and endings of the first few valid sets:

   2184            2200
  27828           27846
  27829           27846
  27830           27846
  32214           32230
  57860           57876
  62244           62260
  87890           87906
  87890           87907
  87890           87908
  87890           87909
  87890           87910
  92274           92290
 110990          111010
 117920          117936
 122304          122320
 127374          127398
 147950          147966
 151058          151090
 151059          151090
 151060          151090
 151061          151090
 151062          151088
 151062          151089
 151062          151090
 152334          152350
 163488          163506
 171054          171072
 171054          171073
 171054          171074
 171054          171075
 171054          171076
 177980          177996
 182364          182380
 185924          185946
 185925          185946
 185926          185946
 208010          208026
 212394          212410
 238040          238056
 242424          242440
 249678          249696

Posted by Charlie on 2011-03-26 14:29:58