Problem: a set of integers has a coprime cycle if it can be listed in a cyclic list of the form $(a_1, a_2, a_3, \ldots, a_n)$, where
- each element of the set appears exactly once and $\gcd(a_i, a_{i+1}) = 1$ for $i = 1, \ldots, n$ and
- $a_{n+1} = a_1$.
For example, $(7, 8, 9, 10, 11, 14, 13, 12)$ is a coprime cycle for $k = 7$, but $(7, 8, 9, 10, 11, 12, 13, 14) $ is not because $\gcd(14, 7) \ne 1$. What is the smallest positive integer $k$ such that the set $\{k, k + 1,\ldots, k + 7\}$ does not possess a coprime cycle?
The answer is 98, and I guessed and tried to solve it. Is there another way?
It is obvious that $k$ must be divisible by $7$, otherwise $$(k,k+1,k+2,k+3,k+4,k+5,k+6,k+7)$$ is a coprime cycle.
Now if $$\begin{cases}k\not \underset3 \equiv 0\\ k\not \underset5 \equiv 3\end{cases}\tag1$$
then the following coprime cycle can be made: $$(k,k+1,k+2,k+7,k+6,k+5,k+4,k+3).$$ It is indeed a coprime cycle since $\gcd(k,k+3)$ can only be $3$ but $3\not\mid k$. Also $\gcd(k+2,k+7)$ can only be $5$ but $5\not\mid k+2$. And the rest are consecutive numbers.
If $$\begin{cases}k\not \underset3 \equiv 2\\ k\not \underset5 \equiv 0\end{cases}\tag2$$
then the following coprime cycle can be made: $$(k,k+1,k+2,k+3,k+4,k+7,k+6,k+5).$$ It is indeed a coprime cycle since $\gcd(k+4,k+7)$ can only be $3$ but $3\not\mid k+4$. Also $\gcd(k,k+5)$ can only be $5$ but $5\not\mid k$. And the rest are consecutive numbers.
Notice that all the numbers that are divisible by $7$ and less than $98$ fall into at least one of the two above categories: $7,14,35,49,56,70,77,85,92$ meet the conditions of the system $(1)$. $21,28,42,63$ meet the conditions of the system $(2)$.
The number $98$, however, is different. We can prove that the set $\{98,99,100,101,102,103,104,105\}$ can’t be presented as a coprime cycle. (One can draw a graph, connecting numbers that can go next to each other, and see that there is no Hamiltonian cycle there.) Indeed, $102$ can be only with $101$ and $103$. So there is this segment of the cycle: $$(101,102,103).$$
$105$ can be only with $101$, $103$ and $104$. So it has to be next to $104$, otherwise we close the cycle too early. The second neighbour is either $101$ or $103$, and it doesn’t matter which one since those are two prime numbers. So we can say that the cycle must contain
$$(101,102,103,105,104).$$
The next neighbour of $104$ can be only $99$. $98$ and $100$ are left, they must go together, but they are both even. A cycle can’t be constructed. Hence the answer to the problem is $98$.
Note: there is another way to prove that $98,99,…$ don’t form a coprime cycle, using that even and odd numbers must alternate in a cycle.