TARDÍGRADOS

Ciencia en español

Factorización unaria de un número primo

Posted by Albert Zotkin en enero 13, 2018

Todos sabemos que un número entero puede ser descompuesto (factorización ) en sus factores primos, y hay mucha literatura al respecto. Pero, ahora podemos hacer la siguiente pregunta: ¿y un número primo?, ¿puede ser factorizado o descompuesto de alguna forma?. La respuesta es sí. fijémonos en la sucesión de números primos

\displaystyle \{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113, \dots\} (1)
el 2 es el primer número primo, el 3 es el segundo, etc. De esa forma todo número primo puede ser etiquetado según el orden que ocupa en esa sucesión. Consideremos ahora la función P(n) que nos da el n-ésimo número primo de esa sucesión. Por ejemplo P(1) = 2. Esto significa que cuando nos encontremos con un número que no sea primo procederemos a factorizarlo normalmente, y si es primo anidaremos la función P dentro de sí misma tantas veces como sea necesario hasta dar con un no primo o hasta que lleguemos al primer elemento de la sucesión. Es fácil ver, que el número primo 3, el cual es el segundo de la sucesión puede ser expresado unariamente de esta forma:

\displaystyle 3 = P(2)= P(P(1))
De igual forma con el número 5. Sabemos que es el tercer elemento de la sucesión, por lo tanto, aplicamos la función P reiteradamente y tenemos:

\displaystyle 5 = P(3) = P(P(2))= P(P(P(1)))
Como he dicho antes, se presentarán casos en los que el ordinal del número primo no sea a su vez un número primo. En tal caso la función P quedará multiplicada, no anidada. Veamos el siguiente número. El número 7 es el cuarto número primo de la sucesión, por lo tanto tendremos:

\displaystyle 7 = P(4) = P(2 \times 2) = P(P(1) \times P(1))
Podemos incluso economizar aún más la factorización unaria y obviar los caracteres P y 1, y dejar sólo los parentesis para visualizar el anidamiento. Con lo cual tendríamos la equivalencia:

\displaystyle 7 \equiv  (()())
Elijamos ahora números primos grandes. Sea por ejemplo, el número primo más largo que conoce hasta ahora. Vamos a intentar factorizarlo unariamente. Ese número perteneces a una clase de número primos llama primos Mersenne .

\displaystyle 2^{77232917} -1
el cual posee exactamente 23249425 cifras decimales. Para empezar, vemos ya de entrada que el exponente 77232917 es a su vez un número primo. y el proceso hacia su factorización unaria es el siguiente:

\displaystyle 77232917 = P(4517402) = P(2 \times 19 \times 53 \times 2243) \\ \\  77232917 = P(P(1) \times P(P(1)^3) \times P(P(1)^4) \times P(P(1) \times P(167))) \\ \\  77232917 = P(P(1) \times P(P(1)^3) \times P(P(1)^4) \times P(P(1) \times P(P(P(3)) \times P(P(2) \times P(3))))) \\ \\  77232917 = P(P(1) \times P(P(1)^3) \times P(P(1)^4) \times P(P(1) \times P(P(P(P(2))) \times P(P(2) \times P(P(2)))))) \\ \\  77232917 = P(P(1) \times P(P(1)^3) \times P(P(1)^4) \times P(P(1) \times P(P(P(P(P(1)))) \times P(P(P(1)) \times P(P(P(1)))))))

Y si simplificamos borrando la P y el 1, podemos escribirlo sólo con los paréntesis así:

