Project Euler Problem 886
A permutation of 2,3,ldots,n is a rearrangement of these numbers.
Solution
A key observation is that among the numbers $2,\dots,34$, there are $17$ even numbers and $16$ odd numbers. Since two even numbers can never be adjacent (they always share a factor $2$), every valid coprime permutation must alternate parity:
$$E,O,E,O,\cdots,O,E$$
This reduces the problem to counting alternating compatible sequences, where compatibility depends only on shared odd prime factors. Compressing numbers by their odd-prime-factor masks and performing dynamic programming over the remaining multiplicities of each mask-type yields the final value modulo $83{,}456{,}729$.
The computation reproduces the checks:
- $P(4)=2$
- $P(10)=576$
and finally gives:
Answer: 67630318