There's an excellent algorithm. Constant time. Print "Yes." Did you want to restrict the question more, perhaps? On Fri, Jan 6, 2017 at 4:30 PM, Dan Asimov <dasimov@earthlink.net> wrote:

Suppose we are given the prime factorization of a rather large integer Q.

Is there a good algorithm for determining from this whether the number Q is a binomial coefficient?

I.e., whether there exist positive integers k < n such that

Q = n! / (k! (n-k)!)

.

—Dan

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --

I assume you mean to decide if Q = (n choose k) for some k, n with 1 < k < n. And by "good algorithm", I assume you mean runtime bounded by time polynomial in Q. Even more is true: not only can you tell whether this is solvable, but you can also list all (n,k) pairs, in polynomial time. And you don't need the prime factorization of Q. We can assume in (n choose k) that n >= 2k; if not replace k by n-k. Then Q = (n choose k) >= (2k choose k) ~ 4^k/sqrt(Pi*k) So k is clearly bounded above by c log_2 Q for some small c around 2, so we can simply try k = 2, 3, ..., c log_2 Q and then use binary search to solve Q = (n choose k) for n, for each individual k. This would make a nice first exercise for a course in algorithmic number theory. But perhaps you mean that Q is given in compressed form as p_1^{e_1} ... p_j^{e_j} with p_1 < .... < p_j and you want to do it time polynomial in the logs of all p_i and e_i? In that case more work is needed. First, unless k is relatively small, n will be between p_j and the next prime after p_j. Assuming Cramer's conjecture, this restricts n to a relatively small range, something like [p_j, p_j + (log p_j)^2]. So we can simply test each n in this range and determine the possible k using numerical estimates on the logs. Finally, we can get the prime factorization of (n choose k) for this n and this k, using Legendre's formula and compare to the given list. I think this should work. On 1/6/17 7:30 PM, Dan Asimov wrote:

Suppose we are given the prime factorization of a rather large integer Q.

Is there a good algorithm for determining from this whether the number Q is a binomial coefficient?

I.e., whether there exist positive integers k < n such that

Q = n! / (k! (n-k)!)

.

—Dan

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun