Creating 6 Digit Numbers Whose Adjacent Digits are Relatively Prime
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