calculating Combination for large numbers

Question

I'm trying to calculate if a particular entry in the 100th row of Pascal's triangle is divisible by 3 or not.I'm calculating this using the formula nCr where n=100 and r is the different entries in the 100th row. I'm using the below code to calculate combination

 public static double Combination(int n, int m, double comb)
    {
        for (int r = -1; ++r < m; )
            comb = comb * (n - r) / (r + 1);
        return comb;
    }

But for values such as 100C16 i'm getting large number containing decimal and e in it. I searched on the internet found that actually there are 12 numbers which are not divisible by 3, but my program gives me 63 number which are not divisible by 3 in 100th row which is wrong.Can any tell me what is it that i'm doing wrong.

Answer 1

I assume "nCr" is shorthand for n-choose-r, or choose r from N, right?

To see if nCr is divisible by three, you don't need to calculate the result, you just need to figure out if it's divisible by 3. You have to see how many times n! is divisible by 3, and then how many times r! is divisible by 3 and how many times (n-r)! is.

It really is quite simple - 1! is not divisible by 3, 2! isn't, 3! is divisible once. 4! and 5! are also divisible once. 6! is divisible twice, and so are 7! and 8!. 9! is divisible 4 times, and so on. Go all the way up to n (or work out the formula without calculating incrementally, it's not all that hard), and check.

Clarification - my math studies where in Hebrew, so "How many times n! is divisible by 3" may not be the proper English way of saying it. By "n! is divisible by 3 m times" I mean that n!=3^m*k, where k is not divisible by 3 at all.

EDIT: An example. Let's see if 10c4 is divisible by 3.

Let's make a small table saying how many times k! is divisible by 3 (the k! column is just for demonstration, you don't actually need it when calculating the divisiblity column):

  k      k!     Divisibility
  1       1     0
  2       2     0
  3       6     1
  4      24     1
  5     120     1
  6     720     2
  7    5040     2
  8   40320     2
  9  362880     4
 10 3628800     4

10c4 is 10! / (6! * 4!) .

10! is divisible 4 times (meaning 10! = 3^4 * something not divisible by 3), 6! is divisible 2 times 4! is divisible 1 time

So 10! (6! * 4!) is divisible by 3. It is in fact 3 * 70.

Answer 2

First of all you are using doubles, I don't think that's a good idea. Floating point numbers will give errors after a while.

If the number will not grow that huge one could use the following method:

public static long nCr (int m, int n) {
    long tmp = 1;
    int j = 2;
    int k = m-n;
    for(int i = m; i > k; i--) {
        tmp *= i;
        while(j <= n && tmp%j == 0) {
            tmp /= j++;
        }
    }
    while(j <= n) {
        tmp /= j++;
    }
    return tmp;
}

In this case however this still isn't enough. In that case one can use the BigInteger struct in System.Numerics

public static BigInteger nCr (int m, int n) {
        BigInteger tmp = 1;
        int j = 2;
        int k = m-n;
        for(int i = m; i > k; i--) {
            tmp *= i;
            while(j <= n && tmp%j == 0) {
                tmp /= j++;
            }
        }
        while(j <= n) {
            tmp /= j++;
        }
        return tmp;
    }

You could argue that with a BigInteger one doesn't need to interleave devision and multiplication. However if BigInteger is quite big the operations on the data will take some time (because the number is represented as an array of a number of bytes). By keeping it small one can avoid long calculation times.