Wednesday, December 19, 2012

Lucas' Theorem to solve binomial coefficients

I am happy cause only one problem and i will be done solving interviewstreet mathematical problems. After solving the Binomial Coefficients  problem i think i have something useful to share with you.

In this problem you are given two number N and P, where P is a prime number. You are requested to find how many binomial coefficients of n become to 0 after modulo by P.

So the output should be the number of  \tbinom nks (0<=k<=n)  each of which after modulo operation by P is 0.

I hear you saying its an easy problem, but you won't say that after knowing about the input constraints.

n is less than 10500.
P is less than 109.

For such large number i will use Java to solve this problem, thanks to the BigInteger Class in java. After doing some search i found that there is a theorem called Lucas' Theorem which is as follows:

Given n, k, and prime p, binomial (n,k) is divisible by p if and only if at least one of  the base p digits of k is larger than the corresponding digit of m (also base p digit).

So to solve this problem we need to find the base P representation of n, and counting how many numbers (R) that have all digits (in base P) less than the corresponding digit in n.

1. We have k is between 0 and n, so we have (n+1) numbers to check with n.
2. Now need to find R.

Now if n in base P is as follows: abc...

Then we need to get all numbers that have:

1. First digit is 0, 1, 2, .... a-1
2. Second digit is 0, 1, 2, .... b-1
3. Third digit is 0, 1, 2, ...., c-1

Obviously R = (a+1)*(b+1)*(c+1).

So we have (n+1) total numbers, subtracting  R, then the result would be n+1-R.


  1. This comment has been removed by the author.

  2. Totally, the actual write-up is really the very best in that will worthwhile matter. I really fit in jointly with your results and certainly am going to keenly seem to be toward your own upcoming improvements. Just telling many thanks could not only be sufficient, for your exceptional readability as part of your composing.I'll use this information to provide term papers for my friends.