%#% Los últimos dígitos de la #% de una suma

Question

¿Qué es una eficiente manera (no uso ningún programa de ordenador y tal) para encontrar los últimos $m$ dígitos de algún aspecto terrible suma, por ejemplo, no sé $$1^{1000}+2^{1000}+3^{1000}+\ldots+(10^{1000})^{1000}?$$ Y digamos que también se $m=1000$. Creo que sé cómo abordar este problema, pero parece muy difícil (algo casi imposible) y me gustaría encontrar algo "bonito", si eso es aún posible. De cualquier manera es probablemente requiere algo de aritmética modular.

Muchas gracias!

Answer 1

No hay un "one-size-fits-all" algoritmo general, pero hay un par de principios que pueden ayudar. Aquí están algunos (por favor, siéntase libre de añadir más en los comentarios):

1. Cuando se trata de un módulo como $10^m$, puede ayudar a considerar por separado en su primer factores de potencia, en este caso $2^m$$5^m$, y, a continuación, utilizar el Teorema del Resto Chino para combinarlos.
2. El teorema de Euler: si $\gcd(a,n) = 1$, $a^{\phi(n)} \equiv 1 \mod n$ donde $\phi$ es de Euler totient función.
3. Repetición: $k^x \equiv j^x \mod n$ si $k \equiv j \mod n$. Por lo tanto si $m$ es un múltiplo de a $n$, decir $m = c n$,$\sum_{k=1}^m k^x \equiv c \sum_{j=1}^n j^x \mod n$.
4. Reordenamiento: si $\gcd(n,a) = 1$, luego $$\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$$ por lo $$(1-a^x) \sum_{k=1}^n k^x \equiv 0 \mod n $$ Así, si no es $a$ tal que $a$ $a^x-1$ son coprime a $n$, obtenemos $\sum_{k=1}^n k^x \equiv 0 \mod n$.
5. Faulhaber la fórmula que expresa el $\sum_{k=1}^m k^x$ como un polinomio en $m$ grado $x+1$, con término constante $0$. Por supuesto, tenemos que ser cuidadosos en el uso de este con aritmética modular, debido a que los coeficientes son números racionales.

Por cierto, en el caso que nos ocupa, el uso de Faulhaber la fórmula podemos resolver el problema: $$\sum_{j=1}^{10^{1000}} j^{1000} \equiv 3 \times 10^{999} \mod 10^{1000}$$

EDITAR: Faulhaber expresa $\sum_{j=1}^{10^{1000}} j^{1000}$ como un polinomio en $n = 10^{1000}$ $502$ cero términos, pero ninguno de los denominadores son divisibles por $2^2$ o $5^2$, tan sólo el término en $n^1$ tiene una oportunidad de ser distinto de cero mod $n$: este término es $B_{1000} n$ donde $B_{1000}$ $1000$'th número de Bernoulli. El resultado es $10^{1000} B_{1000} \mod 10^{1000} = 3 \times 10^{999}$.

Answer 2

No hay ningún algoritmo general. Usted tiene que encontrar un ingenioso enfoque basado en el problema en particular en la mano, por ejemplo, mediante la observación de algunas propiedades de los términos en la suma.

Esto me recuerda Proyecto de Euler. Hay muchos problemas que hay que pedir el último $m$ dígitos de algunos de los grandes de la suma. Yo creo que lo hacen debido a que la razón: ya que no hay algoritmo general, si usted encuentra la última $m$ dígitos, lo que significa que en realidad resuelto el problema, encontrar una manera de calcular la suma. En lugar de pedir a usted para toda la gran suma (que es una cadena grande), se les pedirá que ingrese los últimos $m$ dígitos. Si usted proporciona la correcta últimos $m$ dígitos, para ellos si hay suficiente evidencia de que has resuelto el problema.