Is there an efficient way to calculate last digits of this sum?

Question

Is there a more efficient way to find the last digits of the following sum for any $n$?

$1 + n + n(n-1) + n(n-1)(n-2) + ... + \frac{n}{2!} + n!$

The method I currently use to find the last $d$ digits of the sum is as follows:

Let $M$ be $n \bmod 10^d$, or $n \bmod 10^d +10^d$ if $n \bmod 10^d < 5\times d$, since an additional step would affect the result if the latter is true. Evaluate $1 + M + M (M-1)$, then add $M(M-1)(M-2)$, and continue until the number of desired digits stabilize.

This can be done quickly for a small number of digits, but for, say, 20 digits, it would be very time-consuming. Is there a way to program this in Mathematica? As far as I'm sure, this would require a loop that references the number of iterations that have been looped, which the Nest function doesn't do.

Answer 1

There is some undocumented functionality in Mathematica that allows you to work with a factored representation of integers, encapsulated as the object Internal`FactoredNumber[]. This has associated operators such as Internal`FactoredNumberTimes[] and Internal`FactoredNumberPlus[] that can be used on it, as well as the conversion functions Internal`ToFactoredNumber[], Internal`FromFactoredNumber[], and, most importantly for our purposes, Internal`FromFactoredNumberMod[].

Applied to this problem, we can use these operations along with Fold[]/FoldList[]:

With[{n = 20, m = 1*^5}, 
    Internal`FromFactoredNumberMod[Fold[Internal`FactoredNumberPlus, 1, 
                                        FoldList[Internal`FactoredNumberTimes, 
                                                 Internal`ToFactoredNumber /@
                                                 Range[n, 2, -1]]], m]]
   40001

Compare this with

With[{n = 20, m = 1*^5}, 
     Mod[Sum[FactorialPower[n, k], {k, 0, n - 1}], m]]
   40001

Answer 2

Maybe I'm stating the obvious, but there's a direct way of calculating this sum, expressed in terms of an incomplete gamma function:

f[n_] = Sum[n!/k!, {k, 0, n}] // FullSimplify
(*    E * Gamma[n+1, 1]    *)

Computing the last four digits, for example, directly (without explicit summing):

Mod[f[1234], 10^4]
(*    7685    *)