"Binomiable" numbers

Here is a partial answer for a special case: if $\sqrt{8n+1}$ is an odd integer, then $n$ is a binomial coefficient of the form $n \choose 2$. Such a formula is possible because $n \choose 2$ is quadratic in $n$ and therefore has a straightforward solution.

I don't think theres a single simple criterion, but one could construct an algorithm for determining it with time complexity of $O((\ln c)^2)$ binomial coefficients or $O((\ln c)^3)$ multiplicaitons. Besides it may be unknown or hard to determine totally certainly whether the number is actually prime or not.

What we can use is to estimate the coefficients:

$$\binom{n}{k} = {\prod_0^k (n-j)\over\prod_0^k j} = {\prod_0^k (n-(k/2)+k/2-j)\over\prod_0^k j} \\ = \begin{cases} {(n-k/2)\prod_0^{(k-1)/2} (n-(k/2)-k/2+j)(n-(k/2)+k/2-j)\over\prod_0^k j} = {(n-k/2)\prod_0^{(k-1)/2} (n-(k/2))^2-(k/2+j)^2\over\prod_0^k j} & \text{ if } k \text{ is odd } \\ {\prod_0^{k/2} (n-(k/2))^2-(k/2+j)^2\over\prod_0^k j} & \text{ if } k \text{ is even } \\ \end{cases} \\ \le {(n-k/2)^k\over k!}$$

We also can estimate it from below:

$${(n-k)^k\over k!} \le \binom{n}{k} \le {(n-k/2)^k\over k!}$$

So given $k$ we have an estimate for $n$

$$(k!c)^{1/k} \le n \le (k!c)^{1/k} + k/2$$

Also since we only have to consider $2k<n$ we can use the estimate:

$$\binom{n}{k} \ge \binom{2k}{k} = {(2k)!\over k!k!}$$

So we don't have to consider $k$ with $(2k)!/(k!)^2 > c$ and since it's increasing we can terminate the algorithm once it happens.

Take for example the numbers $8008$ and $8009$ (the later being prime)

We have the ranges of $n$ depending on $k$ as:

$$\begin{matrix} k & n_{min} & n_{max} & \binom{2k}{k} \\ \hline 2 & 127 & 127 & 6\\ 3 & 37 & 37 & 20 \\ 4 & 21 & 22 & 70 \\ 5 & 16 & 18 & 252 \\ 6 & 14 & 16 & 924 \\ 7 & 13 & 15 & 3432 \\ 8 & & & 12870 \end{matrix}$$

That is we only have to consider $\binom{127}{2}$, $\binom{37}{3}$, $\binom{21}{4}$, $\binom{22}{4}$, $\binom{16}{5}$, $\binom{17}{5}$, $\binom{18}{5}$, $\binom{14}{6}$, $\binom{15}{6}$, $\binom{16}{6}$, $\binom{13}{7}$, $\binom{14}{7}$ and $\binom{15}{7}$. Calculating these reveals that $8008 = \binom{16}{6}$ and $8009$ is none of them.

The time complexity is due to stirlings formula for the termination condition:

$$\ln{(2k)!\over (k!)^2} = (2k \ln (2k) - 2k + O(\ln 2k))-2(k\ln k - k+O(\ln k)) \\ = 2k(\ln 2+\ln k) - 2k - 2k\ln k + 2k + O(\ln k) = 2k\ln 2 + O(ln k) < \ln(c)$$

So we have to consider $O(\ln(c))$ values of $k$ and for each of those $k/2$ values of $n$ making it $O((\ln(c))^2)$ binomial coefficients.

Just some comment so far:

By brute force I found the following very likely pattern, by which the sequences $a_j$ and $b_j^2$ can directly be generated. In all cases $m=2$, I had no case with $m \gt 2$ so far, except of course where $b_1 = 1$ - here the exponent $m$ can take any value.

• The sequence of $a_j$ is
  $$ a_j = \{2,9,50,289,...\}_{j=1,2,3,...} $$ and has the iteration formula $$a_{j}\underset{j\ge3}=6a_{j-1}-a_{j-2}-2$$ The question of whether $a_j$ can be prime has at least for each second $a_j$ a simple answer by this formula: if $a_{j-2}$ is even, then also $a_j$. And since $a_1=2$ is even, all $a_j$ with odd $j$ are composite. It seems also that all $a_j$ at even index $j$ are squares, however I didn't try to derive an analogue conclusion for this from the recursion-formula so far. At least, under the assumption, that the partial sequence $c_{j}=a_{2j}=\{9,289,577,...\}$ has indeed only squares $c_j^2$ then we have a recursion $ c_j = 6c_{j-1} - c_{j-2} $ and this would also exclude $a_{2j}$ being prime.
• The sequence $b_j$ is $$\begin{array}{} b_j^2 = \{1,36,1225,41616,...\} \\ b_j = \{1, 6, 35, 204,...\} & \text{with iteration formula} \qquad b_{j}\underset{j\ge3}=6b_{j-1}-b_{j-2} \\ \end{array}$$

First examples by brute force ($a_j \le 20,000,000$): $$ \begin{array} {r|r|rrrll} j & a_j & {a_j \choose 3}=b_j^m & & b_j &\text{^}m \\ \hline 1 & 3 & 1 &=& 1 &\text{^}0 \ldots \infty \\ 2 & 4 & 4 &=& 2 &\text{^}2 \\ 3 &50 & 19600 &=& 140&\text{^}2 \\ \end{array} $$

Interestingly, W|A didn't find the solutions except the trivial one where $b_j=0$