¿Existe alguna fórmula general para calcular la suma de dígitos de número de $1$ a $n$ ?
$n < 10^9$
Respuestas
¿Demasiados anuncios?
Para facilitar el recuento consideraré la suma de los dígitos de todos los enteros de $0$ a $n$ - claramente esto no cambia la respuesta. Denotemos esta suma por $D(n)$ .
Editar . Aquí hay una respuesta mejorada. Como un par de personas pensaron que mi respuesta anterior valía la pena de ser votada, no la he borrado, ver abajo.
Escribe $n=10q+r$ donde $q\ge0$ y $0\le r\le 9$ . Los dígitos de todos los números de $0$ a $n$ puede dividirse en los cuatro conjuntos siguientes:
- los dígitos de las unidades de los números de $0$ a $10q-1$ ;
- los otros dígitos de los números de $0$ a $10q-1$ ;
- los dígitos de las unidades de los números de $10q$ a $10q+r$ ;
- los otros dígitos de los números de $10q$ a $10q+r$ .
El primer grupo está formado por los dígitos de $0$ a $9$ repetido $q$ veces cada uno. La segunda consiste en los dígitos de los números $0,1,\ldots,q-1$ repetido $10$ veces cada uno. La tercera consiste en los dígitos $0,1,\ldots,r$ . El cuarto consiste en los dígitos de $q$ repetido $r+1$ tiempos. Así que si escribimos $d(q)$ para la suma de los dígitos de $q$ obtenemos el fórmula recursiva $$D(10q+r)=45q+10D(q-1)+\frac{r(r+1)}{2}+(r+1)d(q)\ .$$
Aquí está mi respuesta anterior . Primero considera todos los números de $0$ a $10^k-1$ . Hay $10^k$ tales números, cada uno con $k$ dígitos si permitimos los ceros a la izquierda. Esto da como resultado $k10^k$ dígitos en total, y se distribuyen por igual entre los $10$ posibilidades, $k10^{k-1}$ de cada dígito. Así que $$D(10^k-1)=k10^{k-1}(0+1+\cdots+9)=(45k)10^{k-1}\ .$$
Considerar a continuación $n=a10^k-1$ , donde $1\le a\le9$ . Todo lo anterior ocurre $a$ veces; también están los dígitos iniciales $0,1,\ldots,a-1$ que se produce $10^k$ veces cada uno. Así que $$D(a10^k-1)=(45ak)10^{k-1}+(1+\cdots+(a-1))10^k=(45ak)10^{k-1}+\frac{a(a-1)}{2}10^k\ .$$
Por último, considere $n=a10^k+b$ con $1\le a\le 9$ y $0\le b<10^k$ . La suma de los dígitos incluye todo lo anterior; y todos los números de $0$ a $b$ con un dígito inicial $a$ prepagada. Así obtenemos un fórmula recursiva que quizás en la práctica sea la forma más fácil de calcular $D(n)$ : si $1\le a\le 9$ y $0\le b<10^k$ entonces $$D(a10^k+b)=(45ak)10^{k-1}+\frac{a(a-1)}{2}10^k+a(b+1)+D(b)\ .$$
kerchee
Puntos
66
No hay ninguna función racional (fórmula que implique sólo $+$ , $-$ , $\cdot$ y $/$ ) que hace esto. De hecho, para $n = 100...00$ tenemos $f(n+1)=f(n)+2$ . Por lo tanto, la función $f(x+1)-f(x)$ que también es racional, toma el valor $2$ un número infinito de veces, pero una función racional no puede tomar el mismo valor un número infinito de veces a menos que sea constante, y $f(x+1)-f(x)$ no es claramente constante.
user30382
Puntos
48
Dejemos que $n=\sum_{i=0}^k10^i\cdot n_i$ Así pues, el $n_i$ son los dígitos decimales de $n$ . Sea $[x]$ denotan la parte entera de $x$ . Entonces la suma $S$ de todos los dígitos de todos los enteros hasta $n$ es
$$S=\sum_{i=0}^kn_i\cdot\left(n+1-10^i\cdot\left[\frac{n}{10^i}\right]\right)+\frac{1}{2}\cdot\sum_{i=0}^k10^in_i(n_i-1)+45\cdot\sum_{i=0}^k\left[\frac{n}{10^{i+1}}\right].$$
Como me temía, es muy feo. A partir de la edición de su pregunta (que dice $n<10^9$ ) Supongo que es una cuestión de programación. Programar un bucle es mucho más agradable para números tan pequeños.
Tad
Puntos
188
En realidad he conseguido encontrar, mediante varios cálculos, una fórmula recursiva general para la suma de los dígitos fom $0$ a $n$ que denoté por $Dg(n)$ . Sin embargo, $n$ debe escribirse utilizando la notación posicional, es decir $10^z\alpha+10^{z-1}\beta+10^{z-2}\gamma+...+\omega$ , donde $\alpha,\beta,\gamma,...,\omega$ son los dígitos de $n$ en orden de izquierda a derecha, y $z+1$ corresponde al número de dígitos de n. Dicho esto, la fórmula es $$ Dg(10^z\alpha+10^{z-1}\beta+10^{z-2}\gamma+\cdots+\omega)= $$ $$ =\alpha(45\times z\times 10^{z-1}+1+10^{z-1}\beta+10^{z-2}\gamma+\cdots+\omega)++Dg(10^{z-1}\beta+10^{z-2}\gamma+\cdots+\omega)+10^z\times T_{\alpha-1} $$ donde $T_n$ es el enésimo número triangular.
El cálculo termina cuando la recursión llega a $Dg(\omega)$ que es igual a $\frac{\omega(\omega+1)}{2}$ .
