# How can I find the first occurrence of a number in Pascal's triangle?

Is there a way to efficiently(ie: without building the actual triangle) to find out which row a number first occurs in in Pascal's triangle?

This is equivalent to answering: given A what is the smallest number m such that there exists n such that m choose n = A. This is due to the fact that a number at row m and column n in Pascal's triangle is equal to m choose n.

-
–  JavaMan Jan 29 '12 at 1:10
Apply the algorithm described in the link above, but start with the largest value of $k$ first. –  Qiaochu Yuan Jan 29 '12 at 1:11

The link provided by JavaMan indeed answers this question: How to reverse the $n$ choose $k$ formula?

A summary of the algorithm -- took me while to figure out from that answer, so I'm writing it as an algorithm instead of an explanation of one. If you want to know how this works, I highly recommend visiting that answer and upvoting it, it's very informative -- is as follows. First, the problem is minimizing n given X such that:

$${n \choose k} = X$$

First we determine max(k) given that we know that: $$X > \frac{4^k}{2k+1}$$

From there we iterate over 1 to max(k). At each step of the iteration, n, if it exists is contained in the interval:

$$\sqrt[k]{k! X} + k \ge n \ge \sqrt[k]{k! X}$$

We iterate over that interval and check if ${n \choose k}=X$. We can then easily find the minimum such n.

-