# Finding Positive Integers for Coprime Arrangements in a Circular Sequence

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.

• The rules aren't clear. I thought only those pairs which surround a single number needed to be coprime. For the order $\{1,3,2,4\}$, the pairs which surround a single number are $(1,2),(3,4), (2,1), (4,3)$. and each of those pairs is coprime.
– lulu
Commented Jun 26 at 12:08

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.