5

Now that CodeSprint 3 is over, I've been wondering how to solve this problem. We need to simply calculate nCr mod 142857 for large values of r and n (0<=n<=10^9 ; 0<=r<=n). I used a recursive method which goes through min(r, n-r) iterations to calculate the combination. Turns out this wasn't efficient enough. I've tried a few different methods, but they all seem to not be efficient enough. Any suggestions?

Sumurai8
  • 20,333
  • 11
  • 66
  • 100

1 Answers1

9

For non-prime mod, factor it (142857 = 3^3 * 11 * 13 * 37) and compute C(n,k) mod p^q for each prime factor of the mod using the general Lucas theorem, and combine them using Chinese remainder theorem.

For example, C(234, 44) mod 142857 = 6084, then

  • C(234, 44) mod 3^3 = 9
  • C(234, 44) mod 11 = 1
  • C(234, 44) mod 13 = 0
  • C(234, 44) mod 37 = 16

The Chinese Remainder theorem involves finding x such that

  • x = 9 mod 3^3
  • x = 1 mod 11
  • x = 0 mod 13
  • x = 16 mod 37

The result is x = 6084.

Example

C(234, 44) mod 3^3

First convert n, k, and n-k to base p

n = 234_10 = 22200_3

k = 44_10 = 1122_3

r = n-k = 190_10 = 21001_3

Next find the number of carries

e[i] = number of carries from i to end
e   4 3 2 1 0
        1 1
r   2 1 0 0 1
k     1 1 2 2
n   2 2 2 0 0

Now create the factorial function needed for general Lucas

def f(n, p):
    r = 1
    for i in range(1, n+1):
        if i % p != 0:
            r *= i
    return r

Since q = 3, you will consider only three digits of the base p representation at a time

So

f(222_3, 3)/[f(210_3, 3) * f(011_3, 3)] *
f(220_3, 3)/[f(100_3, 3) * f(112_3, 3)] *
f(200_3, 3)/[f(001_3, 3) * f(122_3, 3)] = 6719344775 / 7

Now

s = 1 if p = 2 and q >= 3 else -1

Then

p^e[0] * s * 6719344775 / 7 mod 3^3
e[0] = 2
p^e[0] = 3^2 = 9
s = -1
p^e[0] * s * 6719344775 = -60474102975

Now you have

-60474102975 / 7 mod 3^3

This is a linear congruence and can be solved with

ModularInverse(7, 3^3) = 4
4 * -60474102975 mod 27 = 9

Hence C(234, 44) mod 3^3 = 9

miles
  • 226
  • 1
  • 7
  • Can you explain how to use the general Lucas Theorem to compute C(n, k) mod p^q? – jonderry Nov 22 '12 at 20:18
  • I made an example, or did you want pseudocode? Much of this relies on an implementation of Extended Euclidean to get GCDs to simplify the factorials and to do the modular inverse needed for solving the linear congruence and for combining using the Chinese Remainder theorem – miles Nov 23 '12 at 02:40
  • This is better, but I don't really understand why it works, other than trying to slavishly copy what is described in the paper and hope it works. I understand extended Euclid, modular inverses, and CRT, as well as the original version of Lucas' Theorem, but have no intuition for why the extended version is true, and how the corresponding algorithm works (i.e., why should we expect it to give a correct result?). – jonderry Nov 23 '12 at 08:32
  • Why you just said s to be -1 ? I just read generalised Lucas Theorem. It has a power, e_q-1. – rnbguy Jul 28 '13 at 22:36
  • By the way, I think the number carries when you are adding a and b in base p is same as the number of power p in (a+b)Cb. Am I right ? – rnbguy Jul 28 '13 at 22:39