Processing math: 100%

11 votos

Número de apariciones del dígito 1 en los números del 0 al 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 ?

6voto

Alex Andronov Puntos 178

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.

5voto

Joshka Puntos 141

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=rk10k+rk110k1+...+r0100[rk,rk1,...,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)=kj=0(rji=0(10jδi1,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)=j10j1

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 10k1 hay k10k1 apariciones de cualquier dígito en ese rango.

Esto motiva mi definición de la función

E(j)=j10j1

Sin embargo, es poco probable que el número dado sea tan bonito como 10k1 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 0999 se produce 4 veces ( 0999 , 10001999 , 20002999 , 30003999 . Así que nos quedamos con 4E(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δi1,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 41004124 . 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.

1voto

Frew Puntos 133

Creo que tengo el principio de una idea para resolver esto. Podemos empezar observando que f(10n+11)=1+10n+10×f(10n1) porque cuando se enumeran todos los números del 1 al 10n+1 ...tienes: 1... 10n1 , 10n ,..., 1999...99, 20...00,... 10n+11 . de 10n a 1999...99 puedes ver 10n+f(n)+1 el dígito "1", y de 20...00 a 10n+11 se obtiene 9×f(10n1) el dígito '1'. Así que vamos a llamar a un=10n1 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 10101 .

i-Ciencias.com

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.

Powered by:

X