Puede $N^2$ sólo tienen los dígitos 0 y 1, además de $N=10^k$ ?

Question

Pablo Solís preguntó esto en una reciente Seminario de 20 preguntas en Berkeley. ¿Hay un número entero positivo $N$ no de la forma $10^k$ , de manera que los dígitos de $N^2$ ¿son todos 0 y 1?

Parece muy poco probable, pero no tengo pruebas. Es fácil ver que tal número debe terminar en 1 o 9, y luego es fácil ver que debe terminar en 01, 49, 51 o 99, y se puede continuar recursivamente durante todo el tiempo que se quiera, determinando posibles "sufijos". Usando esto, hice que un ordenador comprobara por mí que no hay tales N hasta aproximadamente $10^{24}$ .

Si se pretende que los dígitos de $N^2$ se distribuyen aleatoriamente, y $N$ tiene $n$ -dígitos, hay un $(2/10)^{2n}$ posibilidad de satisfacer esta condición. Sólo hay $10^n$ $n$ -números de dígitos, por lo que se puede esperar un $(4/10)^n$ posibilidad de tener una $n$ -número de dígitos. Esto sugiere que no debemos esperar encontrar nada.

(Si se intenta el mismo problema en otras bases, donde las probabilidades son mejores, sí se encuentran algunas: en base 5, funcionan 222112144, 22222111221444 y 100024441003001).

Answer 1

En aras de la exhaustividad, esto es lo que puse en la wiki de 20 preguntas - también podríamos repetirlo aquí en el $\infty$ -sitio de preguntas. Tuve básicamente la misma idea que Ilya, hacer una búsqueda ramificada para buscar los dígitos de $N^2$ . Sin embargo, el código que yo escribí en Python funciona desde el extremo de los 10 ádicos, mientras que el de Ilya lo hace desde el extremo de los arcos. Ambos programas soportan un modelo heurístico que implica que las soluciones en los enteros son muy poco probables. Si quisieras una búsqueda optimizada en los enteros, trabajarías desde ambos extremos y tratarías de igualar las soluciones parciales. Y probablemente querrías implementar los algoritmos en C++ en lugar de en Python.

maxmod = 10**24

def check(x):
    if not str(x**2).replace('0','').replace('1',''):
        print 'Eureka:',x,x**2

def search(x,mod):
    x %= mod
    if mod == maxmod:
        check(x)
        check(mod-x)
        return
    top = -(x**2/mod) % 10
    x += (top + top%2)/2 * mod
    search(x,mod*10)
    search(x + 5*mod,mod*10)

search(1,10)    # Solution is either 1 or 9 mod 10

Además, es tentador marcar el problema como abierto y no como un "rompecabezas". Encontré varios artículos que analizaban la estructura de congruencia de los números enteros con dígitos restringidos, y uno que analizaba los factores primos. Dos son de Erdos, Mauduit y Sarkozy 1 2 y dos son de Banks y Shparlinski (uno también con Conflitti) 3 4 . Es de suponer que algunos de estos autores pueden decir si el problema debe llamarse abierto.

Answer 2

Permítanme rehacer el argumento probabilístico. Sabemos que el $k$ últimos dígitos de $n^2$ se determinan por el $k$ últimos dígitos de $n$ . Por ejemplo, $n^2$ termina con un $1$ si y sólo si $n$ termina con un $1$ o un $9$ . Por inducción, se demuestra que hay $2^k$ $k$ -suplementos de dígitos $\bar a=a_1\ldots a_k$ tal que el cuadrado de un número $n$ terminando con $\bar a$ termina con $k$ unos y ceros. Por ejemplo, si $k=3$ los trillizos son $001,249,251,499,501,749,751, 999$ .

Si $n$ es una solución al problema, y $k$ es el número de dígitos de $n$ entonces $n$ debe ser un $\bar a$ como en el caso anterior. Tomar el cuadrado de tal $\bar a$ . Sabemos que su $k$ los últimos dígitos son unos y ceros. Para que proporcione una solución, el $k$ los primeros dígitos tienen que ser unos y ceros, una propiedad cuya probabilidad es $5^{-k}$ . Por lo tanto, la probabilidad de que haya una solución $n$ de longitud $k$ es aproximadamente $(2/5)^{-k}$ . Desde la serie $$\sum_{k=1}^\infty\left(\frac{2}{5}\right)^k$$ converge, apuesto a que sólo hay un número finito de soluciones. Pero si no se encuentra una finita, supongo que no habrá ninguna solución.

Answer 3

Esto me recuerda el primer problema que Knuth propuso para las Sesiones "Aha" (1985): encontrar todos los enteros positivos N tales que los dígitos decimales de N y N 2 están en orden no decreciente de izquierda a derecha.

El informe está aquí: http://www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf y los vídeos disponibles en http://scpd.stanford.edu/knuth/index.jsp

Tal vez no sirva de nada, pero creo que algunos de los análisis podrían (como el descubrimiento de lemas de bombeo).

Answer 4

Por si le interesa a alguien, aquí están los resultados de mi programa en Python que intentaba encontrar un posible prefijo empezando por el 1:

(number of digits) (prefixes found) (random prefix's square)
1 1 1
2 1 100
3 3 11025
4 7 1110916
5 13 110103049
6 29 10110101401
7 54 1000000000000
8 109 110110079422225
9 211 11011100073896521
10 420 1011001100765105025
11 825 100111001106029802256
12 1665 10111011010034411118321
13 3278 1001010099998757262220676
14 6547 101001100011007822397559225
15 13029 10101011110111066632483438225
16 26204 1101001101100999240998885170436
17 51971 100101111100099999132148424632569
18 104374 11110111010101000021756144077830521

(Se perdió el 19)

20 415887 101001001010000099981803716294793733281
21 831804 11110100101110110101012586511482091637081
22 1663040 1110000111001111100100391333262727080693449

Confirma lo que sabíamos sobre la probabilidad -es muy poco probable que exista tal número-, pero no mucho más todavía.

Answer 5

El argumento de la probabilidad es engañoso: hay 0 probabilidades de que un número entero aleatorio sea primo, y sin embargo son infinitas. Así que aunque la probabilidad de que haya un entero menor que N que tenga la propiedad vaya a 0 a medida que N aumenta, no descarta su existencia.

Los mismos argumentos se pueden utilizar para los cuadrados, es decir, la probabilidad de que un número en [1,N] sea un cuadrado perfecto converge a 0 a medida que N crece.