¿Hay algún cuadrado perfecto en la secuencia $12,123,1234,12345,...$?

Question

Sea $x_n$ el número construido concatenando los primeros $n$ enteros positivos. ¿Hay algún cuadrado perfecto en la secuencia $(x_n)_{n>2}$?

Este es OEIS A007908. Esta es la secuencia de números de Smarandache. No conocemos ningún índice $n$ tal que $x_n$ sea un número primo (ver aquí, o la página de OEIS enlazada anteriormente).

Este código de Mathematica sugiere que no hay cuadrado perfecto para $n<1000$:

For[i = 1; t = i, i < 1000,
   t = 10^(Floor[Log10[i]] + 1)*t + i, ++i;
   If[ Floor[Sqrt[t]] == t, Print[t]]
]

De manera similar, usando Surd[t, k] parece que $x_n$ no es una potencia $k$-ésima para $n>1000$, $k>5$. Según Sobre la secuencia de cuadrados concatenados al revés (Ling Li), se conjetura que la secuencia similar $14,149,14916,1491625$ obtenida concatenando los primeros $n$ cuadrados no contiene ningún cuadrado perfecto. Creo que la inducción podría ser utilizada.

¡Gracias por tu ayuda!

Answer 1

Respuesta parcial

El último dígito de cualquier cuadrado perfecto debe ser 0, 1, 4, 5, 6, 9. Por lo tanto, debemos tener $n \in \{ 0, 1, 4, 5, 6, 9 \}$ (módulo 10).

Recordemos que la suma de los primeros $n$ enteros es $\frac{n(n+1)}{2}$, y cada entero es congruente módulo 9 con la suma de sus dígitos. Al leer por la diagonal de la tabla de multiplicar en base 9, vemos que los cuadrados perfectos terminan en 0, 1, 4 o 7. Por lo tanto, debemos tener $\frac{n(n+1)}{2} \in \{ 0, 1, 4, 7 \}$ (módulo 9). De manera equivalente, $n \in \{0, 1, 4, 7, 8\}$ (módulo 9).

Al combinar los resultados módulo 10 y módulo 9, obtenemos:

$$n \in \{0, 1, 4, 9, 10, 16, 19, 25, 26, 31, 34, 35, 36, 40, 44, 45, 46, 49, 54, 55, 61, 64, 70, 71, 76, 79, 80, 81, 85, 89 \}~ (\text{mód } 90)$$

Ahora, consideremos los dos últimos dígitos del número. Todos los cuadrados perfectos terminan en 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89 o 96. De estos, los únicos que contienen dígitos consecutivos son 01, 56 y 89. Pero dado que $n = 1$ es explícitamente descartado por la pregunta, y $n = 6$ ($\sqrt{123456} \approx 351.36306$) y $n = 9$ ($\sqrt{123456789} \approx 11111.111061$) no producen cuadrados perfectos, entonces los dos últimos dígitos deben ser parte de $n$ mismo.

Al combinar los resultados módulo 90 y módulo 100, obtenemos:

$$n \in \{0, 1, 4, 9, 16, 25, 36, 44, 49, 61, 64, 76, 81, 89, 100, 109, 116, 121, 124, 125, 136, 144, 161, 169, 181, 184, 189, 196, 216, 224, 225, 229, 241, 244, 256, 261, 269, 289, 296, 301, 304, 316, 324, 325, 341, 349, 361, 364, 369, 376, 396, 400, 404, 409, 421, 424, 436, 441, 449, 469, 476, 481, 484, 496, 504, 521, 529, 541, 544, 549, 556, 576, 584, 589, 601, 604, 616, 621, 625, 629, 649, 656, 661, 664, 676, 684, 700, 701, 709, 721, 724, 729, 736, 756, 764, 769, 781, 784, 796, 800, 801, 809, 829, 836, 841, 844, 856, 864, 881, 889\}~ (\text{mód } 900)$$

Esto no resuelve el problema, pero reduciría el esfuerzo de una búsqueda exhaustiva, ya que solo tienes que probar 110 de cada 900 enteros consecutivos. Veré si hay una manera de filtrar la lista aún más.

Answer 2

Si $n$ es un cuadrado, entonces el siguiente cuadrado es $(\sqrt{n}+1)^2\approx n+ 2\sqrt{n}$, por lo que la densidad de cuadrados es alrededor de $2/\sqrt{n}$.

$n$ tiene alrededor de $\log(n)$ dígitos, por lo que $x_n$ tiene alrededor de $n \log(n)$ dígitos, entonces $x_n \approx 10^{n \log(n)}\approx n^n$.

