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?

A great problem!
1. Start with a few asumptions e.g. the following:

The first number is divisible by 2.
There is a gap. Make the second number divisible by 3.
The third number is divisible by 2.
There is a gap. Make the fourth number divisible by 5.
The fifth number is divisible by 2 and 3.
There is a gap. Make the sixth number divisible by 7.
The seventh number is divisible by 2.
The eighth number is divisible by 3.
The ninth number is divisible by 2 and 5.
There is a gap. Make the tenth number divisible by 11.
The eleventh number is divisible by 2 and 3.
There is a gap. Make the twelfth number divisible by 13
And so on.

2. Now we can cut down the required length quite a bit by making the first number divisible by the largest number in the series of primes, but it should be obvious that the minimum length can't be less than 14 i.e. a prime gap of 14 is required to fit the series, because 13 is the first number that allows a consecutive set of numbers to be complete without gaps.

3. It might also be a good idea to put the second largest prime at or near the end to maximise the overlap.

4. Putting all this together, we takes the primes from 2 to 13, put 13 at one end and 11 at the other, and try to fill all the gaps:
{13,5,2,3,2,11,2,7,2,3,2,5,2,13,7,3,11}

5. This gives 2 simultaneous equations: 546n+1=5m and 546n+5=11p, because the sequence starts with 2*3*7*13. Then m = 6006k+437,   n = 55k+4,   p =2730k+199,   k element Z. This gives a solution at 32214, with n=59. But we know that 11 and 5 will coincide at each multiple of 55k, so that there is, amazingly, a smaller solution at k=0,n=4, corresponding to 2184.

6. So the first set of qualifying consecutive positive numbers starts with 2184 and ends with 2200. And, almost like magic, the numbers, with their factorizations, are:

1 2184 2^3×3×7×13
2 2185 5×19×23
3 2186 2×1093
4 2187 3^7
5 2188 2^2×547
6 2189 11*199
7 2190 2×3×5×73
8 2191 7*313
9 2192 2^4×137
10 2193 3*17*43
11 2194 2×1097
12 2195 5×439
13 2196 2^2×3^2×61
14 2197 13^3
15 2198 2×7×157
16 2199 3*733
17 2200 2^3×5^2×11

7. It also follows from the construction of the series that not only does each number share a factor with some other number in the series, but all of them share at least one factor with either 2184 or 2200. Incredible!

Edited on March 26, 2011, 1:36 pm

Posted by broll on 2011-03-26 13:28:37