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 coefficient 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 coefficient.
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 coefficients modulo a prime might be productive.
I think you will essentially have to factor the integer, or at least find 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 find k with a few trials.
Conversely, if you CAN write the integer as a binomial coefficient, 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 coefficient 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 finite 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 first 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 refine this to find 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 find 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;