Calculating large Bell number modulo a composite number

Question

I have been trying to solve http://www.javaist.com/rosecode/problem-511-Bell-Numbers-Modulo-Factorial-askyear-2018

It is not an ongoing contest problem.

We can calculate $n$th Bell number modulo a prime number greater than $10^7$ in $O(n)$ arithmetic operations, using this formula $$B_n=\sum_{k=1}^{n}\frac{k^n}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!}$$ We can store the partial inner sum for future use, without calculating again and again. For example $B_{10^7}$ $\text{mod}$ $1000000007$ $=29987405$.

But in the problem the modulus is $30!$, so we can't do modular inverse operations. I tried to reduce the formula to $$B_n=\sum_{k=1}^{n}\frac{k^n!(n-k)}{k!(n-k)!}=\frac{1}{n!}\sum_{k=1}^{n}\binom{n}{k}k^n!(n-k)$$ $!n$ denotes subfactorial function.

I am stuck here. Can anyone help?

Answer 1

As mentioned in the comment, large Bell number modulo factorials can be calculated efficiently using following congruence.

$$\sum_{k=0}^{n}D_{n,k}B_{m+k}\equiv 0\ (\textrm{mod}\ n!)$$ $$D_{n+1,k}=D_{n,k-1}-(n+1)D_{n,k}-nD_{n-1,k}$$ $n \geq 0,k \geq 0$

$D_{0,0}=1$

$D_{n,k}=0,\hspace{5 mm}k>n,k<0$

It takes $O(MN)$ time to calculate $M^{th}$ Bell number modulo $N!$.

Answer 2

For this problem, it's more convenient to use the formula for Bell numbers expressing them as the sum of Stirling numbers of the second kind: $$B_n=\sum_{k=0}^n \left\{ {n \atop k} \right\}.$$ This formula does not involve any divisions and can be evaluated modulo any given $m$, provided that we can compute $n$-th row of Stirling numbers modulo $m$.

Stirling numbers modulo $m$ can be computed row-by-row (hence keeping only two rows in the memory at once) using the recurrence: $$\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}\quad (k>0)$$ with the initial conditions $\left\{{ 0 \atop 0 }\right\} = 1$ and $\left\{{ n \atop 0 }\right\} = \left\{{ 0 \atop n }\right\} = 0$ for any $n>0$.