Given any positive integer $~m~$ there always exist pair of positive integers $~(n,k)~$ such that $~\binom{n}{k} = m~$. At least we can take $~n = m~$ and $~k = 1~$.
How can we efficiently find all such pairs?
For example, if $~m = 15~$ then all the pairs are $~(6,2),~(6,4),~(15,1),~(15,14)$.
Legendre's formula allows us to compute for each prime $~p~$ its power in factorization of $~\binom{n}{k}$: $$\sum_{i=1}^{\infty} \left( \left \lfloor \frac{n}{p^i} \right \rfloor - \left \lfloor \frac{k}{p^i} \right \rfloor - \left \lfloor \frac{n-k}{p^i} \right \rfloor \right)$$ and thus we can try to somehow use factorization of $~m~$ to estimate $~n~$ and $~k~$. But i'm not sure whether this approach is useful and how to implement it.
Thank you for any ideas!
P.S. I'm first of all interested in algorithmic solution. We may assume that $~m \leq 10^{15}$.
You can handle, say, $k\le5$ using $m=\binom nk\lesssim\frac{\left(n-\frac{k-1}2\right)^k}{k!}$ and thus $n\gtrsim\frac{k-1}2+\sqrt[k]{k!m}$, which should be acccurate enough to only require a couple of tries for each $k$. For $k=5$ the highest possible value of $n$ is about $2+\sqrt[5]{5!10^{15}}\approx2607$, and since $\binom nk$ is increasing in $n$ and decreasing in $k$ (for $k\le\frac n2$, the only values we need), you can now in each step increment $k$ and then decrement $n$ until $\binom nk\le m$. Since each increment and decrement only requires one multiplication and one division and there are at most $\sim2607$ of them, this takes less than $\sim10^4$ operations.