可以被行中的素数整除为pascal三角形的数字的数量

Question

如何找到一个pascal三角形的给定行号中的数字总数,该三角形可以被一个素数整除,其中给出行号和素数我在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

但是给定的代码需要很长时间才能获得大数字.你能告诉我一个更好的算法吗？

Answer 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)?...?(am+1), where a_i 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.