4
$\begingroup$

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 \mod 10^d$, or $n \mod 10^d +10^d$ if $n \mod 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.

$\endgroup$
9
$\begingroup$

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
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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