\displaystyle 77232917 \equiv (()(()()())(()()()())(()((((())))((())((()))))))
En general, podemos incluso codificar los paréntesis de forma binaria mediante unos y ceros. Así, el paréntesis de apertura “(” podría ser escrito como un 1 y el paréntesis de cierre como un 0. Para el número anterior la codificación binaria sería:

\displaystyle 77232917 \equiv 110110101001101010100110111110000111001110000000  \\ \\
Las reglas de escritura para construir un número primo con esta codificación binaria son simples.

1. Se debe empezar siempre por un 1, nunca por 0. 2. Debe haber tantos unos como ceros. 3. Se debe finalizar siempre con un 0.
Escribamos ahora los primeros números primos de la sucesión de número primos con esta codificación binaria:

\displaystyle 2  \;\;\equiv 10 \\  3  \;\;\equiv 1100 \\  5  \;\;\equiv 111000 \\  7  \;\;\equiv 110100 \\  11 \equiv 11110000 \\  13 \equiv 11011000 \\ 17 \equiv 11101000 \\ 19 \equiv 11010100 \\ 23 \equiv 1110011000 \\ 29 \equiv 1101110000 \\ 31 \equiv 1111100000 \\ 37 \equiv 1101011000 \\ 41 \equiv 1110110000 \\ 43 \equiv 1101101000 \\ 47 \equiv 111001110000 \\  53 \equiv 1101010100 \\ 59 \equiv 1111010000 \\ 61 \equiv 110110011000 \\ 67 \equiv 1110101000 \\ 71 \equiv 1101110001110000 \\ 73 \equiv 111001101000 \\ \cdots

Pero surge un pequeño problema. Por ejemplo, el número 13 puede ser codificado de dos formas distintas:

\displaystyle 13 \equiv 11011000 \\ 13 \equiv 11100100
ya que en realidad estamos considerando P(13) = P(2 x 3) = P(3 x 2) = P(P(1) x P(2)) = P(P(2) x P(3)), y debido a que se cumple la propiedad conmutativa del producto de dos números. Por lo tanto, nos hace falta una nueva regla de escritura: hay que ordenar los productos de forma que los factores mayores estén a la izquierda.

La factorización unaria de los números primos puede ser vista como una especie de producto, de tal forma que podemos decir que todo número primo puede escribirse como producto de primos menores que él, y ese producto es único.

Fijémonos ahora en una clase de números primos, aquellos cuya representación binaria nos da todos los unos a la izquierda y todos los ceros a la derecha. Es decir, tenemos la sucesión:

\displaystyle 2  \;\;\equiv 10 \\  3  \;\;\equiv 1100 \\  5  \;\;\equiv 111000 \\  11 \equiv 11110000 \\  31 \equiv 1111100000 \\  127 \equiv 111111000000 \\ 709 \equiv 11111110000000 \\ 5381\equiv 1111111100000000 \\ 52711\equiv 111111111000000000 \\\cdots

esta sucesión esta relacionada con los números Matula-Goebel, y está catalogada en la enciclopedia OEIS con el link A007097

Pero, volvamos al número primo 77232917. La factorización unaria, es pues un proceso computacional, y puede ser presentado en árbol. Para este número en concreto tendremos el árbol siguiente:

En los nodos terminal del gravo siempre debe aparecer el número 1, en todos los demás nodos aparecen números primos. Cada arista del grafo que une dos nodos de diferentes niveles representa una computación con la función P(n) = m. Es decir, m estará arriba en el árbol y n estará en el nivel inmediato siguiente. Las bifurcaciones se producen allí donde un número no es primo. Por ejemplo el 2243 es primo, pero su ordinal, 334, no es un número primo, es decir, tenemos que P(334) = 2243 , y a su vez 334 = 2 x 167, con lo cual en el árbol aparece 2243 bifurcado hacia 2 y hacia 167. Los números primos que presentan un árbol lineal, es decir, sin ramificaciones, son pues los que se obtienen por la iteración directa P(P(P(P(P(P(P(…))))))). Esa sucesión especial de números primos relacionada con los números Matula-Goebel, y está catalogada en la enciclopedia OEIS con el link A007097

Los llamados números Mersenne, que he presentado arriba, y sabemos que son de la forma 2n – 1, resultan en primos Mersenne si y sólo si el exponente n es primo. Con lo cual puede darse el caso, y de hecho se dan infinitos, que aun siendo n primo no da un primo Mersenne. Los casos triviales de exponentes que no dan primos Mersenne es pues el conjunto de los números compuestos. En otras palabras, si n es compuesto entonces 2n – 1 no es primo. Ahora cabe la pregunta siguiente: ¿Tienen algo de peculiar las factorizaciones unarias (árbol) de los primos Mersenne. Un número Mersenne expresado en sistema binario sólo posee unos, es un número repunit, del que ya hablé en otra ocasión. Construyamos algunos árboles para los primeros primos Mersenne, y veamos si somos capaces de apreciar similitudes. Empecemos por los cuatro primeros, los cuales fueron descubiertos por Euclides, que son 3, 7, 31, 127:

No perdamos tiempo y dibujemos los árboles a mano alzada para los tres primos Mersenne siguientes. El primero es 8191, es anónimo del año 1456, los dos siguientes son 131071 y 524287 de Pietro Cataldi 1588:

La función contador de números primos, p(n), es la inversa de la función P(n). Fijémonos ahora en el primo Mersenne 127, el último que descubrió Euclides. Es el primer número de los primos Mersenne cuyo ordinal es también un primo Mersenne. El ordinal de 127 es 31. Es decir:

\displaystyle 127  = P(31) \\ \\ 127 = 2^7 - 1 \\ \\  31 = 2^5 -1  \\ \\ 2^7 - 1 = P( 2^5 -1) \\ \\ 2^5 - 1 = \pi( 2^7 -1)

En general tenemos que

\displaystyle y  = \frac{\log(\pi(2^x-1)+1)}{\log 2} \\ \\ \\ x  = \frac{\log(P(2^y-1)+1)}{\log 2}
donde y es el exponente de un primo Mersenne, cuyo ordinal es también primo Mersenne, con exponente x. ¿Cuál es el siguiente primo Mersenne con esa característica?. Es decir: ¿Qué número primo Mersenne mayor que 127 es el primero que cumple la relación de que su ordinal sea también primo Mersenne?. Quien dé la respuesta correcta recibirá como premio un jamón pata negra. Os puedo asegurar que ese número existe.

Saludos unarios a todos 🙂

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

 
A %d blogueros les gusta esto: