Publicado por

Curiosidad sobre el codigo binario

Una curiosidad sobre la representación binaria de los números perfectos

Posted By  on 16 de abril de 2013 in Álgebra y Matemática discreta, Números enteros, Números primos.
En ocasiones nos encontramos con que algunas características de ciertos tipos de números son realmente sorprendentes, casi místicas en algunos casos. Pero no podemos dejar que ese aparente misticismo nos nuble la vista, ya que eso que parece tan sorprendente quizás sea algo relativamente evidente que no acertamos a ver, puede que por estar poseídos por esa sorpresa.

Los números perfectos son uno de esos tipos de números que poseen características sorprendentes. Para empezar, su propia definición los eleva a una categoría acorde con su propia denominación:
Un número entero positivo N es un número perfecto si la suma de todos sus divisores (excluyéndolo a él mismo) es igual al propio N.
Ejemplos de números perfectos son los siguientes:
\begin{matrix}6=1+2+3 \\ 28=1+2+4+7+14 \\ 496=1+2+4+8+16+31+62+124+248 \end{matrix}
que son los tres más pequeños.
Hay dos cuestiones interesantes sobre los números perfectos que actualmente siguen sin respuesta. Son las siguientes:
  • ¿Existen infinitos números perfectos?
  • ¿Existen números perfectos impares?
Sobre la segunda pregunta, solamente se conocen propiedades que deberían cumplir si en realidad existieran relacionadas con el número de factores que deberían tener o sobre la cantidad de dígitos de dichos factores (aquí se demostró un resultado relacionado con ellos).
Y sobre la primera, sabemos algo pero no demasiado. No sabemos si hay infinitos números perfectos, pero sí sabemos cómo son exactamente los números perfectos pares. Se sabe (gracias, a partes iguales, a Euclides y a Euler) que hay una relación biunívoca entre los números perfectos pares y los primos de Mersenne (que recordemos que son primos de la forma 2^p-1, con p un número primo). Es decir, sabemos que cada número perfecto par corresponde con un primo de Mersenne, y viceversa de la siguiente forma:
Si 2^p-1 es un número primo, entonces 2^{p-1} \cdot (2^p-1) es un número perfecto.
Por tanto a día de hoy se conocen 48 números perfectos (uno por cada primo de Mersenne que conocemos). Por ejemplo, los tres anteriores corresponden a los siguientes primos de Mersenne:
  • Para p=2 obtenemos el primo de Mersenne 2^2-1=3, y el número perfecto 2^{2-1} \cdot (2^2-1)=6.
  • Para p=3 obtenemos el primo de Mersenne 2^3-1=7, y el número perfecto 2^{3-1} \cdot (2^3-1)=28.
  • Para p=5 obtenemos el primo de Mersenne 2^5-1=31, y el número perfecto 2^{5-1} \cdot (2^5-1)=496.
Como podemos ver, los números perfectos tienen una definición y unas propiedades ciertamente curiosas y, hasta cierto punto, sorprendentes (esta relación con los primos de Mersenne es, para mí, cautivadora por lo inesperado de la misma), pero no todo lo que está relacionado con ellos debe ser necesariamente «inexplicable». Veamos un ejemplo.
Hace unos días se publicaba en Futility Closet el post Brothers in Binary, en el que aparecía esta tabla con la representación binaria de los primeros ocho números perfectos:
En ella se puede ver que la representación binaria de dichos números perfectos es muy especial, ya que en todos los casos aparecen una cierta cantidad de unos seguidos de otra cierta cantidad de ceros. Además, en todos los casos la cantidad de unos es un número primo y la cantidad de ceros es un número par. ¿Esto es siempre así? Y, en ese caso, ¿tiene algún tipo de explicación?
Pues sí, es así siempre que el número perfecto sea par. Y sí, tiene explicación. Y, como ya habréis adivinado, tiene que ver con la correspondencia de los números perfectos pares con los primos de Mersenne.
Tomemos un número perfecto par cualquiera, K. Por la correspondencia con los primos de Mersenne, debe existir un número primo p tal que 2^p-1 es un número primo y además K=2^{p-1} \cdot (2^p-1). Por otro lado, se puede demostrar fácilmente por inducción que si n es un número entero positivo, entonces
2^n-1=1+2+ \ldots +2^{n-1}
por lo que tenemos que
K=2^{p-1} \cdot (1+2+\ldots +2^{p-1})
Realizando la multiplicación obtenemos la expresión de K como suma de potencias de 2:
K=2^{p-1}+2^p+ \ldots 2^{2p-2}
¿Qué nos dice esta representación? Pues un par de cosas:
  • La primera es que las potencias de 2 menores que 2^{p-1} no aparecen en ella, por lo que en la representación binaria darán ceros. ¿Cuántos habrá? Pues exactamente p-1, que es un número par de ceros.
  • Y la segunda es que hay p potencias de 2 consecutivas que aparecen en esa expresión, que por tanto corresponderán con p unos consecutivos en la representación binaria.
¿Qué significa todo esto? Pues que a partir de la correspondencia biunívoca entre los números perfectos pares y los primos de Mersenne no es para nada sorprendente que la representación binaria de los números perfectos pares tenga siempre la estructura siguiente
K=\underbrace{ 1 \ldots 1 }_{p} \underbrace{ 0 \ldots 0}_{p-1}
sino más bien que es evidente que debe ser así.
Una consecuencia de todo esto es que, aunque no nos vale a encontrar números perfectos pares, esta propiedad nos podría servir para descartar que un número entero sea un número perfecto par: calculamos su representación binaria y si no es un número primo de unos seguidos de un número par de ceros entonces ya sabemos que el número en cuestión no es un número perfecto par. Cierto es que no es de mucha ayuda, pero algo es algo, ¿no?

Comentarios

Publicar un comentario

Entradas populares