2
$\begingroup$

Let

$A(n)=\sum_{k=0}^{n-1}\binom{n}{k}A(k)+n!,\quad A(0)=1$

$B(n)=\sum_{k=0}^{n-1}\binom{n}{k}B(k)-n!-n!\sum_{k=1}^{n}\frac{1}{k!},\quad B(0)=-1.$

I'm interested in computing $S(n)=A(n)+B(n)$ modulo a prime, for large $n$ quickly. Using these equations directly would be very slow.

This looks very similar to Bell's recurrence, but I was unable to leverage that fact :(. Any ideas how to solve this problem?

Edit:

This is the sum from euler problem 330. Someone already asked about $A(n)$ here.

  • 0
    Modulo any prime $\le n$ $A$ and $B$ are mostly the same (chuck the $n!$).2013-05-08

0 Answers 0