¿Es $2^{16} = 65536$ la única potencia de $2$ que no tiene ningún dígito que sea una potencia de $2$ en base-$10$?

Question

Estaba viendo este video en YouTube donde se menciona (en el minuto 6:26) que $2^{16} = 65536$ no tiene ningún número que sea potencia de $2$ cuando se representa en base-$10$. Luego, él - creo que como broma - dice "Vamos, encuentra otra potencia de $2$ que no tenga un dígito que sea potencia de $2" en ella. ¡Te reto!"

Así que lo hice. :) Escribí este pequeño programa en Python para buscar este tipo de números:

toThePower = 0
possiblyNoPower = True

while True:
    number = str(2**toThePower)
    for digit in number:
        if int(digit) in [1,2,4,8]:
            possiblyNoPower = False
            print('No es ' + number)
            break
    if possiblyNoPower:
        print(number + ' no tiene ningún dígito que sea potencia de 2.')
    toThePower += 1
    possiblyNoPower = True

_{Dato curioso: Podría usar el lenguaje de programación Julia en lugar de Python, lo que podría ser mucho más rápido, pero ya verifiqué números realmente grandes y tal programa (y fuerza bruta en general) nunca probará que no hay otras potencias de $2$ que tengan esta propiedad. Podría desaprobarlo, pero creo que la posibilidad es realmente muy pequeña.}

Verifiqué hasta $2^{23826}$, que es un número de 7173 dígitos, pero sin suerte. Dado que los números tienen cada vez más dígitos con potencias de $2$ más grandes, la posibilidad de que un número no tenga un dígito que sea potencia de $2$ se vuelve cada vez más pequeña.

Hice un gráfico de $\frac{\text{número de dígitos que son potencia de 2}}{\text{número total de dígitos}}$ versus la $n$-ésima potencia de $2$ en una escala logarítmica.

¡Este gráfico está equivocado! Ver la edición.

Como predije, el gráfico disminuye muy rápido hasta casi llegar a $0$. Creo que $\frac{\text{número de dígitos que son potencia de 2}}{\text{número total de dígitos}}\rightarrow 0$ a medida que $n \rightarrow \infty$ y por lo tanto $\text{P}(\text{n-ésima potencia de 2 no tiene dígitos de 2 en ella}) \rightarrow 0$, pero esto es solo mi intuición.

Entonces mi pregunta: ¿$2^{16} = 65536$ es la única potencia de $2$ que no tiene ningún dígito que sea potencia de $2$ (es decir, ningún dígito $\in \{1,2,4,8\}$) cuando se representa en base-$10$? ¿Hay una prueba, un contraejemplo, o es una pregunta abierta? También tengo curiosidad sobre potencias de $2$ que no tienen dígitos que sean potencia de $2$ en otras bases que no sean $10$.

Edición: Como señaló @Aweygan, el gráfico de arriba está equivocado. Por error, dividí por el número en sí, en lugar de la cantidad de dígitos que tiene el número. A continuación, una versión correcta, en una escala lineal.

A partir de este gráfico, parece que $\frac{\text{número de dígitos que son potencia de 2}}{\text{número total de dígitos}} \rightarrow 0.4$ a medida que $n \rightarrow \infty$. Esto parece tener sentido, ya que $\text{P}(\text{dígito} \in {1,2,4,8}) = 4/10 = 0.4$ y dado que la cantidad de dígitos se vuelve cada vez mayor, la ley de los grandes números se vuelve "visible".

Sobre la posible duplicación: esa pregunta se publicó hace 4,5 años. El estado del problema (demostrado, refutado, pregunta abierta) podría haber cambiado en ese tiempo. :)

Answer 1

Creo que tu pregunta todavía está abierta. Algo de notación antes de pasar a una conjetura relacionada:

