在 Pascal 三角形中能被质数整除的数的数量

1 投票

6 回答

1755 浏览

提问于 2025-04-17 23:05

我想知道，如何找到在给定的帕斯卡三角形的某一行中，有多少个数字是能被一个质数整除的。这个行号和质数都是已知的。我在用下面的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

不过，这段代码在处理大数字时运行得很慢。你能给我推荐一个更好的算法吗？

算法优化质数组合数学帕斯卡三角形数论

6 个回答

感谢大家回复像我这样的新手提问！这里有一段可以运行的Python代码。

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

回答于 2025-04-17 由 Python大师

分享举报

你不可能在不到一秒的时间内计算出10的12次方。帕斯卡三角形一定有一些特性可以让这个问题变得简单一些……如果这是可能的话。

帕斯卡三角形还有一个有趣的特性，就是在某一行p中，当p是一个质数时，除了1以外的所有项都是p的倍数。这一点很容易证明，因为如果p是质数，那么它除了1和它自己之外没有其他因数。三角形中的每个数都是整数，因此根据定义，(p-k)!和k!都是p!的因数。然而，p本身不可能出现在分母中，所以p（或者它的某个倍数）必须留在分子里，这样整个项就成了p的倍数。

这可能和那个结果有关（来自维基百科页面 http://en.wikipedia.org/wiki/Pascal%27s_triangle）……如果这个问题有答案的话（也就是说，如果这是某个教授布置的大学作业）。

可以查看这里 https://mathoverflow.net/questions/9181/pascal-triangle-and-prime-numbers

（我很喜欢这个问题——不过我不确定这是否是一个编程问题）。

回答于 2025-04-17 由 Python大师

分享举报

你可以重写你的组合函数，而不需要计算阶乘。(n, r) 可以用递归的方式来写，具体如下：

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

现在我们需要找出基本情况。这些情况是：

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

在这里，我们假设 n 和 r 是非负整数，并且 n >= r 这个条件成立。然后，函数 combination 可以重写为：

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

回答于 2025-04-17 由 Python大师

分享举报

你不需要计算二项式系数 (n,r)。

只需要计算一下 p 在 n!、r! 和 (n-r)! 中出现的次数，然后看看 n! 中的 p 的数量是否比另外两个加起来的数量还要多。

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

这样做可以避免处理大数字，并减少计算的步骤。

这个方法可以在 O(log(n)) 的时间内检查 (n,r) = 0 mod p，而不需要计算阶乘。不过，计算一行的次数需要 O(n log n)。

你还可以通过利用 (n,r) 的对称性来加速这个过程。只计算前半部分，然后乘以二。如果 n 是偶数，你需要计算前半部分，但要排除中间的 r = n/2，然后在乘以二后再加上中间的部分。

另外，你可以提前计算 count_p_in_fac(i,p) 对于所有的 i。

回答于 2025-04-17 由 Python大师

分享举报

根据卢卡斯定理，有一个结论是：在一个数字中，计算不被某个质数p整除的二项式系数C(n,k)的数量，可以用这个公式来表示：(a₁+1)⋅(a₂+1)⋅...⋅(a_m+1)。这里的a_i是数字n在以p为底的数字系统中的第i位数字。

举个例子：

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

帕斯卡三角形的第七行是1 7 21 35 35 21 7 1，其中有6个系数是不被3整除的，而剩下的两个是可以被3整除的。

回答于 2025-04-17 由 Python大师

分享举报

在 Pascal 三角形中能被质数整除的数的数量

6 个回答

撰写回答