#### binomial coeﬃcients (11.1.03)

##### Brendan McKay

The following problem has no important application that I know of. It just occurred to me as something that would interest a few people in this group.

Say that a binomial coeﬃcient binomial(n,k) is ”non-trivial” if $$n$$ and $$k$$ are integers such that 2 <= k <= n-2. The problem is to determine if (and how) a given number is a non-trivial binomial coeﬃcient.

For example, if we are given

$$11159690566590580740354583612991667619792058478202676400$$

we would like to quickly recognise that it equals binomial(187,92).

I suspect that considering the theory of binomial coeﬃcients modulo a prime might be productive.

##### Ronald Bruck (14.1.03)

I think you will essentially have to factor the integer, or at least ﬁnd the biggest prime factor of the integer. Your example factors as

2^4 * 3 * 5^2 * 7 * 11^2 * 13 * 17 * 31 * 37 * 53 * 59 * 61 * 97
* 101 * 103 * 107 *109 * 113 * 127 * 131 * 137 * 139 * 149
* 151 * 157 * 163 * 167 * 173 * 179 * 181

and since the next prime after 181 is 191, this means the n must be between 181 and 190, inclusive. Not a big range, and once you know n you can ﬁnd k with a few trials.

Conversely, if you CAN write the integer as a binomial coeﬃcient, you will have reduced the range (and if k is large, quite substantially reduced the range) that n can lie in. So this is essentially a factorization problem.

Note that the number of times a prime p divides a binomial coeﬃcient is $$N(n,p) - N(k,p) - N(k,n-k)$$, where N(n,p) = sum of floor(n/p^i), i = 1 to infinity (really a ﬁnite sum).

Assuming k <= n/2 (which we can surely arrange) this means that all primes p between k and n must appear in the factorization. The longest such list is {97,101,103,107,...,181} for your example, so I would start at k = 97 and work down.

##### Robert Israel (15.1.03)

Given a number like that, you might ﬁrst try to factor it, using the ”easy” option (because if it is binomial(n,k) with n not very large, its prime factors should all be fairly small). In your example, if your number is B, we get

The largest prime factor is 181.

If B = binomial(n,k) with (wlog) k <= n/2, any prime between n-k+1 and $$n$$ inclusive will divide $$B$$. Assuming there are such primes, the most $$n$$ could be is 190 (because 191 is the next prime after 181).

So there aren’t too many possibilities for n. For any given n, we could use Stirling’s approximation to determine k approximately and then quickly reﬁne this to ﬁnd which $$k$$ will make the magnitude of binomial(n,k) close to that of $$B$$. In this case we must have n >= 187, else binomial(n,floor(n/2)) is too small. And checking $$n=187$$, we ﬁnd indeed that $$k=92$$ works.

So here’s my proposed code. It will return the pair [n,k] if successful, an error if it can’t factor $$B$$, or FAIL if it can factor $$B$$ and determines there is no possible [n,k] (or no prime between n-k and n).