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

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.

## 2 Answers

There is some undocumented functionality in Mathematica that allows you to work with a factored representation of integers, encapsulated as the object InternalFactoredNumber[]. This has associated operators such as InternalFactoredNumberTimes[] and InternalFactoredNumberPlus[] that can be used on it, as well as the conversion functions InternalToFactoredNumber[], InternalFromFactoredNumber[], and, most importantly for our purposes, InternalFromFactoredNumberMod[].

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

With[{n = 20, m = 1*^5},
InternalFromFactoredNumberMod[Fold[InternalFactoredNumberPlus, 1,
FoldList[InternalFactoredNumberTimes,
InternalToFactoredNumber /@
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


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    *)