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. 

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$.
