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
    Do you consider the $n!\sum_{k=1}^n\frac{1}{k!}$ term to vanish when $n\ge$ the modulus (even though there's a $1/0$ in there)?2012-01-01
  • 0
    @HenningMakholm: $1/0$? This term is always an integer.2012-01-01
  • 2
    Is this related to [Project Euler #330](http://projecteuler.net/problem=330)?2012-01-01
  • 0
    @Sasha: yes, that's the sum that needs to be computed.2012-01-01
  • 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.2012-01-01
  • 0
    Oh, I see, you mean $n!\sum_k\frac{1}{k!} = \sum_k\frac{n!}{k!}$ where the summands are integers.2012-01-01
  • 0
    @HenningMakholm: is it forbidden to ask about project euler questions? How is asking for help worse than copy&pasting solutions found on the Internet? As for your $1/0$ remark: consider this term as expanded ($n!$ multiplied by everything inside the sum).2012-01-01
  • 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).2012-01-01
  • 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?2012-01-01
  • 1
    If you really think your behavior is acceptable, then I wonder why you chose not to tell where you got the problem from.2012-01-01
  • 1
    @HenningMakholm: I didn't link to the question, because I didn't knew I'll be violation some kind of math.SE rule. Again, if I wanted to "cheat" I'd find the solution on the internet. Instead, I showed effort and asked for help in understanding the solution. Apparently that's unacceptable and I should just kill myself, not being able to solve this problem. Can you answer my other questions?2012-01-01
  • 1
    It's not a m.se rule, it's a Project Euler rule. This was discussed on the meta site here (or maybe on MathOverflow, but I think it was here), and PE left no doubt as to the disapproval of seeking help here.2012-01-01
  • 4
    The discussion on meta is at http://meta.math.stackexchange.com/questions/1090/re-project-euler-questions2012-01-01
  • 0
    Modulo any prime $\le n$ $A$ and $B$ are mostly the same (chuck the $n!$).2013-05-08

0 Answers 0