# Creating 6 Digit Numbers Whose Adjacent Digits are Relatively Prime

Six-digit integers will be written using each of the digits $1$ through $6$ exactly once per six-digit integer. How many different positive integers can be written such that all pairs of consecutive digits of each integer are relatively prime? (Note: $1$ is relatively prime to all integers.)

The pairs of numbers that are relatively prime from $1-6$ are: $1:2,3,4,5,6$ and $2:3,5$ and $3,4,5$ and $4,5$ and $5,6$. Now, what should I do from here.

• I'd be surprised and pleased if there were a solution other than essentially brute force. – Ethan Bolker Feb 25 '18 at 16:05
• Even with, e.g., brute force, you can speed it up in certain ways. As one small example: List all the numbers with this property that have 1 to the left of 6; since a number with this property retains it when reversed, you can then take that list (of just 36 elements) and its reverses for the total. There is also a bit of craftiness around where a 6 can appear... – Benjamin Dickman Feb 25 '18 at 16:29
• Note that this question is equivalent to counting Hamiltonian paths on the graph with nodes $1\ldots 6$ and edges between relatively prime points: i.imgur.com/IuBRxzE.gif . In the abstract, the problem of counting Hamiltonian paths is known to be #P-complete, so it shouldn't be any surprise that there's not necessarily a 'clever' solution here. – Steven Stadnicki Feb 26 '18 at 18:06

Edit 2: If you consider the analogous question for five digit numbers, then you will also find that the answer is $72$; so, perhaps someone can find a slick bijection between the two sets.

The technique for five digit numbers is relatively simple:

You need to avoid having $2$ and $4$ as adjacent; so, you can place them without constraints in $5(4) = 20$ places, but then subtract off the $8$ adjacent cases for $12$ in total.

Once $2$ and $4$ are placed, the $1$, $3$, and $5$ can be placed in any order among the three empty slots, i.e., $3! = 6$ ways, yielding $12 \cdot 6 = 72$ as the total.

Edit 1: Here is an AoPS link that also finds the answer to be 72. The underlying technique is to place the 2, 4, and 6 first; then, you figure out where the remaining digits can go. For those who do not wish to click through, here is an image of the text: Brute force, in case others have craftier ways and want to check/verify; seventy two in total:

123456 143256 165234 165432 213456 214356 216534 216543 231456 231654 234156 234165 234516 234561 235416 235614 253416 254316 256134 256143 321456 321654 325416 325614 341256 341652 345216 345612 412356 413256 416523 416532 431256 431652 432156 432165 432516 432561 435216 435612 452316 453216 456123 456132 523416 543216 561234 561432 612345 612354 612534 612543 613254 613452 614325 614352 614523 614532 615234 615432 651234 651432 652134 652143 652314 652341 653214 653412 654123 654132 654312 654321

• sadly, this does not work. I will try to refine the list. – A Piercing Arrow Feb 25 '18 at 16:29
• @shouldn'tbehere I pasted a list of these numbers (link) and then removed those with any of the substrings: 24, 26, 36, 42, 46, 62, 63, 64 – Benjamin Dickman Feb 25 '18 at 16:36
• @BenjaminDickman I input my answer, and it is incorrect. And: Brute force is a method which, although sometimes inefficient, works when trying to solve problems which you don't have a slick solution for. For example: Trying to count the number of ways which $a+b+c=51$ is true for integers $a,b,$ and $c$. This can be solved using stars and bars, but if you didn't know this, you would list out every single possible solution. That is brute force. – A Piercing Arrow Feb 25 '18 at 16:37
• I don't get why $72$ is not the correct answer? – ArsenBerk Feb 25 '18 at 16:53
• I am so sorry. You are very right. THe answer was $72$. I was looking at the wrong problem when I answered. – A Piercing Arrow Feb 25 '18 at 16:55

If $6$ is an interior entry then it has to appear in one of the subwords $165$ or $561$. If all three of $\{2,3,4\}$ are on the same side of these the digit $3$ has to be in the middle of the three (gives $4$ ways). If one of $\{2,3,4\}$ stands alone it has to be one of $2$ and $4$ (gives another $8$ ways). In all there are $24$ admissible words of this kind.

If $6$ is the first or last entry the entry next to $6$ has to be $1$ or $5$. The remaining four digits could be arranged in $4!=24$ ways, but we have to exclude the $2\cdot 3!=12$ ways containing $24$ or $42$ as a subword. It follows that there are $2\cdot 2\cdot(24-12)=48$ admissible words of this kind.

The total number of admissible words therefore is $72$.