Find number of digits not divisible by X in 100th row of Pascal's Triangle

Question

I need to find out the number of digits which are not divisible by a number x in the 100th row of Pascal's triangle.

The algorithm I applied in order to find this is: since Pascal's triangle is powers of 11 from the second row on, the nth row can be found by 11^(n-1) and can easily be checked for which digits are not divisible by x.

How do I find this out for large numbers when n is equal to 99 or 100? Is there any other algorithm that can be applied to find this?

Answer 1

You can directly calculate values of pascal's triangle using factorials (n!/(n-k+1)!(k-1)! nth row, kth value). You can start with k=1, incrementally calculate binomial coefficient and in n/2 steps you can find the number not divisible by x.

choose(n,k+1) = choose(n,k)*(n-k+1)/k where choose(n,k) = (n!/(n-k+1)!(k-1)!

Answer 2

You don't need exact values of 100th line of the triangle. It's OK to calculate value mod x. Just build the triangle as usual, but apply modulus operation everywhere - you will not need big numbers.