Una fórmula para números que no son
Una fórmula como a_n=n^2 genera todos los números naturales que son cuadrados perfectos. Y quizá nunca te hayas planteado el problema inverso. ¿Existe alguna fórmula que genere los números que no son cuadrados perfectos? O sea, si separamos los naturales en dos grupos, uno con los cuadrados y otro con los no-cuadrados, de esta manera
\begin{array}{l | ccccc}
a_n & 1 & ~& ~& 4 & ~ & ~& ~&~& 9& & & & \cdots & \\[4pt]
b_n & ~ & 2& 3& ~ & 5 & 6& 7&8& ~& 10 & 11 & 12&\cdots &
\end{array}¿Qué fórmula genera los números que aparecen en la segunda fila? ¿Hay alguna expresión sencilla para b_n? De eso hablaremos en el artículo de hoy. ¡Un teorema que no sabías que necesitabas hasta ahora!
No me quiero guardar el resultado hasta el final. ¡Hay infinitas fórmulas que generan los números que no son cuadrados! Aquí una de ellas:
Números no-cuadrados
La siguiente expresión genera todos los números no-cuadrados. El n-ésimo número que no es un cuadrado perfecto es
b_n = n+\big\lfloor \sqrt{n}+\tfrac{1}{2}\big\rfloor .Los símbolos \lfloor \cdot \rfloor representan la función suelo, que borra los decimales del número que contiene.
En este artículo propongo un método para encontrar números que no son algo (como números que no son cuadrados o que no son potencias de dos). Este problema suele mencionarse al hablar del teorema de Lambek-Moser. En el libro Ingenuity in Mathematics, Ross Honsberger hace una introducción general, pero prefiero el artículo de Bakir Farhi para entender cómo se deducen este tipo de fórmulas.
La demostración de todo está en el artículo de Bakir y no pienso repetirla. Aquí solo comento algunas ideas intuitivas y de motivación. Venga, ¡al lío!
Una fórmula de andar por casa
Un poco de notación. La sucesión \{a_n\} contiene todos los cuadrados perfectos y la sucesión \{b_m\} todos los no-cuadrados, ambas ordenadas de forma creciente. Cuando hable de la primera, usaré el subíndice n; cuando hable de la segunda, usaré una m. Estos valores de n y m indican la posición de los elementos de cada sucesión. El quinto cuadrado perfecto es a_5=25. El quinto no-cuadrado es b_5=7.
\begin{array}{l | ccccc}
n & 1 & 2& 3& 4 & 5 & 6 & \cdots & \\[4pt]
a_n & 1 &4& 9& 16 & 25 & 36& \cdots &
\end{array}\begin{array}{l | ccccc}
m & 1 & 2& 3& 4 & 5 & 6 & \cdots & \\[4pt]
b_m & 2 &3& 5& 6 & 7 & 8& \cdots &
\end{array}La fórmula que genera los números de la primera sucesión está clara: a_n=n^2. ¿Qué fórmula genera los números de la otra sucesión? Echa un vistazo a los elementos de la lista:
\begin{array}{l | ccccc}
m & ~&1 & 2& ~&3& 4 & 5 & 6& ~&7&8& 9& 10& \cdots & \\[4pt]
b_m & \square & 2& 3&\square& 5 & 6& 7&8& \square& 10 & 11 & 12& 13 &\cdots &
\end{array}
Observa que esta sucesión es muy parecida a la de los números naturales, pero añadiendo algunos huecos. Cada vez que aparece un cuadrado perfecto, nos lo saltamos, no lo incluimos en la lista. Es como contar los números naturales de uno en uno dando un salto cada vez que encontramos un cuadrado perfecto.
Déjame profundizar en esta idea. ¿Cuál es el noveno término de la sucesión, b_9? Si contáramos todos los números naturales, el noveno elemento de la lista sería 9. Pero como la lista no incluye los cuadrados perfectos, hemos omitido los números uno, cuatro y nueve de la lista. Por tanto, el número b_9 estará desplazado tres unidades hacia delante. O sea, b_9=9+3=12. ¡Puedes comprobar en la tabla anterior que este resultado coincide con lo que esperábamos!
Pongo otro ejemplo. ¿Cuál es el no-cuadrado de la quinta posición? Si todos los naturales estuvieran en la lista, b_5 sería 5. Como la lista no incluye los números uno y cuatro, el número b_5 estará desplazado dos unidades, porque nos hemos saltado dos números. Por tanto, b_5=5+2=7.
En general, el término general de la fórmula que buscamos se puede escribir como
b_m = m + (\text{número de cuadrados}\leq b_m).Es decir, calcular el m-ésimo número no-cuadrado es como contar hasta el número m y añadir los cuadrados que nos hemos saltado, los que no aparecen en la lista.
Aunque la fórmula tiene sentido intuitivo, es horrible. ¡Es demasiado circular! Según la expresión, para calcular b_m necesito contar cuántos cuadrados perfectos hay antes de b_m. Pero ¿cómo puedo hacer eso si no conozco el valor de b_m? Bueno, hay dos soluciones posibles: aceptar que la fórmula es circular y el mundo es hostil y frío algunas veces, o complicarnos la vida para eliminar esa recursividad. ¡Vamos a probar los dos métodos!
Una fórmula circular
Buscamos una fórmula para el término
(\text{número de cuadrados}\leq b_m) .Dado un número natural p, ¿cuántos cuadrados perfectos son menores o iguales que p? Dicho de otra manera: ¿cuántos números n\in\mathbb{N} cumplen n^2\leq p? Podemos resolver la desigualdad directamente tomando raíces cuadradas en cada lado.
n^2 \leq p \qquad\to\quad n\leq \sqrt{p}.Como n es un número natural, podemos obviar los decimales que aparecen en \sqrt{p}. Esto se consigue con la función suelo: n\leq \lfloor \sqrt{p} \rfloor. En resumen, hay \lfloor\sqrt{p}\rfloor cuadrados perfectos que son menores o iguales que p. Por poner un ejemplo numérico, los cuadrados perfectos menores que veinte son \lfloor \sqrt{20} \rfloor = \lfloor 4.47... \rfloor = 4. A saber: el uno, el cuatro, el nueve y el dieciséis.
La fórmula que genera los números que no son cuadrados perfectos se puede reescribir como
b_m = m + (\text{número de cuadrados}\leq b_m) = m +\lfloor \sqrt{b_m}\rfloor.Como ya habíamos adelantado, esta fórmula es circular. Para calcular el valor de b_m necesitamos introducir el valor de b_m en la fórmula. No es un problema insalvable: si introducimos la fórmula de b_m dentro de la raíz cuadrada, obtenemos algo así:
b_m = m +\left\lfloor \sqrt{m +\lfloor \sqrt{b_m}\rfloor}\right\rfloor.Podemos sustituir de nuevo el valor de b_m dentro de la raíz, obteniendo
b_m = m +\left\lfloor \sqrt{m +\left\lfloor \sqrt{m +\left\lfloor \sqrt{m +\lfloor \sqrt{b_m}\rfloor}\right\rfloor}\right\rfloor}\right\rfloor.Y podemos alargar este proceso hasta que la paciencia nos aguante. Lo interesante es que, después de la segunda sustitución, estas raíces encadenadas no modifican el resultado final. Podríamos añadir veinte raíces encadenadas más y el valor de b_m no se modificaría, sin importar cuál sea el contenido de las raíces internas. Por ello, recortamos la expresión y nos quedamos solo con las dos primeras raíces:
b_m = m+ \left\lfloor \sqrt{m+\left\lfloor \sqrt{m} \right\rfloor}\right\rfloor.¡Y esta es una fórmula que genera los números que no son cuadrados perfectos! Si damos valores a m, encontramos la siguiente tabla. La fórmula funciona perfectamente.
\begin{array}{l | ccccc}
m &1 & 2& 3& 4 & 5 & 6& 7&8& 9& 10& 11& 12& 13& 14& \cdots & \\[4pt]
b_m & 2& 3& 5 & 6& 7&8& 10 & 11 & 12& 13 & 14 & 15 & 17 & 18 &\cdots &
\end{array}Hay algunos problemas que mencionar. El método para deducir la fórmula no es tan general como parece. Hemos tenido suerte, ya que las raíces encadenadas se pueden cortar en un punto y acabamos con una expresión sencilla. ¿Esto funciona siempre? Si pregunto cuál es la fórmula de los números que no son potencias de dos, ¿podré cortar la recursividad en algún momento, o eso es algo que solo funciona con los cuadrados?
Es difícil generalizar este método con otros números que no son algo. Muchas veces la fórmula que obtenemos con esta receta «converge» y podemos detener las sustituciones en algún punto. Pero determinar cuándo podemos parar la recursividad depende de cada problema particular. Por ello, lo ideal sería evitar la recursividad de alguna manera más general. ¡Y eso es lo que veremos en la siguiente sección!
Cómo evitar la recursividad
Hay una forma de evitar la circularidad de
b_m = m + (\text{número de cuadrados}\leq b_m).Podemos calcular el número de no-cuadrados con una resta. Lo explico con un ejemplo. Si escribes todos los naturales desde el uno al n^2, habrá n cuadrados perfectos: 1^2, 2^2, …, n^2. Dicho de otra forma, habrá n^2-n números en la lista que no son cuadrados perfectos. Definimos entonces la función cuenta-no-cuadrados como:
\phi(n)=n^2-n.
Esta función nos indica la cantidad de no-cuadrados que aparecen al escribir los números naturales desde el uno hasta el n^2. Tenemos, por ejemplo, que \phi(3)=6, es decir, que al escribir los números entre el uno y el 3^2=9 encontramos seis números que no son cuadrados perfectos. Aquí represento gráficamente algunos valores de la función. Son los puntos gordos.
La función \phi solo tiene sentido para valores naturales, pero podemos introducir cualquier número real en su fórmula. En ese caso obtendremos un gráfico como la línea continua representada en la imagen anterior.
El problema «inverso»
Piensa ahora en el problema a la inversa: ¿hasta qué n^2 tenemos que llegar para encontrar 6 no-cuadrados en la lista? Dicho de otra manera, ¿en qué momento se cumple que \phi(n)=6? Gráficamente, esto equivale a encontrar los puntos donde el gráfico está a altura seis, lo que ocurre cuando n=3. O sea, que si escribimos una lista de números entre el uno y el 3^2=9, habrá seis valores que no son cuadrados perfectos.
Este resultado tiene una lectura interesante: al escribir una lista de naturales con seis no-cuadrados, hemos incluido en ella tres cuadrados perfectos. Piénsalo: esa lista incluye los números entre el 1 y el 3^2, así que incluye tres cuadrados: el 1^2, el 2^2 y el 3^2. Y este es el problema que queríamos resolver. Queríamos saber cuántos cuadrados nos habíamos saltado al escribir una lista de números naturales que contenga una cantidad determinada de no-cuadrados.
\begin{array}{l | ccccc}
m & ~&1 & 2& ~&3& 4 & 5 & 6& ~\\[4pt]
b_m & \boxed{\,1\,} & 2& 3& \boxed{\,4\,}& 5 & 6& 7&8& \boxed{\,9\,}
\end{array}Otro ejemplo, para profundizar en la idea. ¿Hasta qué n^2 tenemos que llegar para encontrar 13 no-cuadrados en la lista? Esto equivale a buscar los puntos donde el gráfico está a altura 13, lo que ocurre cuando n\approx 4.1, un número entre cuatro y cinco. O sea, hay que escribir una lista de números entre el uno y el 4.1^2 (aproximadamente) para encontrar trece valores no-cuadrados.
\begin{array}{l | ccccc}
m & ~&1 & 2& ~&3& 4 & 5 & 6& ~&7&8& 9& 10& 11& 12& ~& 13\\[4pt]
b_m & \boxed{\,1\,} & 2& 3& \boxed{\,4\,}& 5 & 6& 7&8& \boxed{\,9\,}& 10 & 11 & 12& 13 &14 & 15& \boxed{16} & 17
\end{array}Al escribir esa lista, habrá cuatro cuadrados perfectos en ella. O sea, para escribir una lista con trece no-cuadrados debemos incluir cuatro cuadrados.
La función inversa
La idea detrás de estos cálculos es, en esencia, el propósito de la función inversa. Buscar qué punto del gráfico se encuentra a una altura m equivale a resolver la ecuación \phi(n)=m. En mi caso, como \phi(n)=n^2-n, el problema se reduce a resolver una ecuación de segundo grado:
n^2-n=m \qquad \to \qquad n=\frac{1}{2}\pm\frac{\sqrt{1+4m}}{2}.De los signos de la raíz cuadrada, elegimos el positivo. (Recuerda que queremos crear una lista de números entre el uno y el n^2, así que n debe ser un número positivo). Por tanto, la expresión de la función inversa que buscamos es esta:
\phi^{-1}(m)=\frac{1}{2} + \frac{\sqrt{4m+1}}{2}.Si queremos saber qué punto del gráfico está a altura m podemos usar la expresión de la función inversa. Así, por ejemplo, el punto del gráfico de que está a altura 13 será
\phi^{-1}(13)=\frac{1}{2} + \frac{\sqrt{4\cdot 13+1}}{2} \approx 4.14 .Para que una lista de números tenga trece no-cuadrados necesitamos escribir los números entre el uno y el 4.14^2 (aproximadamente). Y en esa lista aparecerán cuatro cuadrados.
Fíjate que el número de cuadrados de una lista es el valor de \phi^{-1}(m) obviando la parte decimal. Esto se escribe de manera compacta con la función suelo, de forma que:
(\text{número de cuadrados}\leq b_m) = \left\lfloor \phi^{-1} (m)\right\rfloor .En nuestro caso, sustituyendo las expresiones que hemos comentado a lo largo de la sección, concluimos que
b_m = m + \left\lfloor \frac{1}{2} + \frac{\sqrt{4m+1}}{2}\right\rfloor.¡Y esta es la expresión que buscábamos! Esta fórmula produce todos los números que no son cuadrados perfectos por orden y sin saltarse ninguno.
La función inversa de forma gráfica
No quiero terminar la sección sin hablar de la interpretación gráfica de los cálculos anteriores. Según los libros que calzan la pantalla de mi ordenador, el gráfico de la función inversa es como el de la función original pero reflejado respecto a la línea diagonal y=x. Las expresiones que hemos encontrado en el apartado anterior eran estas:
\phi(x)= x^2-x, \qquad \phi^{-1}(x)=\frac{1}{2}+\frac{\sqrt{4x+1}}{2} .En la siguiente imagen represento sus gráficos: \phi(x) (en colorado) y \phi^{-1}(x) (en anaranjado). Ambas líneas coinciden si imaginamos que la diagonal actúa como un espejo donde se reflejan.
Por último, la expresión de b_m= m + \lfloor\phi^{-1}(m)\rfloor borra los decimales de \phi^{-1}(m) con la función suelo. A nivel gráfico, esto se traduce en dibujar el gráfico de \phi^{-1} y «bajar» los puntos del gráfico hasta el entero que quede justo por debajo. Es como si el gráfico estuviera pixelado, como si fuera una escalera.
Ahora podemos ver cuántos cuadrados aparecen al escribir una lista de números naturales. Si queremos que aparezcan dos, tres, cuatro o cinco no-cuadrados en la lista, el gráfico nos indica que la lista incluirá dos cuadrados. Si queremos que aparezcan seis, siete, ocho, nueve, diez u once no-cuadrados, entonces la lista incluirá tres cuadrados. Y así. Este gráfico muestra cuántos cuadrados aparecen en la lista en función de la cantidad de no-cuadrados.
La moraleja es que, al anotar los números naturales uno por uno, los saltos del gráfico anterior nos indican cuándo aparecen cuadrados perfectos. Por ejemplo, cuando m=6 hay un salto en el gráfico, lo que significa que, al escribir seis no-cuadrados en la lista de números naturales, el siguiente elemento será un cuadrado perfecto. ¡Muy útil para nuestra empresa!
Una fórmula para los números que no-son-algo
Movamos las ideas anteriores un paso hacia la generalización. Considera una sucesión \left\{ a_n\right\} de números naturales, creciente y que no repita elementos. Definimos la sucesión complementaria \left\{ b_n\right\} como la formada por los números naturales que no incluye la sucesión \left\{ a_n\right\}, ordenados de menor a mayor. La pregunta es: ¿cómo podemos encontraruna fórmula para los números de la sucesión complementaria?
Como hemos comentado, el término general de una sucesión complementaria se puede escribir como
b_m = m + (\text{número de elementos de } \{a_n \} \leq b_m).La dificultad radica en contar los elementos de la primera sucesión que son más pequeños que el b_m que queremos calcular. De nuevo, este problema es circular, pero podemos evitarlo de forma análoga al caso de los cuadrados.
Definimos la función cuenta-no-a_n como
\phi(n) = a_n-n.
Esta función cuenta los números entre uno y a_n que no pertenecen a la sucesión original. Es decir, al escribir una lista con los números desde el uno hasta el a_n, habrá n valores que pertenecen a la sucesión original: a_1, a_2, …, y a_n. Por tanto, habrá a_n-n elementos de \left\{ b_n\right\} en esa lista.
Por argumentos análogos a los de la sección anterior, podemos contar el número de elementos de \{a_n\} con la función inversa de \phi, eliminando los decimales con la función suelo. Es decir,
b_m = m + \left\lfloor \phi^{-1}(m)\right \rfloor.Hasta aquí lo único que hemos hecho es generalizar el proceso que presenté en la sección anterior. Este argumento no siempre es preciso, pero se puede afinar como hacen en el artículo de Bakir Farhi. El teorema completo es este:
Teorema. Sucesión complementaria
Sea \{a_n\}_{n\in\mathbb{N}} una sucesión de enteros positivos y sea \phi\colon (0, \infty) \to \mathbb{R} una función creciente, continua y no acotada superiormente. Si \phi satisface para todo n\in\mathbb{N} que
a_n - n < \phi(n) \leq a_n - n +1,
entonces la fórmula b_m = m + \lfloor \phi^{-1}(m) \rfloor con m \geq a_0+1 genera la sucesión complementaria de \{a_n\}.
Ya hemos explicado las ideas que conducen a este resultado, pero hay un detalle que merece un comentario. La función \phi que aparece en el teorema es parecida a la función que cuenta los números que no-son-de-\{a_n\}, pero no tiene por qué ser esa función exactamente. Como la fórmula incluye una función suelo, que elimina los decimales del resultado, podemos escoger una función \phi con un poco de libertad. Da igual que el resultado tenga unos decimales más grandes o más pequeños, porque desaparecen en el cálculo final. Por eso, el teorema permite elegir un valor de \phi(n) que sea hasta una unidad más grande que el que hemos propuesto nosotros.
Muchas veces, este margen permite simplificar la expresión de b_m. Por ejemplo, en el caso de los cuadrados, a_n=n^2, podemos definir la función como
\phi(n)=n^2-n+\frac{1}{4}.Esta expresión es muy parecida a la función cuenta-no-cuadrados que hemos propuesto en la sección anterior, pero es \tfrac{1}{4} más grande. La inversa de esta función es más sencilla de calcular:
\qquad\qquad \phi^{-1}(m) = \frac{1}{2}+ \sqrt{m}.Lo que conduce a
b_m = m + \left\lfloor \sqrt{m} + \frac{1}{2}\right\rfloor.Ejemplo con los números corteses
En el artículo anterior hablábamos de los números corteses y nos interesaba una fórmula para generar números que no son potencias de dos. Ahora estamos en condiciones para encontrarla, con ayuda del teorema anterior. ¡Pero no es tan sencillo como parece!
En primer lugar, si a_n=2^n, podríamos inventar una función que cumpla las condiciones del teorema:
2^n-n < \phi(n) \leq 2^n - n + 1.
En ese caso, m + \lfloor \phi^{-1}(m) \rfloor sería la fórmula para encontrar los números que no son potencias de dos. Solo hay un problema: es difícil encontrar una expresión bonita para la función inversa. Una opción es esta:
\phi^{-1}(m) = \log_2\left( m + \log_2 m \right).¿Cómo se encuentra esa fórmula?
Las propuestas del estilo \phi(n)=2^n-n+1 cumplen las hipótesis del teorema, pero son difíciles de invertir: la expresión de \phi^{-1}(m) no se puede escribir con operaciones sencillas, con las que aparecen en las teclas de una calculadora.
La estrategia aquí es otra: buscamos primero \phi^{-1} y comprobamos después que se cumplen las condiciones del teorema. ¿Cómo encontramos una expresión para \phi^{-1}(m)? Hay varias opciones. Una de ellas es usar nuestro razonamiento inicial para el caso de los cuadrados: encontrar una fórmula circular y empezar a sustituirla dentro de sí misma varias veces. Si lo haces con las potencias de dos, el resultado induce a pensar que la función que buscamos tiene este aspecto:
b_m = m + \Big \lfloor \underbrace{\log_2 \left( m + \log_2 m\right)}_{\phi^{-1}(m)} \Big\rfloor .Ahora solo queda demostrar las hipótesis del teorema con esa expresión de \phi^{-1}(m). Es fácil. La desigualdad del teorema,
2^n-n < \phi(n) \leq 2^n - n + 1 ,
se puede transformar en una equivalente tomando \phi^{-1} en las tres bandas, lo que mantiene el orden ya que es una función creciente y continua:
\phi^{-1}(2^n-n) < n \leq \phi^{-1}(2^n-n+1).
Esta nueva desigualdad es fácil de verificar. Por ejemplo, para la primera parte tenemos que
\phi^{-1}(2^n-n) < n \quad \iff \quad \log_2 \left( 2^n-n + \log_2 (2^n-n)\right) < n .
Cálculos aburridos, pero fáciles, concluyen que la desigualdad es cierta. Y análogo para la otra desigualdad.
Con ella podemos armar la expresión que genera todos los números que no son potencias de dos, ordenados de menor a mayor. Como diría Chatgpt, aquí tienes una fórmula profesional e infalible (100% comprobado) para encontrar los números que no son potencias de dos👍:
b_m = m + \big\lfloor \log_2 \left( m+ \log_2 m\right) \big \rfloor .
Esta fórmula produce el 1 como resultado, aunque no debería (es una potencia de dos, es 2^0). Te dejo a ti pensar por qué ocurre esto. Se puede arreglar desplazando una unidad todos los términos de la sucesión. Es decir, cambiando cada m por m+1.
b_m = m+1 + \Big\lfloor \log_2 \left( m+1+ \log_2 (m+1)\right) \Big \rfloor .
Y ya está todo.
