Loading problem...
Given a positive integer n, your task is to count the number of valid arrangements of the sequence [1, 2, 3, ..., n] such that each element and its corresponding position are mutually coprime.
An arrangement is considered valid (or position-coprime) if for every position i (where positions are numbered from 1 to n), the element placed at position i shares no common divisor with i other than 1. In mathematical terms, for each position i from 1 to n, the condition gcd(element[i], i) = 1 must hold true, where gcd denotes the greatest common divisor.
A permutation of a sequence is any rearrangement of its elements. For the sequence [1, 2, 3], the complete set of permutations includes:
Your goal is to determine how many of these permutations satisfy the position-coprime property described above.
n = 11The only sequence [1] has a single permutation. Since gcd(1, 1) = 1, this arrangement is position-coprime. Therefore, the answer is 1.
n = 21The sequence [1, 2] has two permutations: • [1, 2]: At position 2, we have element 2. Since gcd(2, 2) = 2 ≠ 1, this arrangement is NOT position-coprime. • [2, 1]: At position 1, gcd(2, 1) = 1 ✓. At position 2, gcd(1, 2) = 1 ✓. This arrangement IS position-coprime. Only one valid arrangement exists.
n = 33The sequence [1, 2, 3] has six permutations. Let's verify each: • [1, 2, 3]: gcd(2, 2) = 2 ≠ 1, invalid. • [1, 3, 2]: gcd(3, 2) = 1 ✓, gcd(2, 3) = 1 ✓, valid! • [2, 1, 3]: gcd(3, 3) = 3 ≠ 1, invalid. • [2, 3, 1]: gcd(3, 2) = 1 ✓, gcd(1, 3) = 1 ✓, valid! • [3, 1, 2]: gcd(3, 1) = 1 ✓, gcd(1, 2) = 1 ✓, gcd(2, 3) = 1 ✓, valid! • [3, 2, 1]: gcd(2, 2) = 2 ≠ 1, invalid. Three valid arrangements exist: [1, 3, 2], [2, 3, 1], and [3, 1, 2].
Constraints