guests seats numbered 1 to guests, and there are just as many guests, numbered 1 to guests. Every guest takes exactly one seat and every seat gets exactly one guest.
The host is superstitious: guest j may sit in seat i only if i and j are coprime, meaning their greatest common divisor is 1.
Count the seating plans in which every seat follows this rule.guests=4 → 4
Seats 2 and 4 only accept the odd guests 1 and 3, which gives 2 options. Guests 2 and 4 are coprime with both 1 and 3, so they fill seats 1 and 3 in 2 ways. That makes 2 · 2 = 4.
guests=2 → 1
Guest 2 cannot take seat 2, so the only valid plan is [2, 1].
guests=1 → 1
guests=4
4
Run checks the first 3 tests in your browser. Submit checks all 15 tests on the server, hidden ones included.