Por lo tanto, utilizando una heurística de densidad, $x_n$ es un cuadrado con probabilidad $2 n^{-n/2}$ que disminuye muy rápido, por lo que el número esperado de cuadrados en $x_n$ después de $N$ es alrededor de $\sum_{n\geq N} 2n^{-n/2} \approx 2N^{-N/2}$.

Dado que ya has revisado los primeros $1000$ números, la probabilidad de que algún número posterior en la secuencia sea un cuadrado es a lo sumo $2\times 10^{-1500}\approx 0$. Por lo tanto, según esta heurística, es sumamente improbable que haya cuadrados en esta secuencia.

Nota que esto no es exactamente correcto ya que $x_n$ no está equidistribuido modulo 9, pero no creo que el punto fundamental cambie mucho incluso si manejaras eso de manera más cuidadosa.

Answer 3

Denota $$\dbinom q{r}_d = \dbinom {q-rd}{r+d}=\dbinom{q_{siguiente}}{r_{siguiente}}.$$ Luego los dígitos de la raíz cuadrada se pueden calcular de manera similar al algoritmo de dividir por esquina, en donde $q=0$ es una característica del cuadrado perfecto, con el valor de la raíz cuadrada $\frac r2$.

Si el cuadrado perfecto tiene una cantidad impar de dígitos, entonces el algoritmo se puede presentar en la forma $$\begin{align} &\dbinom{\mathbf1}{1}_1=\dbinom02,\quad\;\dbinom{0\mathbf{23}}{21}_1=\dbinom{2}{22}, \quad\dbinom{2\mathbf{45}}{221}_1=\dbinom{24}{222}, \quad\dbinom{24\mathbf{67}}{222\mathbf1}_1=\dbinom{246}{2222},\\[4pt] &\dbinom{246\mathbf{89}}{22221}_1=\dbinom{2468}{22222}, \quad\dbinom{2\,468\mathbf{10}}{2\,22221}_1=\dbinom{24589}{2\,22222}, \quad\dbinom{24589\mathbf{11}}{22\,22221}_1=\dbinom{2\,36690}{22\,22222},\\[4pt] &\dbinom{236\,690\mathbf{12}}{222\,22221}_1=\dbinom{14\,46791}{222\,22222}, \quad\dbinom{1446\,791\mathbf{13}}{2222\,22220}_0=\dbinom{1446\,79113}{2222\,22220},\\[4pt] &\dbinom{1\,44679\,113\mathbf{14}}{22222\,22206}_6=\dbinom{11345\,78078}{22222\,22212}, \quad\dbinom{11\,34578\,078\mathbf{15}}{2\,22222\,22125}_5=\dbinom{23466\,97190}{2\,22222\,22130},\dots \end{align}$$

Si el cuadrado perfecto tiene una cantidad par de dígitos, entonces el algoritmo se puede presentar en la forma de $$\begin{align} &\dbinom{\mathbf{12}}{3}_3=\dbinom36,\quad\;\dbinom{3\mathbf{34}}{65}_5=\dbinom{9}{70}, \quad\dbinom{9\mathbf{56}}{701}_1=\dbinom{255}{702}, \quad\dbinom{255\mathbf{78}}{702\mathbf3}_3=\dbinom{4509}{7026},\\[4pt] &\dbinom{4509\mathbf{91}}{70266}_6=\dbinom{29395}{70272},\dots \end{align}$$

El algoritmo descrito permite probar toda la secuencia de números en los dos flujos de cálculo. Si el resultado intermedio no corresponde con la secuencia dada, se puede omitir.

$\textbf{Apéndice}$

Hay un algoritmo que obtuve en la escuela. Traducido de mi publicación en otro sitio. Permite extraer una raíz cuadrada por columna, como dividiendo por una esquina.

El algoritmo se basa en la identidad $\mathbf{(ae+b)^2=a^2\,e^2 + (2ae+b)b}$ para $\mathbf{e=10}$.

El papel de a es el valor de la raíz cuadrada calculado para los dígitos más altos del número, el papel de b es el nuevo dígito. El valor de la raíz se calcula por deficiencia, el número de dígitos decimales del resultado no está limitado.

A diferencia del algoritmo de división por columna, dos nuevos dígitos del número original participan en la obtención de un nuevo dígito a la vez, y al recibir una parte fraccional, también se añaden ceros en pares. Esto es lo que nos dice el multiplicador $\mathbf{e^2=100}$ en la fórmula.

