# 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$? –  Henry Oct 5 '11 at 18:40
0 <= n, k <= 100. –  ricola86 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. –  ricola86 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. –  Quixotic Oct 7 '11 at 18:20
@FoolForMath: Good idea. I have added a caveat to my answer. –  robjohn Oct 7 '11 at 19:40
show 1 more comment

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 :(. –  ricola86 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.