A Gathering of Number-Theorists

A certain number of the 5000 members of the World Arithmetical Society (each of which has a different membership number between 1 and 5000) got together to discuss a problem. Much to their surprise, when they were lining up for lunch they discovered that their membership numbers could be arranged to form a sequence of consecutive whole numbers and, moreover, that none of them was standing next to someone whose number was relatively prime to his own. (Remember that two numbers, such as 25 and 34, are relatively prime if they have no common divisor greater than 1.)

How many were the members of the Society who met and what were their membership numbers?

Answer

Here is a solution. I'm afraid I used a computer to help find it. Some explanation is below.

2197 13 2184 2 3 7 13 2191 7 2198 2 7 2194 2 2186 2 2188 2 2192 2 2196 2 3 2187 3 2193 3 2199 3 2190 2 3 5 2185 5 2195 5 2200 2 5 11 2189 11

This uses

17 numbers, from 2184 to 2200. Each row shows which "small" prime numbers divide the number on that row, and you can see that each pair of consecutive rows has a prime number in common.

To find this without requiring too much human brute force or computer cleverness, I

defined a set of numbers to be "plausible" if each shares a common factor with at least one other, and no more than two share a common factor with only one other,

a condition it's easy to check by computer, and then

conducted an exhaustive search for the shortest plausible string of consecutive numbers below 5000.

This might have yielded a non-solution, in which case I'd have continued the search. That would have happened if, e.g.,

you could arrange the numbers into a "chain" and some "rings", but there was no way to connect these together into a single "chain".

Is this solution unique?

This set of numbers is unique. (An earlier version of this answer had a sketch of how to prove it, with a remark to the effect that the details are fiddly enough to put me off doing it properly. Peter Taylor, in comments below, correctly observes that the details are much less fiddly than I'd thought.) Suppose you have a "working" set of numbers, and it includes a prime number $p$. This must be adjacent to at least one other number, which must therefore be a multiple of $p$. Therefore your range must extend at least as far as $2p$. But in the range $(p,2p)$ there is at least one prime number, by Bertrand's postulate. So if you have a prime number then you have a larger prime number; hence, any solution must include no prime numbers. The longest gap between prime numbers below 5000 has length 33; so brute force up to size 33 suffices. I've run my program further than that and found no viable sets of numbers other than the one above.

But

the exact sequence is not unique; e.g., we could swap 2187 and 2193.