Para que el resultado no obtenga el factor $\mathbf{\sqrt{10}\approx 3.162}$, los números se agrupan en pares, comenzando desde el punto decimal. En este caso, el grupo más significativo contiene uno o dos dígitos.

La figura muestra el proceso de extracción de la raíz cuadrada del número $\mathbf{N = 69696}.$

El número N se coloca de la manera habitual. En lugar de una esquina a la derecha, escribimos el signo $\mathbf{=}.$ Y casi inmediatamente escribimos el primer dígito $\mathbf{b_2=a_2=2},$ porque $\mathbf{\lfloor\sqrt6\rfloor=2}.$ Estaba en los cientos.

En la segunda iteración, argumentamos de la siguiente manera: el lado izquierdo de la identidad está en la parte superior, el número $\mathbf{a_2=2}$ está a la derecha del signo igual. Restando el valor $\mathbf{a_2^2=4}$ del número superior y moviendo hacia abajo un par de dígitos $\mathbf{96}$ para este par, obtenemos la igualdad $\mathbf{(2a_2e+b_1)b_1\le296},$ donde $\mathbf{b_1}$ es el dígito desconocido en la decena del dígito. Dibujamos líneas horizontales y verticales, como en la figura, y a la izquierda de la línea vertical, con un salto a la izquierda de un dígito, escribimos el número $\mathbf{2a_2=4}.$

Si concatenamos a esto el número $\mathbf{b_1}$ al lado derecho, obtenemos justo $\mathbf{2a_2e+b_1}.$ Y si el mismo número $\mathbf{b_1}$ se coloca debajo, entonces obtenemos un ejemplo para la multiplicación con la respuesta 296. Vamos a elegir este número en nuestra mente: $\mathbf{45x5=225}-$ no es suficiente, $\mathbf{47x7=329}$ - ya es demasiado, $\mathbf{46\times6=276}$ - ¡justo! Y escribimos inmediatamente $\mathbf{276}$ debajo de $\mathbf{296}$ - para no olvidar. Y añadimos el número obtenido justamente $\mathbf{b_1=6}$ a la respuesta a la derecha.

Entonces, la tercera iteración. Y algo ya está claro: dos nuevos guiones, resta por columna y demolición de los siguientes dos dígitos - $\mathbf{2096}\dots$ Y aquí está el matiz: $\mathbf{(2a_2e+b_1)+b_1\ge2(a_2e+b_1)=2a_1}.$ Es decir, no tenemos que multiplicar en nuestra mente $\mathbf{26\times2},$ sino que podemos sumar $\mathbf{46}$ y $\mathbf{6}$ en una columna. Y obtener $\mathbf{52}.$

Así, $\mathbf{52b_0\times b_0 = 2096\dots... b_0=4}$ - ¡hooray! Pintar cuidadosamente en $\mathbf{4}$ en la multiplicación, $\mathbf{2096}$ en la parte inferior, $\mathbf{4}$ a la derecha. La raíz se extrajo seguramente completamente.

Ahora no hay nada que impida formalizar el algoritmo, y para cualquier sistema numérico.

La pregunta puede surgir: ¿por qué este algoritmo, si hay un algoritmo iterativo de Herón de Alejandría? Simplemente porque tiene ventajas - las mismas que dividir por una esquina:

1. La capacidad de calcular el resultado a una velocidad de ~10 operaciones (comparación, resta, OR lógico y desplazamientos) por bit del resultado con un error de hardware.
2. Sencillez de uso para números binarios largos representados por matrices.
3. Capacidad de extraer la raíz cuadrada manualmente en cualquier sistema numérico.
4. Presentación garantizada del resultado por deficiencia.

Answer 4

Siguiendo el comentario de Samir Khan, usando $2 \times 5 \equiv 1 \pmod 9$, enumerando todos los valores posibles:

$$x_n \equiv \frac{1}{2} n (n + 1) \equiv 5 n (n + 1) \in \{0,1,3,6\} \pmod 9$$ y $$m^2 \in \{0,1,4,7\} \pmod 9$$

Por lo tanto,

$$\exists m\in\mathbb{N} . m^2 = x_n \implies x_n \in \{0,1,3,6\} \cap \{0,1,4,7\} \equiv \{0,1\} \pmod 9$$

Observando los valores tomados por $5 n (n+1) \pmod 9$, vemos que esto se cumple con $$n \in \{ 0,1,4,7,8 \} \pmod 9$$

