# calculating n choose k mod one million

I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula $${n\choose k} = {n\choose k-1} \frac{n-k+1}{k}$$ so I don't have to calculate huge factorials. Is there any way to use this formula and just keep track of the last 6 digits. Could you compute the next k, with only knowing the some of the last digits.
I understand this is a lot to ask, so all I ask is a point in the right direction. Maths is by far not my strongest subject.

• Can you give us an idea of the scale of $n$ or $k$? Oct 5 '11 at 18:40
• 0 <= n, k <= 100. Oct 5 '11 at 18:43

You might also want to use $\binom{n}{k}=\binom{n}{n-k}$ to reduce the case where $k>n/2$.

Using $\binom{n}{k} = \binom{n}{k-1} \frac{n-k+1}{k}$ mod one million has a problem when $(k,10)\not=1$. Such $k$ are zero divisors mod one million, so you cannot divide by $k$ mod one million and get a meaningful result.

However, you can count the number of factors of $p$ that are in $\binom{n}{k}$ for prime $p$. Let $s_p(n)$ be the sum of the base $p$ digits of $n$. Then, the number of factors of $p$ in $\binom{n}{k}$ is $(s_p(k)+s_p(n-k)-s_p(n))/(p-1)$. Thus, instead of multiplying by $n-k+1$ and dividing by $k$, multiply by $n-k+1$ with all factors of $2$ and $5$ removed and divide by $k$ with all factors of $2$ and $5$ removed. At the end, multiply by the number of factors of $2$ and $5$ computed above.

For example, let's compute $\binom{97}{89}=\binom{97}{8}$.

Here are $97$, $8$, and $89$ in base $2$ and $5$ followed by their sum of digits: $$97=1100001_2(3)=342_5(9)$$ $$8=1000_2(1)=13_5(4)$$ $$89=1011001_2(4)=324_5(9)$$ Therefore, the number of factors of $2$ in $\binom{97}{89}$ is $(1+4-3)/(2-1)=2$, and the number of factors of $5$ is $(4+9-9)/(5-1)=1$. Therefore, mod one million,

\begin{align} \binom{97}{8} &=\frac{97}{1}\frac{96/32}{2/2}\frac{95/5}{3}\frac{94/2}{4/4}\frac{93}{5/5}\frac{92/4}{6/2}\frac{91}{7}\frac{90/10}{8/8}\times2^2\times5^1\\ &=\frac{97}{1}\frac{3}{1}\frac{19}{3}\frac{47}{1}\frac{93}{1}\frac{23}{3}\frac{91}{7}\frac{9}{1}\times4\times5\\ &=010441\times20\\ &=208820 \end{align} Everything is good above since we can divide by $3$ and $7$ mod one million.

Caveat: Remember that modular division is quite different than standard division of integers, rationals, and reals. It requires solving a Diophantine equation which usually involves the Euclidean algorithm. For example, $1/7=3\pmod{10}$ because $3\times7=1\pmod{10}$.

• I see after finally posting that most of what I say is covered in the links supplied by Sasha. I hope the example gives it some added value.
– robjohn
Oct 5 '11 at 21:46
• this is good stuff thanks. It's well explained and I've surprised myself in being able to understand it. +1. Oct 7 '11 at 15:14
• @ricola86: as long as you remember that division $\pmod{m}$ is quite different than normal division. It requires solving a diophantine equation and usually involves the Euclidean algorithm. E.g. $1/7=3\pmod{10}$.
– robjohn
Oct 7 '11 at 15:38
• +1,Nice explanation,you may also like to add the final comment in the actual answer as well. Oct 7 '11 at 18:20
• @FoolForMath: Good idea. I have added a caveat to my answer.
– robjohn
Oct 7 '11 at 19:40

You may find the following page of interest.

Much of the math behind it is also discussed in this post at math.SE

• Nice link thanks, It seems I can't upvote with a low reputation :(. Oct 5 '11 at 19:10
• @ricola86: I upvoted for you. Oops, now I can't upvote for myself! :-)
– robjohn
Oct 5 '11 at 22:22

In terms of factorials, probably not.

Use the recurrence ${n \choose k} = {n \choose k-1} + {n-1 \choose k-1}$ and just work mod $10^6$.

Alternatively you can work mod $2^6$ and mod $5^6$ and combine the two results using the Chinese Remainder Theorem. There seem to be interesting patterns in the binomial coefficients mod prime powers but I don't know if there are actually formulas. This is probably more trouble than it's worth, though.

I remember solving SPOJ MARBLES which is actually finding $\binom{n}{k}$,constraints there are also similar to this problem in hand.

Last January this same problem (with much more difficult constraints) features in Codechef's January cookfoff.You may like to check the editorial which explains the algorithm along with the implementation.

• This is exactly what I was looking for, thanks alot. Funnily enough, it's a codechef problem I'm working on. Oct 5 '11 at 19:11
• @ricola86:Aha,glad to help!:-)I didn't practise in codechef anymore,but I guess you are not asking help for any current problem-set?! ;-) Oct 5 '11 at 19:16
• errmm no, I wouldnt dream of it. Oct 5 '11 at 19:24
• @ricola86:Alright! :) Oct 5 '11 at 19:27