Mark Jason Dominus on 15 Sep 2011 18:58:12 -0700

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: [Philadelphia-pm] 378,000 milkshakes

>  We attempted to figure out how they had arrived at that number.

That is a funny synchronicity.  Just last night I was trying to think
of a good algorithm for solving the following problem: given a
positive integer M, find n > 0 and k > 1 such that M = n choose k =
n!/k!(n-k)!, or determine that no such n and k exist.

The obvious brute-force search algorithm is O(sqrt(M)), which is not
efficient; it should be O(p(log M)) for some polynomial p.

Philadelphia-pm mailing list