I've been working on this problem computing $n \choose r$ for large $n$ and $r$, modulo a composite.

I could implement the generalized lucas theorem to handle the prime power case, but I want to understand what I am doing wrong with the following method. The method doesn't always work there must be a flaw in the logic.

To compute the numerator of the factorial representation of $n \choose r$ mod $27$ (say), I create the residue system mod $27$, then calculate each exponent in the residue system, based on how many times that residue would occur in the interval $(\max(r,n-r), n)$. This product of integers in this interval would give the number of distinct ways of choosing $\max(r,n-r)$ objects from $n$ objects respecting order. At this stage I do not calculate this product modulo $27$, since it could go to zero.

Then I calculate the exponents for each member of the class of residues mod $27$, based on how many times that residue would occur in the interval $(1,\min(r,n-r))$. The product of integers in this interval gives the number of rearrangements of $\min(r,n-r)$ distinct objects.

To calculate the quotient of these two numbers I first factor the system of residues. For example, the term $(10^{17})$ in the original sequence would become the two terms : $(2^{17}),(5^{17})$ in the factored sequence. Then with the factored representations of the two sequences for numerator and denominator, I remove from both these sequences the intersection of the sequences, effectively canceling all similar factors.

Finally, to compute the binomial coefficient, I take the product of the numerator sequence and the multiplicative inverse modulo $27$ of the product of the denominator sequence and multiply them together modulo $27$.

The thing that is driving me nuts about this is that it works for some choices of $n$ and $r$, but not for others.

For instance, as a subroutine to calculate the binomial coefficient for $84 \choose 66$ modulo $(11*13*27*37)$, it correctly outputs the value modulo each of these prime powers, and using CRT computes the correct answer of $64269$.

However for the remainder of the binomial coefficient for $91 \choose 63$ divided by the same modulus, the output is correct for all the primes, but fails for $27$. For $27$ it gives the incorrect answer '$3$' instead of the correct answer '$12$'.

In addition, I seem to remember it failing even for prime moduli on other choices of $n$ and $r$.

I have been working on this for around 4 days, and the competition allowed roughly 4 hours for this (so clearly I am not a "sprint" coder), and while I initially didn't want to cheat, I do want to wrap this up. So some kind of insight as to why my logic is flawed and if there is any way to improve it (without using the generalized lucas theorem), I would really appreciate.

I figure my reasoning must be solid, and want to understand what's wrong with it. The ultra correct way of factoring the entire numerator and denominator sequences (instead of just the residue system with calculated exponents), is untenable for large $n$ and $r$. And Generalized Lucas is a solution, but it is not revealing why my current method is broken, which is what I am asking here.

  • $\begingroup$ You can find some good starting points on how to format mathematics on the site here and here. This AMS reference is very useful. If you need to format more advanced things, there are many excellent references on LaTeX on the internet, including StackExchange's own TeX.SE site. $\endgroup$ – Zev Chonoles Feb 4 '13 at 6:14
  • $\begingroup$ Thanks. I should look those up. $\endgroup$ – Cris Stringfellow Feb 4 '13 at 6:15
  • $\begingroup$ My friend wrote an undergraduate paper that is somewhat related to this problem. I hope that it helps you in some way. :) $\endgroup$ – Haskell Curry Feb 4 '13 at 6:32
  • $\begingroup$ Thanks. Derivation of some of the identities. $\endgroup$ – Cris Stringfellow Feb 4 '13 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.