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.

  • 1
    Obligatory link: oeis.org/A086595. – Eric M. Schmidt Jun 5 '15 at 4:32
  • @EricM.Schmidt that's helpful, thanks, but how did they get those values? Also it's not clear whether rotations/reflections are counted or not. In my question, they do not count as separate arrangements. – shardulc Jun 5 '15 at 6:20
  • Presumably the terms were computed using the PARI program provided at the link. It seems that reflections are counted separately but rotations are not (look at the example). If you want to eliminate reflections (writing the numbers in reverse order) just divide the terms (for $n \ge 3$) by 2. – Eric M. Schmidt Jun 5 '15 at 6:29
  • I don't know PARI, but looking at the code, it looks like they're just bruteforcing...? – shardulc Jun 5 '15 at 6:49
  • 1

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}

  • after $n=8: 576$, for $n= 9$ : $6480$ and for $n=10$ : $5760$ – reuns Jun 5 '16 at 3:29
  • With the "big" interpretation, this is oeis.org/A102381 (an algorithm is given for calculating the numbers, but no formula, as such, and no asymptotics, and no links to any literature). – Gerry Myerson Jun 6 '16 at 6:59
  • Your answer is good, but it is still not generalizable enough for me. :) Maybe your method can be extended, I haven't tried it out yet. Also, I fear the numeric patterns in the multiplication (eg. $6 \times (5 - 3) \times \dotsb$) are coincidences due to to the small numbers involved. – shardulc Jun 24 '16 at 14:25

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.