Arrange Relatively Prime Numbers in a Circle

The question:

In how many ways can you arrange the numbers $1$ to $8$ in a circle so that neighboring numbers are relatively prime? Can you generalize for $1$ to $n$?

It's fairly easy to list all possible arrangements for the numbers $1$ to $n$ when $n \leq 7$; however, beyond this it is hard to do it by hand.

I've tried approaching the problem in three ways, but none of them have got me any success (for either the general case or the special one).

Consider the graph with vertices numbered $1, 2, \dotsc, n$. In this graph, there is an edge between two distinct vertices iff their numbers are relatively prime. For example, $1$ will be connected to all other vertices, $2$ to all odd numbers, etc. Then, the number of Hamiltonian cycles in this graph is our answer.

Another way to look at the problem is by recursion. Given an arrangement of $n-1$ vertices, the $n^{\text{th}}$ vertex (with the number $n$) can be inserted on an edge where both neighbors are relatively prime to it. Thus the edge will be split into two. To solve the problem, we have to solve the recurrence. But note that the initial arrangement of $n-1$ vertices does not have to have all neighbors relatively prime; the condition is that either all neighbors are relatively prime, or there is exactly one relatively non-prime pair such that both numbers are relatively prime to the inserted number $n$.

A third way is by making 'trees' for the choices of each next vertex. We start at $1$: there are $n-1$ branches for each of the $n-1$ remaining numbers. For each of the branches, there are further branches for each of the remaining numbers relatively prime to that branch, and so on. Counting the number of ways to get to the bottom of this tree will give us an answer. Edit: As in @Mark Main's answer, this approach is equivalent to making 'option sets' for a given number: starting from 1, choose any number in its option set, then choose any number from that number's option set, and so on. This is a good way to deal with the problem programmatically, but I can see no other advantage for the solution.

Sorry for making it so long, but I thought it's better if I put up all my attempts. Please add more specific tags if you can, I couldn't find any.

Updated answer.

Below are all the possible combinations for relative prime numbers in a circle, for sets contain n integers 1 through 8.

I did not find an easy formula for your question, however, I was able to greatly simply how to figure the answers out:

The cell locations are in a circle, cell 1 at the top and moving clockwise, 2, 3, etc. until the final cell is placed to the immediate right of cell 1.

If "unique" includes the specific cell location (e.g. where the number 1 will reside in cell 1, and later cell 2, 3... etc.) then the number of possible answers within each set of 1 to 8 numbers are respectively: 1, 2, 6, 8, 60, 24, 504, and 576.

However, because the numbers are placed inside a circle, the number 1 can always be represented at the left most location as the starting position, because any other location is simply a duplication of the same numerical sequence starting in a different cell location. Therefore, this smaller subset of "unique" possible answers within each set of 1 to 8 numbers are respectively: 1, 1, 2, 2, 12, 4, 72, and 72.

The relationship between these two potential views of "unique" is therefore directly simple: $\frac{LargeSet}{n}=SmallSet$

$\frac{1}{1}=1, \frac{2}{2}=1, \frac{6}{3}=2, \frac{8}{4}=2, \frac{60}{5}=12, \frac{24}{6}=4, \frac{504}{7}=72, \frac{576}{8}=72$

I have not figured out a formula but did simplify the relationships above to a point where a formula (if possible may be derived, I just ran out of time).

I did notice an interesting relationship: 4 × (3-1) × (2-1) × 1 = 8, and 8 / 4 = 2, which are both the answers for the number of possible large and small sets for n=4. This same pattern works up to n=5. e.g. for n=5: 5 x (4-1) × (3-1) × 2 × 1 = 60, and 60 / 5 = 12. I subtracted 1 twice because 4 and 2 cannot be neighbors starting at n=4.

But with 6 we introduce new non-neighboring numbers: 2, 3 and 6 as a set. The number 2 shares both sets, so it's only able to reside next to 1, 5 and eventually 7.

And so 6 × (5-3) × (4-3) × (3-2) × 2 × 1 = 24 and 24 / 6 = 4, which is interesting, but I can't publish a rule that proves this works.

What I fear is that there will not be a "simple rule" because large n numbers will have more and more overlapping non-neighboring numbers within multiple overlapping subsets. The number of sets and their overlapping number is what will ultimately quantify the answer. I don't believe an easy formula will exist; I'd be interested to know if one does.

Here are the details of the various possible answers for each set of n numbers using 1 through 8:

ONE 1 possible answer: {1}

TWO 1 possible answer: {12}

THREE 2 possible answers: {123, 132}

FOUR 2 possible answers: {1234, 1432}

FIVE 12 possible answers: {12345, 12354, 12534, 12543, 13254, 13452, 14325, 14352, 14523, 14532, 15234, 15432}

SIX 4 possible answers: {123456, 143256, 165234, 165432}

SEVEN 72 possible answers: {1234567, 1234576, 1234756, 1234765, 1235476, 1235674, 1237456, 1237654, 1253476, 1254376, 1256734, 1256743, 1273456, 1274356, 1276534, 1276543, 1325476, 1325674, 1327456, 1327654, 1345276, 1345672, 1347256, 1347652, 1432567, 1432576, 1432756, 1432765, 1435276, 1435672, 1437256, 1437652, 1452376, 1453276, 1456723, 1456732, 1472356, 1473256, 1476523, 1476532, 1523476, 1543276, 1567234, 1567432, 1652347, 1652374, 1652734, 1652743, 1653274, 1653472, 1654327, 1654372, 1654723, 1654732, 1657234, 1657432, 1672345, 1672354, 1672534, 1672543, 1673254, 1673452, 1674325, 1674352, 1674523, 1674532, 1675234, 1675432, 1723456, 1743256, 1765234, 1765432}

EIGHT (72 possible answers): {12345678, 12345876, 12347658, 12347856, 12385476, 12385674, 12387456, 12387654, 12543876, 12567438, 12567834, 12583476, 12743856, 12765438, 12765834, 12783456, 14325678, 14325876, 14327658, 14327856, 14385276, 14385672, 14387256, 14387652, 14523876, 14567238, 14567832, 14583276, 14723856, 14765238, 14765832, 14783256, 16523478, 16523874, 16527438, 16527834, 16543278, 16543872, 16547238, 16547832, 16583274, 16583472, 16587234, 16587432, 16723458, 16723854, 16725438, 16725834, 16743258, 16743852, 16745238, 16745832, 16783254, 16783452, 16785234, 16785432, 18325476, 18325674, 18327456, 18327654, 18345276, 18345672, 18347256, 18347652, 18523476, 18543276, 18567234, 18567432, 18723456, 18743256, 18765234, 18765432}