要检查数字是否为 n，请选择 r

Question

有没有一种有效的方法来找到数字 n，给定一个数字 N（可能大到 10^18），它等于某些 n 和 r 的 nCr？我们如何找到相应的最小值 n？例如

f(20)=6 (20=6C3)  
f(21)= 7 (21=7C2)  
f(22)= 22 (22=22C1)

Answer 1

查找最小值 n 与查找最大值 r 相同 r<=n/2 。因为nCr是从下面用(2r)Cr=(2r)!/r!来界定的，要检查的r的数量是有限的。对于10^18最大 r 为 31，因为 64C32=1.8*10^18 .

对于给定的 r，要找到满足 N=nCr 的 n，可以检查形式是否N*r! n*(n-1)*...*(n-r+1)。 n 接近 (N*r!)^(1/r) + r/2 。我认为只需很少的检查就可以进行测试。

更新：

简单的 python 实现：

from operator import mul  # or mul=lambda x,y:x*y
from fractions import Fraction
def nCk(n,k):
  return int(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1))
def M(f,t):
  return reduce(mul, range(f,t+1), 1)
def find_n_r(N):
  for r in range(2, 50): # omit 1, since it is trivial solution
    if nCk(2*r, r) > N:
      return False
    Nr = N * M(1,r)
    nn = pow(Nr, 1./r) + r*0.5
    n = int(nn)
    if M(n-r+1,n) == Nr:
      return n, r
    n += 1
    if M(n-r+1,n) == Nr:
      return n, r  
print find_n_r(nCk(31,7))
print find_n_r(nCk(31,7) + 12)

指纹：

(31, 7)
False

Answer 2

我将给出一个伪代码。该算法在 O（（N log N）²） 时间内完成任务。它不够快，但我列出了一些可以显着提高速度的优化。也许有人可以进一步优化这一点。

这里的关键是，我们可以确定一些 n，p 的素数 p 的最高幂，而无需计算 n！ 的值，只需查看 n，在 O（log n） 时间内。我们表示除以 n 的 p 的最高幂！由HDP（n，P）。hdp（n，p） 可以计算为：HDP（n，p） = 地板（n/p） + 地板（n/p²）+....因此，hdp（n，p） 可以用对数_pn 时间计算。

首先，我们计算小于或等于n的素数列表。然后，我们找到 N 的所有素因数。这会更容易，因为您在步骤 1 中计算了最多 N 的素数。设 N = p 1 a ^₁p 2 ^a₂...噗_嗤

n 的上限和下限由 Ante 在他的解中给出。我们分别称它们为 n_max 和 n_min。然后，我们迭代 n_min 到 n_max 之间的所有 n，迭代 1 到 n 之间的所有 r。现在，N = n C_r = （ⁿ！）/（（n-r）！*r！）当且仅当 hdp（n，p i） - hdp（k，p i） - hdp（n-k，p i） = a i 对于所有_i。因此，最多可以在 O（（log n）²） 时间内修剪 n-r 对。从最大的素因数开始应该是更好的主意，因为程度应该很小。

一些优化：

1. 对于任何 n，您可以找到 r 可以撒谎的范围，而不是从 1 到 n 迭代所有 r.使用不等式，如 n C r> （ⁿ/r）^r 等。

2. 无需考虑小于 p k 的 n 值，其中 p_k 是 N 的最大素因数。

3. 分别求解 ⁿC₂ = N（它只是一个二次方程）。现在，只考虑小于此解决方案的 n 值。 解将是 O（N^1/2），因此将时间复杂度降低到 O（N（log n）²）。对 n C 2 = N 和 n C 3 = N 执行此操作会将时间复杂度降低到 O（N 2^/3（log ⁿ）²） 等。