Solve $\binom{n}{k}=m$ for $(n,k)$

Question

For an integer $m>0$, put $X(m)=\{(n,k):4\leq 2k\leq n \text{ and } \binom{n}{k}=m\}$. Is there an efficient method to calculate $X(m)$? Is there a uniform upper bound for $|X(m)|$?

By calculating $\binom{n}{k}$ for $4\leq 2k\leq n\leq 1000$ I have found that $X(3003)\supseteq\{(14,6),(15,5),(78,2)\}$ and seven other cases where $|X(m)|>1$ but no more than that.

This question arose because I am running an online test for undergraduates in which the correct answer is a certain binomial coefficient. Frequently they enter a different binomial coefficient and it is useful for the marking logic to determine the corresponding pair $(n,k)$. In practice this can be done by searching through a fairly small plausible parameter space. However, the theoretical question seemed like it might be interesting.

One possible ingredient is the following fact which is quite well-known to algebraic topologists: if $p$ is prime and $v_p(n)$ is the $p$-adic valuation of $n$ and $\sigma_p(n)$ is the sum of the base $p$ digits of $n$, then $$ v_p\binom{n}{k} = \frac{\sigma_p(k)+\sigma_p(n-k)-\sigma_p(n)}{p-1} $$

[UPDATE: The comments give a good answer about upper bounds for $|X(m)|$; but I am still interested in an algorithm for a given $m$.]

Answer 1

You can find a solution in logarithmic time by starting with $i=2$, each time searching (with binary search, for example) for the smallest number such that $\binom{n}{i} \geq m$, return $(n, i)$ if it's exactly $m$, and terminate once $\binom{2i}{i} > m$.

For correctness of the early termination, we can see that if $\binom{n}{k} = m$ and $2k \leq n$, we also have $\binom{2k}{k} \leq m$, and since the central binomial coefficients are increasing we won't terminate before $k$.

For the runtime, since the central binomial coefficients grow exponentially, the number of steps must be $O(\log m)$.

Here's an efficient Python implementation, using Newton's method, either directly on the polynomial if $i$ is small (so we need a lot of precision), or on the logarithm if $i$ is large:

import math
import gmpy2
import scipy.special


def binom_der(x, i):
    v, d = 1, 0
    for j in range(i):
        v, d = v * (x - j), v + d * (x - j)
    return v, d


def newton(mt, i):
    x = int(gmpy2.root(mt, i) + 1)
    lt = 0
    gt = math.inf
    if x < 1000000:
        mlg = math.log(mt)
        while True:
            fv = math.lgamma(x + 1) - math.lgamma(x - i + 1)
            fd = scipy.special.psi(x + 1) - scipy.special.psi(x - i + 1)
            nx = x - (fv - mlg) / fd
            if abs(nx - x) <= 0.001:
                if abs(nx - round(nx)) <= 0.01:
                    v = round(nx)
                    if math.perm(v, i) == mt:
                        return v
                return None
            x = nx
    while True:
        fv, fd = binom_der(x, i)
        if fv == mt:
            return x
        if fv < mt:
            lt = max(lt, x)
        else:
            gt = min(gt, x)
        if gt - lt <= 1:
            return None
        nx = x + (mt - fv) // fd
        if x == nx:
            return None
        x = nx

def invb(m):
    i = 2
    mt = m
    while math.comb(2 * i, i) <= m:
        mt *= i
        n = newton(mt, i)
        if n:
            assert math.comb(n, i) == m
            return n, i
        i += 1
    return None
```