To check if a number is n choose r

Question

Is there an efficient way to find the number n, given a number N (may be as large as 10^18) which is equal to nCr for some n and r ? How do we find the corresponding minimum value of n? for instance

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

Answer 1

To find minimum n is same as to find maximum r with r<=n/2. Since nCr is bounded from below with (2r)Cr=(2r)!/r!, number of r's to check is finite. For 10^18 maximum r is 31, since 64C32=1.8*10^18.

To find n, for given r, that satisfies N=nCr, it is possible to check is N*r! of form n*(n-1)*...*(n-r+1). n is near (N*r!)^(1/r) + r/2. I think with few checks it can be tested.

Update:

Simple python implementation:

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)

prints:

(31, 7)
False

Answer 2

I will give a pseudo-code. This algorithm does the task in O((N log N)²) time. It is not fast enough, but I have listed some optimizations that can boost the speed significanntly. Maybe someone could optimize this further.

The key here is that we can determine the highest power of a prime number p that divides n! for some n,p without computing the value of n!, by just looking at n, in O(log n) time. We denote the highest power of p that divides n! by hdp(n,p). hdp(n,p) can be computed as: hdp(n,p) = floor(n/p) + floor(n/p²)+.... Thus hdp(n,p) can be computed in log_pn time.

First we compute the list of prime numbers less than or equal to n. Then, we find all prime factors of N. This will be easier because you computed prime numbers upto N in step 1. Let N = p₁^a₁p₂^a₂...p_k^a_k.

The upper and lower bounds for n are given by Ante in his solution. We call them n_max and n_min respectively. Then we iterate for all n between n_min and n_max, for all r between 1 to n. Now, N = ⁿC_r = (n!)/((n-r)!*r!) if and only if hdp(n,p_i) - hdp(k,p_i) - hdp(n-k,p_i) = a_i for all i. So an n-r pair can be pruned in at most O((log n)²) time. Starting with the largest prime factors should be better idea for the degree should be small then.

Some optimizations:

1. for any n, you can find the range in which r can lie, instead of iterating for all r from 1 to n. Use inequalities like ⁿC_r > (n/r)^r etc.

2. No need to consider values of n less than p_k where p_k is the largest prime factor of N.

3. Solve for ⁿC₂ = N separately (It is just a quadratic equation). Now, only consider the values of n that are smaller than this solution. the solution will be of O(N^1/2), so that will reduce the time complexity to O(N(log n)²). Doing this for both ⁿC₂ = N and ⁿC₃ = N will reduce the time complexity to O(N^2/3(log n)²) and so on.