How to calculate a Bell number (Bell[n] mod 95041567) quickly enough?
Here n maybe very big as 2^31.
Bell number is http://oeis.org/A000110
Asked
Active
Viewed 428 times
2
smartc
- 21
1 Answers
1
Wikipedia (https://en.wikipedia.org/wiki/Bell_number) states Touchard's congruence for a prime power $p^m$ as $$B_{p^m + n} = m B_n + B_{n+1} \pmod{p}$$ Using this and the Chinese remainder theorem you should be able to calculate the numbers pretty quickly.
More details: One straightforward way is to take $m=1$ in the congruence. Then we are left with the linear recurrence relation $B_{p+n} = B_n + B_{n+1}$. This can be solved efficiently by transforming it into a matrix and using exponentiation by squaring (https://en.wikipedia.org/wiki/Exponentiation_by_squaring). For example: Let $p=5$, then $$\begin{pmatrix} B_{n+1} \\ B_{n+2} \\ B_{n+3} \\ B_{n+4} \\ B_{n+5} \end{pmatrix}=\begin{pmatrix} 0 & 1 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0& 1 & 0 \\0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} B_n \\ B_{n+1} \\ B_{n+2} \\ B_{n+3} \\ B_{n+4} \end{pmatrix}.$$ To calculate $B_n \pmod{5}$ for some big $n$ just raise the matrix in the middle to the $n$th power, multiply by $\begin{pmatrix} B_0 & B_1 & B_2 & B_3 & B_4 \end{pmatrix}^T$ and look at the first entry in the resulting vector.
J. J.
- 9,432
-
good idea,I'll try to think about it ,thank you! – smartc Sep 28 '13 at 08:50
-
In your case the largest prime factor is $p=47$. The above method requires about $O(p^3 \log n)$ operations, so should be doable. – J. J. Sep 28 '13 at 09:18