Finding Positive Integers for Coprime Arrangements in a Circular Sequence

Question

Find all positive integers $n$ such that the numbers from 1 to $n$ can be arranged in a circle, each appearing exactly once, so that any two numbers between which there is exactly one other number are coprime.

$\textbf{My Attempt}$

I'm trying to solve this problem where I need to find all positive integers $n$ such that the numbers from 1 to $n$ can be arranged in a circle, each appearing exactly once, so that any two numbers with exactly one number between them are coprime. Here’s my attempt so far:

I started by considering small values of $n$ to look for a pattern or insight.

For $n = 1$, it's trivial since there's only one number, and it satisfies the condition by default.

For $n = 2$ , I have the numbers 1 and 2. Arranging them in a circle $(1, 2)$, they are coprime. This seems to work fine.

For $n = 3$ , I considered the arrangement $(1, 2, 3)$. The pairs to check are $(1, 3)$ since there is exactly one number $2$ between them. $gcd(1, 3) = 1$, so this arrangement works.

When I tried $n = 4$, I considered the arrangement $(1, 2, 3, 4)$. The pairs to check are $(1, 3)$ and $(2, 4)$. Both pairs are coprime: $gcd(1, 3) = 1$ and $gcd(2, 4) = 2$. However, since $2$ and $4$ are not coprime, this arrangement doesn't work.

I also tried a different arrangement $(1, 3, 2, 4)$, but still, the pair $(2, 4)$ fails the coprimality condition. It seems like $n = 4$ might not have a valid arrangement.

For $n = 5$ , I arranged the numbers as $(1, 2, 3, 4, 5)$. The pairs to check are $(1, 3)$, $(2, 4)$, and $(3, 5)$. Here, $gcd(1, 3) = 1$, $gcd(2, 4) = 2$, and $gcd(3, 5) = 1$. Since $\gcd(2,4) \neq 1$ this arrangement fails

I’m starting to think there might be a specific pattern or additional constraint that I'm missing. Maybe $n$ needs to be prime or have some other special property. I would like to hear others' thoughts or if anyone has found a general solution or further insight into this problem.

Answer 1

For odd $n$, if we take the sequence of all positions in the circle which have exactly one number between them, they form to be a complete cycle of their own. So, we can just fill out this cycle with $1, 2,\dots n$ as $\gcd(k, k+1) =1$ and $\gcd(n, 1) = 1$

For example if $n=7$

• $[\_, \_, \_, \_, \_, \_, \_]$
• $[\color{red} 1, \_, \_, \_, \_, \_, \_]$
• $[\color{green} 1, \_, \color{red} 2, \_, \_, \_, \_]$
• $[1, \_, \color{green} 2, \_, \color{red} 3, \_, \_]$
• $[1, \_, 2, \_, \color{green} 3, \_, \color{red} 4]$
• $[1, \color{red} 5, 2, \_, 3, \_, \color{green} 4]$
• $[1, \color{green} 5, 2, \color{red} 6, 3, \_, 4]$
• $[1, 5, 2, \color{green} 6, 3, \color{red} 7, 4]$
• $[\color{red} 1, 5, 2, 6, 3, \color{green} 7, 4]$

For even $n$, the same sequence as above forms two independent cycles of equal size.

If $\frac{n}{2}$ is even (or $n$ is divisible by $4$), we can fill the first cycle with $1, 2, \dots \frac{n}{2}$ and the second cycle with $\frac{n}{2} + 1, \frac{n}{2} + 2, \dots n$. We can do this because $\gcd(n, \frac{n}{2} + 1) = \gcd(\frac{n}{2} + 1, \frac{n}{2} - 1) = \gcd(\frac{n}{2} - 1, 2) = 1$

For example if $n=8$

• $[\_, \_, \_, \_, \_, \_, \_, \_]$
• $[\color{red} 1, \_, \_, \_, \_, \_, \_, \_]$
• $[\color{green} 1, \_, \color{red} 2, \_, \_, \_, \_, \_]$
• $[1, \_, \color{green} 2, \_, \color{red} 3, \_, \_, \_]$
• $[1, \_, 2, \_, \color{green} 3, \_, \color{red} 4, \_]$
• $[\color{red}1, \_, 2, \_, 3, \_, \color{green} 4, \_]$
• $[1, \color{red} 5, 2, \_, 3, \_, 4, \_]$
• $[1, \color{green} 5, 2, \color{red} 6, 3, \_, 4, \_]$
• $[1, 5, 2, \color{green} 6, 3, \color{red} 7, 4, \_]$
• $[1, 5, 2, 6, 3, \color{green} 7, 4, \color{red} 8]$
• $[1, \color{red} 5, 2, 6, 3, 7, 4, \color{green} 8]$

Now finally for $n$ even and $\frac{n}{2}$ odd ($n\bmod 4 = 2$), we show that we can't form such a circle.

We know that there are exactly $\frac{n}{2}$ even numbers in $\{1, 2, \dots n\}$ for even $n$. That means there are an odd number of even numbers in $\{1, 2, \dots n\}$, which are to be distributed between the two cycles. By the pigeonhole principle, one of the cycles will have atleast $\left\lfloor \frac{n/2}{2} \right\rfloor + 1$ even numbers. As the cycle is of size $\frac{n}{2}$, again by the pegionhole principle, atleast two even numbers will be adjacent in this cycle. As these are not coprime, we cannot have an arrangement according to the original problem.