Denotamos $a\preceq b$ si $a$ es una subsecuencia de $b$ cuando ambos están escritos en base $10$, por ejemplo, $553\preceq 65536$, $63\preceq 65536$, pero $35$ no es una subsecuencia (por lo que el orden importa). Dado un conjunto $S\subseteq\mathbb{N}$, definimos el conjunto mínimo como el conjunto más pequeño $M\subset S$, tal que para todo $s\in S$, existe $m\in M$ y $m\preceq s$. De la lema de Higman, sabemos que el conjunto mínimo es finito para cada posible $S.

Volviendo a tu pregunta, hay una conjetura más débil de J. Shallit en

Primos mínimos, J. Matemáticas Recreativas. 30 (2000), 113-117

de que $\{1,2,4,8,65536\}$ es el conjunto mínimo de potencias de $2$ en base $10$, que hasta donde yo sé aún está abierta. Como observó Shallit en el artículo que esta conjetura es verdadera si "cada potencia de $16$ mayor que $65536$ contiene un dígito en el conjunto $\{1,2,4,8\}$", que es precisamente tu pregunta.

Para la búsqueda numérica, puedes consultar $A137998$. La pregunta es equivalente a afirmar que $16^4$ es la única entrada del $0$ que aparece en esta secuencia. Debido a un patrón repetitivo mencionado en sus comentarios, solo tendrías que verificar como máximo $12$ de cada $25$ potencias de $16$.

(Nota: esto se había publicado como un comentario, pero como era el décimo comentario, sé que no todos lo notarían. Espero que se haya expandido lo suficiente como para ser justificado como una respuesta. Por favor, avísame si no es así)

---

Editado: a continuación se toma del artículo de Shallit en un intento de hacer el concepto de "conjunto mínimo" más accesible.

Vamos a echar un vistazo a los números primos. Si afirmara, como analogía a la pregunta original, que todos los números primos escritos en base-$10$ deben contener un dígito primo, es decir, $\{2,3,5,7\}$, podrías encontrar fácilmente un contraejemplo: "¿Qué tal el $11$? ¿y el $19$?". Sin embargo, podría expandir la lista para incluir todos los números primos de $2$ dígitos que no tienen dígitos primos, es decir, $\{2,3,5,7,11,19,41,61,89\}$. Luego afirmaría que todos los números primos deben contener un número primo en esta nueva lista. Aquí es donde tendría que aclarar qué significa que un número "contenga" otro número con más de un dígito, por ejemplo, $19$. La definición elegida aquí es que, dado un número $b$, si podemos llegar a $a$ eliminando algunos dígitos de $b$, entonces decimos que $b$ contiene a $a$ (o $a\preceq b$). Como ejemplo, $109$ es un número primo y contiene a $19$. Esta vez te llevaría un poco de esfuerzo encontrar una refutación: el primero es $409$. El procedimiento continúa a medida que extendería la lista para incluir tales números primos de $3$ dígitos y tú producirías ejemplos más grandes, y así sucesivamente.

La sorpresa es que este proceso necesariamente termina, debido a la lema de Higman. A medida que mi lista crece (pero sigue siendo finita), en cierto momento la afirmación se vuelve verdadera. Llamamos al conjunto final conjunto mínimo de números primos.

Podemos repetir este proceso para potencias de $2$, lo que lleva a la conjetura de que $\{1,2,4,8,65536\}$ es el conjunto mínimo. Aparentemente, esta conjetura es más débil que tu pregunta, ya que permite la posibilidad de que exista alguna potencia de $2$ que no contenga $1,2,4,8$ pero contenga $65536$. Nota que las pruebas que conocemos para la lema de Higman, aunque constructivas, no son efectivas para darnos el conjunto mínimo real en general. Shallit logró obtener la respuesta para los números primos usando medios elementales, pero hasta donde yo sé, no hay progreso para el conjunto mínimo de potencias de $2`, lo que a su vez indica que la afirmación más fuerte en tu pregunta todavía está abierta.