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.

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.

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

> ifactor(B,easy); 4 2 2 (2) (3) (5) (7) (11) (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)

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`

).

binomialfinder:= proc(B) local F,p,q,Q,Q1,n,t,k,B0; F:= ifactors(B,easy)[2]; if hastype(F,name) then error "couldn't easily factor %1",B fi; p:= F[-1,1]; q:= nextprime(p)-1; for n from p to q do Q:= ln(B) + 1/2*ln(2*Pi*n*t*(1-t)) + n*(t*ln(t)+(1-t)*ln(1-t)): Q1:= evalf(subs(t=1/2,Q)); if Q1 > 0.01 then next # B too big elif Q1 > -0.01 then k:= floor(n/2) else k:= round(n*fsolve(Q=0,t=0..1/2)) fi; B0:= binomial(n,k); if B0 >= B then while B0 > B do k:= k - 1; B0:= B0*(k+1)/(n-k); od else while B0 < B do k:= k + 1; if k > n/2 then B0:= infinity else B0:= B0*(k+1)/(n-k); fi od fi; if B0 = B then return [n,k] fi; od; FAIL end;