Número de apariciones del dígito 1 en los números del 0 al n

Question

Tenemos una función:

$f(n)$ = número de apariciones de la cifra $1$ en los números de $0$ a $n$ .

Ejemplo: $f(12) = 5$

Es evidente que $f(1)=1.$

Pregunta: ¿Cuál es el siguiente número para el que $f(n) = n$ ?

Answer 1

Bien, esto es sencillo de hacer con Mathematica.

For[i = 0; j = 0, i <= 200000,
 i++, j += (Plus @@ Cases[IntegerDigits[i], 1]); If[j == i, Print[i]]]

El resultado es

0,1,199981,199982,199983,...,199990,200000

Por lo tanto, el número que busca tiene que ser 199981.

Answer 2

Así que desenterré mis notas sobre este problema (para los interesados esto es proyecto euler problema # 156 ) Existe una forma analítica para la solución de este problema (pero, por desgracia, incluso la forma analítica es demasiado lenta para resolver el gran problema, que requiere encontrar TODOS los números que satisfagan esta condición para TODOS los dígitos del 1 al 9). Enunciaré mi resultado primero (para evitar ocultarlo en el texto) y daré una explicación después.

SOLUCIÓN

Definir un representación de la lista de un número $n$ para ser (siguiendo una notación que tomé prestada de las fracciones continuas)

$$n = r_k*10^k + r_{k-1}*10^{k-1} + ... + r_0*10^0 \equiv [r_k,r_{k-1},...,r_0]$$ La función $f(d,n)$ que da el número de apariciones de un dígito $d$ hasta el número $n$ viene dada por $$f(d,n) = \sum_{j=0}^k\left(\sum_{i=0}^{r_j} (10^j\delta_{i-1,d})+ r_jE(j) +\delta_{r_j,d}(n[j:]+1)\right)$$

donde la notación $n[j:]$ se utiliza para significar el número formado por el último $j$ dígitos (por ejemplo, para $n=1234=[1,2,3,4]$ , $n[1] = 4$ , $n[3] = 234$ ) y $E(j) = j*10^{j-1}$

Escribiendo esto en mathematica (y comprobando ( $f(1,n) = n$ da el siguiente resultado de $\mathbf{199981}$ ).

NOTA : Esto se puede generalizar aún más a cualquier base $B$ sustituyendo las apariciones de $10^k$ con $B^k$

MOTIVACIÓN

Primero observa que en el número 0-9 cualquier dígito aparece sólo 1 vez.

En los números 0-99 cualquier dígito aparece 10 + 10 veces (10 veces como dígito de la unidad y 10 veces en el rango x0-x9)

En los números 0-999 cualquier dígito aparece 20*10+100 = 300 veces (20 veces en cada rango de 100+ más 100 en el rango x00-x99)

No es difícil demostrar que este patrón continúa, para cualquier número dado como $10^k-1$ hay $k*10^{k-1}$ apariciones de cualquier dígito en ese rango.

Esto motiva mi definición de la función

$$E(j) = j*10^{j-1}$$

Sin embargo, es poco probable que el número dado sea tan bonito como $10^k-1$ tenemos que aprender una forma inteligente de sumar las partes de ese rango. Para un número (dado en la notación anterior) como $[4,0,0,0]$ . Vemos que la gama $0-999$ se produce 4 veces ( $0-999$ , $1000-1999$ , $2000-2999$ , $3000-3999$ . Así que nos quedamos con $4*E(3) = 1200$ ocurrencias del dígito $1$ (esto motiva la $r_jE(j)$ término). Sin embargo, en el rango 1000-1999 el dígito uno aparece un 1000 más (o $10^j$ ) veces, este término adicional sólo se produce si $r_j$ es mayor que el dígito que estamos sumando (por ejemplo, si estamos sumando ocurrencias del dígito $9$ la respuesta sería 1200 y no 2200), la mejor forma que se me ocurrió para expresar analíticamente esta afirmación condicional fue con la suma $\sum_{i=1}^{r_j}(10^j\delta_{i-1,d})$

Calculando un número como $[4,1,2,4]$ no es mucho más difícil, simplemente iteramos sobre la secuencia $[4,0,0,0]$ , $[3,0,0]$ , $[2,0]$ , $[4]$ siguiendo la fórmula del párrafo anterior. Sin embargo, el método anterior contará mal porque ignora la aparición extra del dígito $1$ en el rango $4100-4124$ . Así que en cada paso de la iteración tenemos que asegurarnos de que no hay colas que se nos olvide contar, lo que motiva el $\delta_{r_j,d}(n[j:]+1)$ plazo.

Answer 3

Creo que tengo el principio de una idea para resolver esto. Podemos empezar observando que $f(10^{n+1}-1)= 1+10^n+10\times f(10^n-1)$ porque cuando se enumeran todos los números del 1 al $10^{n+1}$ ...tienes: 1... $10^n-1$ , $10^n$ ,..., 1999...99, 20...00,... $10^{n+1}-1$ . de $10^n$ a 1999...99 puedes ver $10^n+f(n)+1$ el dígito "1", y de 20...00 a $10^{n+1}-1$ se obtiene $9\times f(10^n-1)$ el dígito '1'. Así que vamos a llamar a $u_n=10^n-1$ y $v_n=f(u_n)$ .

Puedo ver que $u_9 >v_9$ y $u_{10} < v_{10}$ por lo que la respuesta debe ser intermedia (o al menos menor que $10^{10}-1$ .