Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Is this related to Project Euler #330? –  Sasha Jan 1 '12 at 18:27
1  
@asd: If $n\ge p$ then one of the summands is $\frac{1}{p!}$ and $p!\equiv 0 \pmod p$. Also: -1 for asking a Project Euler problem without disclosing it as such. –  Henning Makholm Jan 1 '12 at 18:31
1  
Copy-pasting solutions found on the internet is even worse. That doesn't mean that asking us to help you cheat at PE is appropriate (the fact that you're the only one ultimately being harmed by your cheating does not make it any less so, and does not make it an appropriate use of our time to help you cheat). –  Henning Makholm Jan 1 '12 at 18:59
1  
@HenningMakholm: explain how is this cheating. I spent whole day on these equations (I come up with them myself) trying to reduce them to something simpler, but failed. I'm asking for help regarding the sum $A(n)+B(n)$ because there is a chance, that the sum might be easier to calculate than $A(n)$, $B(n)$ individually. Do you consider the other question I linked to be cheating too? What I'm supposed to do if I'm unable to solve a problem, but I'm interested in the solution? –  asd Jan 1 '12 at 19:08
4  
The discussion on meta is at meta.math.stackexchange.com/questions/1090/… –  Gerry Myerson Jan 1 '12 at 19:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.