Números especiales

propuesto por josejuan

Un número es especial cuando el número de números mayores que 1 y menores o iguales a él mismo que contienen algún dígito con uno es el mismo que aquellos que no contienen ningún dígito 1.

Enunciado
Un número es especial cuando el número de números mayores que 1 y menores o iguales a él mismo que contienen algún dígito con uno es el mismo que aquellos que no contienen ningún dígito 1.

Por ejemplo para n=1 sólo hay un número que contenga el dígito 1 y ninguno que no lo contenga, por lo que el 1 no es especial.

Para n=2 tenemos que el 1 sí contiene el dígito 1 y el 2 no lo contiene, tenemos entonces 1 número igual o menor que 2 que sí lo contiene y un número igual o menor que 2 que no lo contiene, por tanto el 2 es especial.

Para n=16 tenemos que los números iguales o menores que él son (divididos por tener o no el dígito 1)

1 10 11 12 13 14 15 16
2 3 4 5 6 7 8 9

por tanto el 16 es especial.

Los primeros especiales son:
	2, 16, 24, 160, 270, 272, 1456, 3398, 3418, 3420


En principio no puede haber especiales por encima de 10^22, una (¿correcta?) demostración podría ser:

Si x(n) es el número de números con 1 desde el 1 hasta 10^n-1 (1..999) es

x(1) = 1
x(n) = 10^(n-1) + 9 x(n-1)

Desarrollando

x(1)= 1
x(2)= 10 + 9
x(3)= 10² + 9 10 + 81
x(4)= 10³ + 9 10² + 81 10 + 729
x(5)= 10⁴ + 9 10³ + 81 10² + 729 10 + 6561
...
x(n) = 10^n - 9^n

Si y(n) es el número de números sin 1 desde 1 hasta 10^n-1 (1..999) es

y(n) = 10^n - 1 - x(n) = 9^n - 1

Como las dos son estrictamente crecientes, en

x(n) - y(n+1)

ya no habrá suficientes "sin 1" para igualar a los "con 1" exactamente para ser

(n-1) ln 10 = n ln 9

es n=21.854, por ya no hay especiales por encima de 10^22.

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

4 Soluciones

Dar mi solución

Dar mi solución