¿Cuántos ceros hay en los números de $m$ a $n$ ?

Question

Contando ceros

Si escribo las representaciones decimales de todos los números naturales entre e incluyendo $m$ y $n$ , ( $m \leq n$ ), ¿cuántos ceros anotaré? ¿Cómo calcularlo? $m$ y $n$ serán enteros de 32 bits.

Por ejemplo, si $m = 10$ y $n = 11$ la respuesta es $1$ . Pero si $m = 13423$ y $n = 2352352454$ ¿cuál será la respuesta?

Answer 1

Lo más fácil es hacerlo para $1$ a $n$ . Entonces, si quieres $m$ a $n$ restar de $1$ a $m-1$ . Si desea el número de ceros hasta $13423$ es el número hasta $10000$ más el número hasta $3423$ . Subiendo a $10000$ Obsérvese que cada lugar, excepto el $1000$ aporta el mismo número de ceros (¿cuántos?) El $1000$ no son ninguno porque sería un cero a la izquierda, por lo que subir a $10000$ es $3$ lugares tiempos $1000$ = $3000$ . Esto debería sugerir un algoritmo recursivo.

Answer 2

Hay 1 cero (para el último dígito) por cada 10 números, hay 10 ceros adicionales cada 100 números, hay 100 ceros adicionales cada 1000 números...

Esto implicaría que el número de ceros es aproximadamente

$$\sum_{k \geq 1} 10^{k-1}\left\lfloor \frac{n}{10^k} \right\rfloor$$

Pero esta fórmula no es exacta, ya que hay un problema cuando se cuenta $10^k$ ceros en un grupo. La fórmula se convierte en :

$$\sum_{k \geq 1} \left\lbrace \begin{array} .10^{k-1}\left\lfloor \frac{n}{10^k}\right\rfloor & \text{if} & \text{k=1 or the k-th digit is not 0} \\ 10^{k-1}\left(\left\lfloor \frac{n}{10^k}\right\rfloor -1\right) +n+1- 10^k\left\lfloor \frac{n}{10^k}\right\rfloor & \text{if} & \text{the k-th digit is 0 and k is not 1}\\ \end{array}\right.$$

Edición : esta fórmula parece funcionar. La he probado con algunos números con el ordenador