Solution for a combinatorial minimization problem

Let's say we have an inequality, $p \le {a \choose b}$ where $p$ is a fixed constant and $a, b$ are variables. The problem is that, we are trying to find the minimum $a$ with respect to the inequality $p \le {a \choose b}$. Is there a closed form solution (can be approximate as well/doesn't have to be exact) for that combinatorial optimization problem?

G. Bach noticed that the best choice for $b$ is $\lfloor a/2 \rfloor$, and furthermore this choice gives the maximal binomial coefficient. The easiest way to see this is to consider the ratio of two adjacent binomial coefficients:
$$ \frac{\binom{a}{b}}{\binom{a}{b+1}} = \frac{b+1}{a-b}.$$
Therefore $\binom{a}{b} \leq \binom{a}{b+1}$ iff $b+1 \leq a-b$ iff $2b+1 \leq a$, and we get the desired result.

The binomial theorem states that
$$ \sum_{b=0}^a \binom{a}{b} = 2^a, $$
hence
$$ \frac{2^a}{a+1} \leq \binom{a}{\lfloor a/2 \rfloor} \leq 2^a. $$
(The correct order of magnitude, $\Theta(2^a/\sqrt{a})$, can be found using Stirling's approximation.) Therefore the optimal $a$ satisfies the following inequalities:
$$ \frac{2^{a-1}}{a} 2\frac{2^{a-1}}{a} (a - \log_2 a) > 2^{a-1}.$$
We conclude that
$$ \log_2 p \leq a < \log_2 p + 1 + \log_2 \log_2 (2p). $$
Therefore the binary search that G. Bach mentions takes only $O(\log\log\log p)$ steps.

If all we want is an asymptotic expression, then since $\binom{a}{\lfloor a/2 \rfloor} = \Theta(2^a/\sqrt{a})$, approximately we have $2^a/\sqrt{a} = Cp$, and so $a = \log_2 p + \Theta(\log_2\log_2 p)$. More terms can be obtained by taking more terms in Stirling's approximation. For example, we can find a constant $A$ such that $a = \log_2 p + A\log_2\log_2 p + o(\log_2\log_2 p)$.

StackExchange Computer Science Q#14135, answer score: 6