Binomial coefficient modulo 142857
algorithm, binomial-coefficients, combinatorics, math
Solution
The algorithm is:
- factorise the base into prime powers; 142857 = 3^3×11×13×37
- compute the result modulo each prime power
- combine the results using the Chinese Remainder Theorem.
To compute `(n above k) mod p^q`:
Source: http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf, theorem 1
define `(n!)_p` as the product of numbers `1..n` that are not divible by `p`
define `n_j` as `n` after erasing `j` least significant digits in base `p`
define `r` as `n`-`k`
define `e_j` as the number of carries when adding `k+r`, not counting the carries from `j` lowest digits, computing in base `p`
define `s` as `1` if `p=2 & q>=3` and `-1` otherwise
then `(n above k) mod p^q := p^e_0 * s^e_(q-1) * concatenate(j=d..0)( (n_j!)_p / ((k_j!)_p*(r_j!)_p) )` with each term of the concatenation computing one base-p digit of the result, lowest `j` computing the least significant non-zero digits.
Problem
How to calculate binomial coefficient modulo 142857 for large `n` and `r`. Is there anything special about the 142857? If the question is modulo `p` where `p` is prime then we can use Lucas theorem but what should be done for 142857.