algorithm - Binomial coefficient modulo 142857

Question

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.

Answer 1

You can actually calculate C(n,k) % m in O(n) time for arbitrary m.

The trick is to calculate n!, k! and (n-k)! as prime-power-vectors, subtract the two later from the first, and multiply the remainder modulo m. For C(10, 4) we do this:

10! = 2^8 * 3^4 * 5^2 * 7^1
 4! = 2^3 * 3^1
 6! = 2^4 * 3^2 * 5^1

Hence

C(10,4) = 2^1 * 3^1 * 5^1 * 7^1

We can calculate this easily mod m as there are no divisions. The trick is to calculate the decomposition of n! and friends in linear time. If we precompute the primes up to n, we can do this efficiently as follows: Clearly for each even number in the product 1*2*...*9*10 we get a factor of 2. For each fourth number, we get a second on and so forth. Hence the number of 2 factors in n! is n/2 + n/4 + n/8 + ... (where / is flooring). We do the same for the remaining primes, and because there are O(n/logn) primes less than n, and we do O(logn) work for each, the decomposition is linear.

In practice I would code it more implicit as follows:

func Binom(n, k, mod int) int {
    coef := 1
    sieve := make([]bool, n+1)
    for p := 2; p <= n; p++ {
        // If p is not sieved yet, it is a prime number
        if !sieve[p] {
            // Sieve of Eratosthenes
            for i := p*p; i <= n; i += p {
                sieve[i] = true
            }
            // Calculate influence of p on coef
            for pow := p; pow <= n; pow *= p {
                cnt := n/pow - k/pow - (n-k)/pow
                for j := 0; j < cnt; j++ {
                    coef *= p
                    coef %= mod
                }
            }
        }
    }
    return coef
}

This includes a Sieve of Eratosthenes, so the running time is nloglogn rather than n if the primes had been precalculated or sieved with a faster sieve.