title: Sum of digits of a factorial
body: <p><strong><a href="http://acm.uva.es/p/v102/10220.html" rel="noreferrer">Link to the original problem</a></strong></p>
  
  <p>It's not a homework question. I just thought that someone might know a real solution to this problem.</p>
  
  <p>I was on a programming contest back in 2004, and there was this problem:</p>
  
  <blockquote>
    <p>Given n, find sum of digits of n!. n can be from 0 to 10000. Time limit: 1 second. I think there was up to 100 numbers for each test set.</p>
  </blockquote>
  
  <p>My solution was pretty fast but not fast enough, so I just let it run for some time. It built an array of pre-calculated values which I could use in my code. It was a hack, but it worked.</p>
  
  <p>But there was a guy, who solved this problem with about 10 lines of code and it would give an answer in no time. I believe it was some sort of dynamic programming, or something from number theory. We were 16 at that time so it should not be a "rocket science". </p>
  
  <p>Does anyone know what kind of an algorithm he could use?</p>
  
  <p><strong>EDIT</strong>: I'm sorry if I didn't made the question clear. As mquander said, there should be a clever solution, without bugnum, with just plain Pascal code, couple of loops, O(n<sup>2</sup>) or something like that. 1 second is not a constraint anymore.</p>
  
  <p>I found <a href="http://research.att.com/~njas/sequences/A004152" rel="noreferrer">here</a> that if n > 5, then 9 divides sum of digits of a factorial. We also can find how many zeros are there at the end of the number. Can we use that?</p>
  
  <p>Ok, another problem from programming contest from Russia. Given 1 &lt;= N &lt;= 2 000 000 000, output N! mod (N+1). Is that somehow related?</p>