Number of numbers divisible by a prime number in a row to pascal triangle

Question 1

One corollary from Luca's theorem states that number of binomial coefficients C(n,k) which are not divisible by prime p, is (a₁+1)⋅(a₂+1)⋅...⋅(a_m+1), where a_i is ith digit of n in p-ary numeral system.

Example:

p = 3, n = 7_dec = 21₃
Result = (2+1)⋅(1+1) = 6

7th row of Pascal triangle is 1 7 21 35 35 21 7 1, it contains 6 coefficients not divisible by 3, and the two remaining are divisible by 3.

Question 2

You do not need to compute the binomial coefficient (n,r).

Count how often p is in n!, r! and (n-r)! and check if n! has more factors p than the other two togeter.

// sry... no python...
long count_p_in_fac(long n, long p)
{ 
   long count = 0;
   long i = 1;
   long temp;
   while(true)
   {
      temp = floor(n/pow(p,i));
      count += temp;
      if(temp == 0)
         break;
   }
   return count;
}

p = input()
cnt = 0
for i in range(0,n+1):
   if(count_p_in_fac(n,p) > count_p_in_fac(i,p) + count_p_in_fac(n-i,p)):
      cnt += 1
print cnt

This avoids big numbers and reduces the operations.

This checks (n,r) = 0 mod p in O(log(n)) without computing factorials. But counting a row takes O(n log n).

You can also speed this up by using the symmetry of (n,r). Computing only the first half and multiply it by two. If n is even, you have to count the first half exept the middle r = n/2 and check add the middle after multiply by two.

And you can precompute count_p_in_fac(i,p) for all i.

Question 3

There's no way you're going to do 10^12 in less than a second. There has to be some property of Pascall's Triangle that makes this easier.. If it's possible

Another interesting property of Pascal's triangle is that in a row p where p is a prime number, all the terms in that row except the 1s are multiples of p. This can be proven easily, since if p\in \mathbb{P}, then p has no factors save for 1 and itself. Every entry in the triangle is an integer, so therefore by definition (p-k)! and k! are factors of p!\,. However, there is no possible way p itself can show up in the denominator, so therefore p (or some multiple of it) must be left in the numerator, making the entire entry a multiple of p.

It might have something to do with that result (from the wiki page http://en.wikipedia.org/wiki/Pascal%27s_triangle).. if this has an answer (i.e. if it's university homework some professor gave you).

See here https://mathoverflow.net/questions/9181/pascal-triangle-and-prime-numbers

(I love this question - I'm not sure it's a programming question though).

Question 4

You can rewrite your combination function without needing to calculate factorial. (n, r) can be written recursively as

(n, r) = (n-1, r) + (n-1, r-1)

Now we should find the base cases. These are:

(n, 1) = n
(n, 0) = 1
(n, n) = 1

Here, we are assuming that n and r are non-negative integers and n >= r holds true. Then the function combination can be rewritten as

def combination(n, r):
    if r == 1:
        return n
    if r == 0 or r == n:
        return 1
    return combination(n-1, r) + combination(n-1, r-1)

p = input()
count = 0
for i in range(n + 1):
    if combination(n, i) % p == 0:
        count += 1

print count

Question 5

Thank you all for responding to the question of a noob like me Here is a working python code

n,p = map(int,raw_input().split(' '))
if n==p:
    print n-1
elif p>n:
    print 0
else:
    result = 1
    m = n
    while n:
        temp = n%p
        result *= (temp+1)
        n /= p
    print m+1-result

Question 6

n = input("enter the row for pascal triangle:")
p = input("enter any prime number u want:")
cnt = 0
line = [1]
for k in range(0, n):
    line.append(line[k] * (n-k) / (k+1))
print line

lengths = map(lambda word: line[word]%p ==0, range(len(line))).count(True)
print lengths