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.
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.