# GCD of adjacent pairs take on all possible values

Given a fixed positive integer $n$. Consider the numbers $1,2,\ldots,2n$. The GCD of any pair is one of $1,2,\ldots,n$. Suppose that all $2n$ numbers are placed around a circle. Is it possible that all $n$ possible GCDs are achieved by some pair of adjacent numbers in the circle?

For example:

$n=1$: $1$ $2$

$n=2$: $1$ $3$ $2$ $4$

$n=3$: $1$ $5$ $2$ $4$ $3$ $6$

$n=4$: $1$ $7$ $2$ $5$ $3$ $6$ $4$ $8$

In particular, note that $n$ and $2n$ always need to be adjacent, since they form the only possible pair with GCD $n$.

[Source: Russian competition problem]

Hint: $\gcd (k, 2k) = k$.
So, you just need to ensure that for all integers $i \leq n$, $i$ is next to $2i$.
Arrange them as $1, 2, 4, 8, \ldots, 3, 6, 12, \ldots, 5, 10, 20, \ldots, 7, 14, 28, \ldots, 9, 18, 36, \ldots$
• But in that arrangement, $6$ is not next to $12$, and $10$ is not next to $20$. – simmons Oct 29 '14 at 4:01