All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Factor numbers (Posted on 2011-03-26)
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?

 See The Solution Submitted by Math Man Rating: 4.8000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution | Comment 2 of 5 |

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 factors2179    21792180    2  2  5  1092181    3  7272182    2  10912183    37  59              The 37 would disqualify the set.2184    2  2  2  3  7  13   Start of first valid set.2185    5  19  232186    2  10932187    3  3  3  3  3  3  32188    2  2  5472189    11  1992190    2  3  5  732191    7  3132192    2  2  2  2  1372193    3  17  432194    2  10972195    5  4392196    2  2  3  3  612197    13  13  132198    2  7  1572199    3  7332200    2  2  2  5  5  11   End of first valid set.2201    31  71              The 31 would disqualify the set.2202    2  3  3672203    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

 Search: Search body:
Forums (0)