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 2


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, 
                                                 Internal`ToFactoredNumber /@
                                                 Range[n, 2, -1]]], m]]

Compare this with

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.