Considerando los dígitos finales en base $10$, como en la respuesta de Dan. Tenemos que para un $n$ con $m$ dígitos (con $n$ no igual a $10^{m-1}$), entonces $n$ debe ser un residuo cuadrático módulo $10^m$ y $(n-1) 10^m + n$ debe ser un residuo cuadrático módulo $10^{2m}$. En general, para $10^{m-1} + k -1 \le n < 10^m$, entonces $\sum_{j=0}^{k-1} (n - j) 10^{jm}$ debe ser un residuo cuadrático módulo $10^{km}$.

Combinando con el test de módulo $9$, enumerando los posibles $n$ por estos criterios se encuentra mediante una búsqueda por computadora (por ejemplo, usando una prueba eficiente de residuo cuadrático) que la proporción de candidatos $n$ parece estabilizarse en alrededor del $3.5\%$, incluso a medida que $m$ y $k$ aumentan, lo cual considero sorprendente.

Mientras tanto, desde el otro extremo, los dígitos principales de la raíz cuadrada de $x_n$ (por ejemplo, usando un algoritmo védico) son uno de

$$11111111065105601373995021196\ldots$$ o $$35136418300833130224757756198\ldots$$ dependiendo de si el número de dígitos de $x_n$ es impar o par.

El cálculo puede formularse como algoritmos (de manera similar a la respuesta de Yuri Negometyanov) que emiten dígitos de las raíces cuadradas: si alguno termina, entonces un $x_n$ es un cuadrado perfecto. Probar la (no)terminación puede no ser más fácil que el problema original.

Aquí tienes un ejemplo de implementación simplificado en Haskell (este programa puede dar un falso positivo debido a truncar la secuencia de dígitos concatenados en la mitad de uno de los números agregados):

import Data.List (elemIndex)
import Data.Maybe (fromJust)
import Numeric (showIntAtBase)

b :: Integer
b = 10

digits :: [Char]
digits = "0123456789"

string :: [Integer]
string = map (fromIntegral . fromJust . (`elemIndex` digits)) .
  concat . map (\n -> showIntAtBase (fromIntegral b) (digits !!) n "") $
    [1..]

isqrt :: Integer -> Integer -> [Integer] -> [Char]
isqrt acc s (x:y:zs) = (digits !! fromIntegral d) :
    if r == 0 && acc /= 0 {- && not an incomplete concatenation -} then [] else
      isqrt (b * acc + 2 * d) (b^2 * r + b * x + y) zs
  where
    d = maximum [ d | d <- [0..b-1], (b * acc + d) * d <= s ]
    r = s - (b * acc + d) * d

main' :: [Integer] -> ([Char], [Char])
main' (x:y:zs) = (isqrt 0 x (y:zs), isqrt 0 (b * x + y) zs)

main :: IO ()
main = do
  let (x, y) = main' string
  mapM_ print (zip3 [1..] x y)

El cálculo no ha terminado hasta ahora, actualmente tiene alrededor de $4000000$ dígitos de salida después de unas 3.5 horas de computación.

Answer 5

EDICIÓN: Las tablas estaban completamente equivocadas.

Siguiendo el consejo de Samir Khan, consideremos el módulo 11:

Sea $d_n$ el número de dígitos de $n$. Se puede demostrar que si $d_n$ es par, entonces $$x_n\equiv 6(1+n+n^2)-d_n\pmod{11}.$$ Me tomó un tiempo demostrar esto, tal vez alguno de ustedes pueda encontrar una prueba simple; escribiré la mía al final de esta publicación. Por otro lado, si $d_n$ es impar y $n$ es par, tenemos $$x_n\equiv -(1+5n)+d_n\pmod{11}.$$

Finalmente, si tanto $d_n$ como $n$ son impares, entonces $$x_n\equiv -(4+5n)-d_n\pmod{11}.$$

En resumen, el módulo $11$ no nos dice mucho. Tal vez puedan obtener congruencias similares modulo $12$ que serían más útiles, ya que $12$ no tiene tantos residuos cuadráticos como $11$.

PRUEBA DE LAS CONGRUENCIAS

