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 ?
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 ?
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=rk∗10k+rk−1∗10k−1+...+r0∗100≡[rk,rk−1,...,r0] 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)=k∑j=0(rj∑i=0(10jδi−1,d)+rjE(j)+δrj,d(n[j:]+1))
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∗10j−1
Escribiendo esto en mathematica (y comprobando ( f(1,n)=n da el siguiente resultado de 199981 ).
NOTA : Esto se puede generalizar aún más a cualquier base B sustituyendo las apariciones de 10k con Bk
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 10k−1 hay k∗10k−1 apariciones de cualquier dígito en ese rango.
Esto motiva mi definición de la función
E(j)=j∗10j−1
Sin embargo, es poco probable que el número dado sea tan bonito como 10k−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 rjE(j) término). Sin embargo, en el rango 1000-1999 el dígito uno aparece un 1000 más (o 10j ) veces, este término adicional sólo se produce si rj 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 ∑rji=1(10jδ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 δrj,d(n[j:]+1) plazo.
Creo que tengo el principio de una idea para resolver esto. Podemos empezar observando que f(10n+1−1)=1+10n+10×f(10n−1) porque cuando se enumeran todos los números del 1 al 10n+1 ...tienes: 1... 10n−1 , 10n ,..., 1999...99, 20...00,... 10n+1−1 . de 10n a 1999...99 puedes ver 10n+f(n)+1 el dígito "1", y de 20...00 a 10n+1−1 se obtiene 9×f(10n−1) el dígito '1'. Así que vamos a llamar a un=10n−1 y vn=f(un) .
Puedo ver que u9>v9 y u10<v10 por lo que la respuesta debe ser intermedia (o al menos menor que 1010−1 .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.