subfactorial modulo prime (!n mod p)
algorithm, math
Solution
It turns out that `!n mod p` is periodic with a period of `2p`. Thus we can compute `!n mod p` as `!(n mod 2p) mod p`, which we do with the recursive formula for derangements `!n = (n-1) (!(n-1) + !(n-2))`.
For a proof:
- Observe that `!(p+1) = 0 mod p`, by the recursive relation for derangements.
- Working modulo p, `!(n+p) = !p * !n` (this can be proved inductively using the previous observation).
- Observe that `!p = -1 mod p`. Wikipedia provides a formula: `!n = n! - Sum[(n choose i) * !(n-i), i=1..n]` -- modulo p, the only nonzero term on the right hand side appears where `i=n`.
- Conclude that `!(n+2p) = !p !p !n = !n mod p`.
From the proof, we see that we can in fact compute `!n = ± !(n mod p) mod p` where the sign is positive when `n mod 2p` is less than `p`.
Problem
Is there a simple way to implement `!n mod p` (number of derangements) `where n ≤ 2∗10^8` and `p` is a prime and `p < 1000` The program must execute fast so the naive approach doesn't work.