Search code examples
pythonalgorithmprimesfactorial

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

How can i find the total number of numbers in a given row number of a pascal triangle divisible by a prime number in which the row number and prime is given I am using the following code in python

def factorial(x):
    result = 1
    for i in xrange(1,x+1):
        result *= i
    return result

def combination(n,r):
    return factorial(n)/(factorial(n-r)*factorial(r))

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

but the given code takes long time for big numbers. Can you please suggest me a better algorithm.

Solution

  • 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)⋅...⋅(am+1), where ai is ith digit of n in p-ary numeral system.

    Example: 

    p = 3, n = 7dec = 213
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.