Last $m$ digits of a sum

Question

What is an efficent way (not using any computer programs and such) to find last $m$ digits of some terrible looking sum, for example I don't know $$1^{1000}+2^{1000}+3^{1000}+\ldots+(10^{1000})^{1000}?$$ And let's say that also $m=1000$. I think I know how to approach this problem, but it seems very hard (rather near impossible) and I would like to find something "nice", if that is even possible. Either way it probably requires some modular arithmetics.

Thanks a lot!

Answer 1

There is no "one-size-fits-all" general algorithm, but there are a few principles that may help. Here are some (please feel free to add more in comments):

1. When dealing with a modulus such as $10^m$, it may help to look separately at its prime power factors, in this case $2^m$ and $5^m$, and then use the Chinese Remainder Theorem to combine them.
2. Euler's theorem: if $\gcd(a,n) = 1$, then $a^{\phi(n)} \equiv 1 \mod n$, where $\phi$ is Euler's totient function.
3. Repetition: $k^x \equiv j^x \mod n$ if $k \equiv j \mod n$. Thus if $m$ is a multiple of $n$, say $m = c n$, then $\sum_{k=1}^m k^x \equiv c \sum_{j=1}^n j^x \mod n$.
4. Rearrangement: if $\gcd(n,a) = 1$, then $$\sum_{k=1}^n k^x \equiv \sum_{k=1}^n (a k)^x \equiv a^x \sum_{k=1}^n k^x \mod n$$ so $$(1-a^x) \sum_{k=1}^n k^x \equiv 0 \mod n $$ Thus if there is $a$ such that $a$ and $a^x-1$ are coprime to $n$, we get $\sum_{k=1}^n k^x \equiv 0 \mod n$.
5. Faulhaber's formula expresses $\sum_{k=1}^m k^x$ as a polynomial in $m$ of degree $x+1$, with constant term $0$. Of course we need to be careful in using this with modular arithmetic, because the coefficients are rational numbers.

By the way, in the case at hand, using Faulhaber's formula we can solve the problem: $$\sum_{j=1}^{10^{1000}} j^{1000} \equiv 3 \times 10^{999} \mod 10^{1000}$$

EDIT: Faulhaber expresses $\sum_{j=1}^{10^{1000}} j^{1000}$ as a polynomial in $n = 10^{1000}$ with $502$ nonzero terms, but none of the denominators are divisible by $2^2$ or $5^2$, so only the term in $n^1$ has a chance to be nonzero mod $n$: this term is $B_{1000} n$ where $B_{1000}$ is the $1000$'th Bernoulli number. The result is $10^{1000} B_{1000} \mod 10^{1000} = 3 \times 10^{999}$.

Answer 2

There is no general algorithm. You have to find an ingenious approach based on the particular problem at hand e.g. by observing some properties of the terms in the sum.

This reminds me of Project Euler. There are many problems there, which ask for the last $m$ digits of some large sum. I think they do this just because of that reason: since there's no general algorithm, if you found the last $m$ digits, that means you actually solved the problem, you found a way to calculate the sum. Instead of asking you for the whole large sum (which is a large string), they only ask you to input the last $m$ digits. If you provide the correct last $m$ digits, to them this if enough evidence that you solved the problem.