Denotemos el número de dígitos de $x_n$ como $D_n$; para simplificar la notación escribiremos $D=D_n$ y $d=d_n$. Consideremos la expansión en base $10$ de $x_n$: \begin{array}{} x_n&=&10^{D-1} 1&+&10^{D-2}2&+&10^{D-3} 3&+&\cdots&+&10^{D-9} 9\\ &&10^{D-11}10&+&10^{D-13}11&+&10^{D-15}12&+&\cdots&+&10^{D-189}99\\ &&10^{D-192}100&+&10^{D-195}101&+&10^{D-198}102&+&\cdots&+&10^{D-2889}999\\ &&\cdots\\ &&\cdots&+&10^{D-D}n \end{array} Observe que el valor exacto de los exponentes de $10$ no importa: solo importa si son pares o impares. Módulo $11$ obtenemos: \begin{array}{} x_n&\equiv&(-1)^{D-1} 1&+&(-1)^D2&+&(-1)^{D-1} 3&+&\cdots&+&(-1)^{D-1} 9\\ &&(-1)^{D-1}(\quad10&+&11&+&12&+&\cdots&+&99\quad)\\ &&(-1)^{D}100&+&(-1)^{D-1}101&+&(-1)^{D}102&+&\cdots&+&(-1)^{D-1}999\\ &&\cdots\\ &&\cdots&+&n Observe el patrón: estamos obteniendo sumas alternadas de las forma $s_1(k):=\sum_{i=10^k}^{10^{k+1}-1}(-1)^{D-i}i$ en las filas impares y sumas fáciles $s_2(k):=(-1)^{D-1}\sum_{i=10^k}^{10^{k+1}-1}i$ en las filas pares. Además, obtenemos una suma final desde $10^{d-1}$ hasta $n$ que puede tener cualquiera de las dos formas anteriores.

Consideremos primero las sumas fáciles $s_2(k)$. Usando la fórmula escolar para la suma de números consecutivos, obtenemos $$s_2(k)=\frac{(-1)^{D-1}}{2}(10^{k+1}-10^k)(10^{k+1}+10^k-1).$$ Reduciendo módulo $11$ para obtener ($k$ es impar ya que sumamos las filas pares) $$s_2(k)\equiv (-1)^{D}\pmod{11}.$$ Ahora, examinemos la suma de $s_2(k)$ para las filas pares, es decir, para $k$ que va desde $1$ hasta la última potencia de $10$ de la fila par. Si no me equivoco, esto debería ser $$S_2:=\sum_{\substack{k=1\\k+=2}}^{d-\frac{(-1)^d+5}{2}}s_2(k)\equiv(-1)^D\bigg(1+\Big\lfloor\frac{1}{2}\Big(d-\frac{(-1)^d+5}{2}-1\Big)\Big\rfloor\bigg)\equiv(-1)^D\bigg(1+\Big\lfloor\frac{1}{4}(2d-7-(-1)^d)\Big\rfloor \bigg)\pmod{11}.$$ De manera similar, se puede demostrar que para $k>0$ $$s_1(k)\equiv (-1)^{D}\pmod{11},$$ y $$S_1:=\sum_{\substack{k=2\\k+=2}}^{d+\frac{(-1)^d-5}{2}}s_1(k)\equiv(-1)^{D} \bigg(1+\Big\lfloor \frac{1}{4}(2 d-9+(-1)^d)\Big\rfloor \bigg)\pmod{11}.$$ Adicionalmente, las expresiones de suelo que aparecen en $S_1$ y $S_2$ se pueden combinar para obtener $$S_1+S_2\equiv (-1)^D(d-2)\pmod{11}.$$ A continuación, calculemos la suma de la primera fila (que omitimos porque asumimos que $k>0$): $$\sum_{i=1}^9(-1)^{D-i}i=-5(-1)^D.$$ Por lo tanto, $$\text{Suma de todas las filas menos la última}\equiv S_1+S_2-5(-1)^D\equiv(-1)^D(d+4)\pmod{11}.$$ Observe que esto no debería funcionar para $n<10$, ya que estaríamos sumando toda la primera fila. Además, la página de Wolfram MathWorld sobre números Smarandache dice que $D=(n+1)d-\dfrac{1}{9}(10^d-1)$. Entonces, simplificando, $$\text{Suma de todas las filas menos la última}\equiv -(-1)^{(n+1)d}(d+4)\pmod{11}.$$ Por lo tanto, todo se reduce a considerar las diferentes posibilidades para la última fila. Por ejemplo, si $d$ es par, la última fila se convierte en $$(-1)^{D-1}\sum_{i=10^{d-1}}^n i=\frac{(-1)^{D-1}}{2}(n-10^{d-1}+1)(n+10^{d-1})\equiv 6(-1)^{D-1}(n+2)(n-1)\pmod{11}.$$ Aplicando nuevamente la igualdad para $D$ obtenemos $$\text{Suma de la última fila}\equiv 6(n+2)(n-1)\pmod{11},$$ y así $$\text{Suma de todas las filas}\equiv -(-1)^{(n+1)d}(d+4)+6(n+2)(n-1)\equiv 6(1+n+n^2)-d\pmod{11}.$$ Los otros casos son análogos.