TARDÍGRADOS

Ciencia en español

Posts Tagged ‘número primo’

El conjunto de los números fantásticamente completos y dónde encontrarlo

Posted by Albert Zotkin en marzo 7, 2018

Se me ha ocurrido una idea sencilla para estudiar los números primos desde perspectivas aún inexploradas. Vayamos al conjunto de los números complejos, y definamos el subconjunto de los números “fantástamente completos” así:

El número complejo z pertenecerá al conjunto de los números “fantástamente completos“, {Fc}, si su parte real es un número primo y su parte imaginaria es un número compuesto, o viceversa, y cumplen las siguientes propiedades:

1. Si la parte real de z es el número primo, p, entonces su parte imaginaria sólo podrá ser uno de estos números compuestos: (p+1) ó (p-1). Con lo cual tendremos cuatro valores diferentes:

\displaystyle  z=p +(p+1)i \\  z=p -(p+1)i \\ z=p -(p-1)i \\ z=p +(p-1)i (1)
2. Si la parte real de z es el número compuesto que dista sólo una unidad de un número primo, entonces tendremos también cuatro posibles números pertenecientes al conjunto Fc:

\displaystyle  z=(p+1)+pi  \\ z=(p+1)-pi  \\ z=(p-1)-pi  \\ z=(p-1)+pi (2)
3.El tercer caso es para los números complejos cuya parte real es un número compuesto, pero el menor primo mayor que él ya no dista una unidad, o el mayor primo menor que él tampoco. Por ejemplo para los complejo cuya parte real es 8, tendremos que el menor primo mayor que él es el 11, y el mayor primo menor que él es el 7: así tendremos los números:

\displaystyle  z=8+11i  \\ z=8-11i  \\ z=8+7i   \\ z=8-7i (3)

O para el 15 de parte real tendríamos:

\displaystyle  z=15 + 17i  \\ z=15 - 17i  \\ z=15 + 13i  \\ z=15 - 13i (4)
Usemos la función cuenta primos π(x). Un número entero positivo, m, es compuesto si π(m) – π(m-1) = 0, y también π(m+1) – π(m) = 0. Por el contrario, si m es primo, entonces π(m) – π(m-1) = 1, y π(m+1) – π(m) = 1. Pero, antes de intentar encontrar una forma cerrada para este último caso de números, debemos preguntarnos, que podríamos hacer con esta clase de números. Ya sabemos que dado un número primo p, podemos definir desde él, al menos, ocho complejos diferentes, los de (1) y (2). Y si tenemos de entrada un compuesto, podemos construir complejos además podrían ser del tercer caso.

Enpecemos a jugar un poco con estos números del conjunto de los “fantástamente completos“, {Fc}. Por ejemplo, seleccionemoss números de la forma m = p -(p-1)i, donde p es primo. Elevemos al cubo ese número m:

\displaystyle  m^3 = -3 p + 6 p^2 - 2 p^3 +  (-1 + 3 p - 2 p^3)i (5)
Observamos claramente que su parte real sólo puede ser un número compuesto o el primo 2, pues es divisible por 2, y su parte imaginaria sí podría ser un número primo, según el valor de p. Además, vemos que sería esa parte imaginaria un número entero negativo. Busquemos que números primos p, producen un número primo en esa parte imaginaria de m. Por mucho que búsquemos, sólo encontraremos el siguiente número complejo:

\displaystyle  m^3 = 2 - 11 i (6)
El cual, claramente, no pertenece al conjunto Fc. Pero, lo curioso de todo esto es siempre obtenemos el número p = 2. Cuando vamos elevando el número m a las sucesivas potencias, obtenemos los siguientes números cubos vuyas partes imaginarias son números primos:

\displaystyle  m = p - (p-1)\,i \\ \\ p=2,\,\, m = 2 - i \\  p=2,\,\, m^3 = 2 - 11\,i \\  p=2,\,\, m^5 =-38-41\,i\\  p=2,\,\, m^7 =-278-29\,i\\  p=2,\,\, m^{11} =2642-6469\,i\\  p=2,\,\, m^{13} =33802-8839\,i\\  p=2,\,\, m^{17} =-24478-873121\,i\\  p=2,\,\, m^{19} =-3565918-2521451\,i (7)
Observamos que sólo las potencias impares dan esos números con parte imaginaria prima. Veamos ahora las potencias pares: Veremos que sólo para m al cubo se obtiene 153 números con sucesivos valores de p, desde el 2 hasta el 7867. Los siguientes dos números obtenidos corresponden a las potencias de 5 y de 9

\displaystyle  m = p - (p-1)\,i \\ \\ p=2,\,\, m = 2 - i \\  p=2,\,\, m^3 = 3-4\,i \\ \\  p=3,\,\, m = 3 - 2\,i \\  p=3,\,\, m^3 = 5-12\,i\\  \cdots \\  p=7687,\,\, m^{3} =15373-118164564\,i\\  p=7867,\,\, m^{3} =15733-123763644\,i\\ \\  p=2,\,\, m^{5} =-7-24\,i\\  p=3,\,\, m^{9} =-239+28560\,i (8)
En resumen, que esta clase de números puede dar un juego bastante bueno, si se investiga un poco. Veamos ahora números de la forma m = p-1 –p i. Obtenemos los siguientes para potencias impares:

\displaystyle  m = p -1 - p\,i \\ \\ p=2,\,\, m = 1 - 2\,i \\  p=2,\,\, m^3 =  -11+2\,i \\  p=2,\,\, m^5 =-41 -38\,i\\  p=2,\,\, m^7 =-29-278\,i\\  p=2,\,\, m^{11} =-6469+2642\,i\\  p=2,\,\, m^{13} =-8839+33802\,i\\  p=2,\,\, m^{17} =-873121 24478\,i\\  p=2,\,\, m^{19} =-2521451-3565918\,i

(9)
Vemos que el complejo p-1 –p i, como es el conjugado de p -(p-1)i, los números obtenidos de sus potencias, también son conjugados de (9).

Nos faltaba aún encontrar una forma cerrada para el tercer caso que expliqué arriba. Es decir, dado un número entero positivo cualquiera, n, ¿cómo construir desde él los númerod fantásticamente completod, m, con sud parted reales igual a n?. La respuesta no sea hace esperar. Primero hay que hallar las partes imaginarias de esos posibles números. Para ello definimos la siguiente función, que llamaremos PrimeComplexBlock, para la cual introducimos el dato inicial n, y nos devolverá el par de números buscado:

\displaystyle   \text{\textbf{PrimeComplexBlock}}(n)= \begin{cases}  \{n - 1,\, n + 1\}    & \small \text{si \textit{n} es primo} \\  \{p(\pi(n)),\, \text{\small{\textbf{NextPrime}}}(n)\} & \small \text{en caso contrario}   \end{cases}

(10)
Es decir, si n es compuesto entonces nos devuelve el par de números {p(π(n)), NextPrime(n)}. El primer número del par nos da el mayor número primo de todos los primos menores que n. Y el segundo número del par, es decir, NextPrime(n)}, como su propio nombre indica, nos da el menor primo de todos los que son mayores a n. Pongamos un ejemplo. Sea n = 10, entonces tenemos:

\displaystyle  p(\pi(10)) = 7,\, \text{\small{\textbf{NextPrime}}}(10)=11
la funcion π(n), es la función cuenta primos, es decir, nos dice cuántos números primos hay menores o igual a n. Y la función p(n) nos da el n-ésimo número primo. Por lo tanto, ambas funciones combinadas, en p(π(n)) nos definen una función que nos da el mayor número primo de los menores a n. Así pues, para n = 10, tendremos todos estos números fantásticamente completos:

\displaystyle 10 - 7  i \\  10 + 7  i \\  10 - 11 i \\ 10 + 11 i
Fijémonos ahora en los números fantásticaente completos de la forma m = p + (p+1)i, donde p son un número primo. Calculemos los cuadrados de esos números m. Sus cuadrados son también números complejos. Seleccionemos de los sucesivos cuadrados, aquellos cuya parte real es un número primo. La sucesión de esas partes reales primas es lo que se llama números primos seguros:

\displaystyle  \text{Re} ((p +(p+1)i)^2) =\\ \\ \{5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, \\ 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, \\ 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, \\ 2063, 2099, 2207, 2447, 2459, 2579, 2819, 2879, 2903, 2963, 2999, \\ 3023, 3119, 3167, 3203, 3467, 3623, 3779, 3803, 3863, 3947, 4007, \\ 4079, 4127, 4139, 4259, 4283, 4547, 4679, 4703, 4787, 4799, 4919, \\ 5087, 5099, 5387, 5399, 5483, 5507, 5639, 5807, 5879, 5927, 5939, \\ 6047, 6599, 6659, 6719, 6779, 6827, 6899, 6983, 7079, 7187, 7247, \\ 7523, 7559, 7607, 7643, 7703, 7727, 7823, 8039, 8147, 8423, 8543, \\ 8699, 8747, 8783, 8819, 8963, 9467, 9587, 9743, 9839, 9887, 10007, \\ 10079, 10103, 10163, 10343, 10463, 10559, 10607, 10667, 10799, 10883, \\ 11003, 11279, 11423, 11483, 11699, 11807, 12107, 12203, 12227, 12263, \\ 12347, 12527, 12539, 12647, 12659, 12899, 12983, 13043, 13103, 13127, \\ 13163, 13523, 13799, 13967, 14087, 14159, 14207, 14243, 14303, 14387, \\ 14423, 14699, 14867, 15083, 15287, 15299, 15383, 15647, 15683, 15767, \\ 15803,\ldots \} (11)
sucesión A005385 en la biblioteca de secuencias OEIS. Como esas partes enteras son los llamados números seguros, resulta que estos números son a su vez números de la forma 2p + 1, donde p es otro primo, que es llamado número primo de Sophie Germain. Es decir, de la lista de arriba (11), restamos la unidad a cada uno de sus números y dividimos por 2, para obteber estos números primos de Sophie Germain:

\displaystyle \frac{\text{Re} ((p +(p+1)i)^2) -1}{2} =\\ \\ \{2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, \\ 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, \\ 683, 719, 743, 761, 809, 911, 953, 1013, 1019, 1031, 1049, 1103, \\ 1223, 1229, 1289, 1409, 1439, 1451, 1481, 1499, 1511, 1559, 1583, \\ 1601, 1733, 1811, 1889, 1901, 1931, 1973, 2003, 2039, 2063, 2069, \\ 2129, 2141, 2273, 2339, 2351, 2393, 2399, 2459, 2543, 2549, 2693, \\ 2699, 2741, 2753, 2819, 2903, 2939, 2963, 2969, 3023, 3299, 3329, \\ 3359, 3389, 3413, 3449, 3491, 3539, 3593, 3623, 3761, 3779, 3803, \\ 3821, 3851, 3863, 3911, 4019, 4073, 4211, 4271, 4349, 4373, 4391, \\ 4409, 4481, 4733, 4793, 4871, 4919, 4943, 5003, 5039, 5051, 5081, \\ 5171, 5231, 5279, 5303, 5333, 5399, 5441, 5501, 5639, 5711, 5741, \\ 5849, 5903, 6053, 6101, 6113, 6131, 6173, 6263, 6269, 6323, 6329, \\ 6449, 6491, 6521, 6551, 6563, 6581, 6761, 6899, 6983, 7043, 7079, \\ 7103, 7121, 7151, 7193, 7211, 7349, 7433, 7541, 7643, 7649, 7691, \\ 7823, 7841, 7883, 7901,\ldots \} (12)
sucesión A005384 en la biblioteca de secuencias OEIS. Estos últimos números primos de la lista (12) se llaman primos Sophie Germain, porque fué la matemática francesa Marie-Sophie Germain la primera en demostrar que el Último teorema de Fermat era cierto para esta clase de números primos.

Un saludo fantásticamente completo 🙂

Anuncios

Posted in Matemáticas | Etiquetado: , , , , , , , , , , , , , , , , , , , | Leave a Comment »

Números casi enteros

Posted by Albert Zotkin en febrero 13, 2018

Hola amigo. Ayer se me ocurrió jugar un poco con los llamados números casi-enteros. Como su propio nombre indica, son números reales que son casi enteros, es decir, que a su parte decimal le sobra o le falta muy poco para ser cero. Por ejemplo el número de Ramanujan:

\displaystyle  e^{\pi {\sqrt {163}}}=262\,537\,412\,640\,768\,743.999\,999\,999\,999\,25\ldots  (1)
Es un casi-entero porque le falta muy poquito para ser 262537412640768744. El problema con esta clase de números reside en su definición, la cual no parece muy matemática. Decir que algo es casi blanco o casi negro, es decir poco, cuando la definición la basamos en el adverbio “casi”. ¿Hasta qué punto un número es casi-entero?. Si el corte lo pusiéramos en que la parte decimal debe empezar por más de veinte 9’s seguidos o por más de veinte 0’s, entonces el número de Ramanujan no sería un casi-entero. Por eso, para resolver ese problema, se me ocurre la siguiente definición: Definamos la sucesión de números casi-enteros Qk, de orden k, de la función F(n) de dominio natural, así:

\displaystyle   Q_k(F(n))=\{ q_n \}_{n\text{,}\,k\in N} (2)
sería una sucesión de números reales, para los que su parte decimal tendría una precisión de k 9’s seguidos, ó de k 0’s seguidos, si expresamos la sucesión en notación de base decimal. Por ejemplo, el número de Ramanujan no estaría en ninguna sucesión de casi-enteros de orden k = 13, ó superior, ya que posee sólo doce 9’s seguidos en sus primeras posiciones decimales. En cambio, sí estaría en una sucesión de orden k = 10, o de grados inferiores. Pongamos un ejemplo: Sea la función de dominio natural siguiente:

\displaystyle   F(n)= e^{\pi {\sqrt {n}}} (3)

y calculemos su sucesión de casi-enteros de grado k = 10:

\displaystyle   Q_{10}( e^{\pi {\sqrt {n}}})= \{q_{58},\,q_{163},\,q_{1467},\,\ldots\} (4)
No sé si esa sucesión es finita o infinita, pero lo que si es fácil de comprobar es que 1467 = 9 × 163, y que esos tres primeros números casi-enteros son exactamente estos:

\displaystyle   q_{58}=e^{\pi \sqrt{58} }= 24591257751.99999982221324\ldots\\ \\   q_{163}=e^{\pi \sqrt{163} }= 262537412640768743.9999999999992500725\dots\\ \\  q_{1467}=e^{\pi \sqrt{1467} }=18095625621654510801615355531263454706630064771074975.9999999901236\ldots
Propongo que el número casi-entero q1467 = 18095625621654510801615355531263454706630064771074975.9999999901…, sea llamado número de Alberti, porque 1467 fue el año en que el criptógrafo León Battista Alberti escribió el tratado De Componendis Cifris, donde describe un disco para encriptar alfabeto, que ahora llamamos disco de Alberti.

Si el grado k de la sucesión Q de casi-enteros lo hubieramos rebajado a k = 6, esa sucesión sería esta:

\displaystyle   Q_{6}( e^{\pi {\sqrt {n}}})=  q_{37},q_{58},\, q_{67},q_{163},\, q_{232},\, q_{719},\, q_{1467},\, q_{4075},\ldots (5)
Todo esto nos debe hacer reflexionar sobre el hecho de que, antes de ponerse a divagar sobre un asunto, es muy importante acotar con una buena definición de qué estamos hablando, y eso es especialmente importante en matemáticas.

Y para terminar de jugar con el tema de los números casi-enteros, definiré ahora otra clase de números, que llamaré casi-enteros Cunningham. Los números casi-enteros Cunningham de base b van a ser números de la forma:

\displaystyle  \frac{\log(b^{n}\pm 1)}{\log(b)}= \log_b(b^{n}\pm 1) (6)
Donde, obviamente b^{n}\pm 1 es un número de Cunningham. Por ejemplo, la sucesión de casi-enteros Mersenne, son números casi-enteros Cunningham de base 2 de la forma:

\displaystyle  \frac{\log(2^{n} - 1)}{\log(2)} = \log_2(2^{n} - 1) (7)
Que es una forma de mapear los exponentes de esos números Mersenne. Por ejemplo, el número primo Mersenne M31 = 2305843009213693951, que fue descubierto por Euler en 1772, genera el casi-entero:

\displaystyle   Q_{31}=\log_2(2^{31} - 1) =30.99999999932819276991073646469478216 \ldots (8)
que, como vemos, se aproxima mucho al exponente 31. Y alguien se preguntará “ok, muy bien, y ¿qué utilidad tiene todo esto?“. La respuesta es fácil, “ninguna, en principio” 🙂 . Pero, si de lo que se trata es de hallar número primos Mersenne, los casi-enteros Cunningham, que he definido arriba, pueden tener mucho que decir, sobre todo si analizamos su partes fraccionales.

Podemos expresar elegantemente la parte fraccional, {Qp}, de un número casi-entero Mersenne Qp así:

\displaystyle  \{Q_p\}=\int_1^p \frac{dx}{2^x-1} (9)

porque es fácil ver que, efectivamente:

\displaystyle  \{Q_p\}=\int_1^p \frac{dx}{2^x-1} = \log_2(2^p - 1) -p+1 (10)

Saludos

Posted in Matemáticas | Etiquetado: , , , , , , , , , , , , , , , , , , , , , , , | Leave a Comment »

Infinitas formas de dividir un número primo

Posted by Albert Zotkin en enero 25, 2018

    Uno de los hechos más asombrosos de dividir un número entero por otro, es que a veces ocurre que ciertos números sólo son divisibles por sí mismos y por la unidad, y los llamamos números primos. Pero, nadie sabe cómo esos números primos se van distribuyendo a lo largo de la sucesión de los números naturales. Ese hecho nos deja perplejos, porque no somos capaces de encontrar ninguna fórmula eficaz ni algoritmo para generar el siguiente número primo. ¿Por que ocurre eso?. Eso ocurre porque nuestra aritmética estándar es sólo una entre infinitas aritméticas posibles. En este pequeño artículo voy a definir algunas de esas aritméticas, que se me han ocurrido, pero siempre teniendo en mente que pueden haber infinitas más, desde otros criterios y perspectivas. Cada aritmética genera su sucesión única de números primos. Empecemos pues:

    Todos sabemos, o deberíamos de saber, que cuando dividimos un número natural por otro, lo podemos interpretar como un método para saber cuántos grupos de cosas se pueden formar, tal que todos los grupos posean el mismo número de ellas. Esa aritmética es básicamente una cuadrícula. Cada columna ( o cada fila) de la cuadrícula es pues un grupo de cosas, y todas tienen el mismo número. Puede ocurrir que la ultima fila o la ultima columna no tenga completas ( llenas) todas sus celdas, eso nos indica que hay un resto distinto a cero en la operación de division. Ahora borremos de nuestra mente esa cuadrícula y exploremos otras posibles formas de dividir un número por otro. Supongamos que, al dividir un número p de manzanas por otro q, lo que queremos es formar q grupos de manzanas y que cada uno contenga un número distinto. En concreto, lo que queremos es que exista una diferencia de una manzana entre los sucesivos grupos, desde el más numeroso al menos.

    Al aplicar ese criterio de división, aunque sería más apropiado hablar de distribución, entramos en el territorio de los números triangulares. Supongamos que tenemos 10 manzanas y queremos saber cuántos grupos podemos formar tal que exista esa diferencia de una unidad entre ellos al considerarlos sucesivamente. Rápidamente vemos que sólo se pueden formar 4 grupos:

    Con los números triangulares podemos definir operaciones de división y multiplicación que escapan ya de la estándar cuadriculada. Con los números triangulares, los distintos grupos que se pueden formar, con la operación de división, difieren en una unidad. En el caso del ejemplo, diremos que 10 manzanas son divisibles por 4, y el grupo más numeroso tiene precisamente 4 manzanas, y el menos numerosos tiene 1. En general, para los números triangulares tendremos que, cualquier número entero positivo p es divisible por otro q, si la siguiente igualdad se cumple:

    \displaystyle p =\frac{q(q+1)}{2}
    Y si obviamos la fórmula podemos indicar la división 10/4 de esta forma:

    \displaystyle  \frac{10}{4} = 4 ,\;\; \text{diff 1}
    que se leerá así: “10 divido por 4 igual a 4, diferencia 1“. El cociente de dividir 10 por 4 es también 4, es decir coincide con el divisor. La sucesión de los números triangulares es la siguiente,

    \displaystyle T_n=\{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136,\dots\} \\ \\  T_n=\{1, 1+2, 1+2+3, 1+2+3+4,1+2+3+4+5,\dots\} \\ \\  T_{n}=\sum _{k=1}^{n}k=1+2+3+\dotsb +n={\frac {n(n+1)}{2}}={n+1 \choose 2},
    Si Tn es el n-ésimo número triangular, entonces podemos decir que es divisible por n diff 1, y el cociente coincide siempre con su divisor:

    \displaystyle \frac{T_n}{n} = n ,\;\; \text{diff 1} \\ \\  T_n = n \times n = \;\; \text{diff 1}
    Veamos ahora qué otros números naturales, que no sean triangulares, son divisibles diff 1. Observamos que el primer número no triangular divisible diff 1 es el 5:

    5 es divisible por 2 diff 1, porque obtenemos dos grupos, uno de 3 manzanas y otro con 2, es decir:

    \displaystyle \frac{5}{2} = 3,\;\; \text{diff 1} \\ \\
    significa que el cociente 3 es el numero de manzanas en el grupo más numeroso, y vemos que 5 no es triangular porque el menor grupo no es la unidad. En seguida nos damos cuenta que los número no triangulares que son divisibles diff 1, son en realidad, fragmentos verticales de números triangulares
    En este caso, el menor número triangular que contiene al 5 es el 6, y el siguiente que lo contiene es el 10:

    El primer número primo diff 1 es el 2, el siguiente será el 4, y el siguiente el 8. Parecería fácil afirmar que todos los número pares que no sean triangulares serían primos diff 1, pero no, no es tan fácil, ya que existen números pares que no son triangulares, pero son divisibles diff 1. Por ejemplo:

    \displaystyle \frac{12}{3} = 5,\;\; \text{diff 1} \\ \\  \frac{18}{4} = 6,\;\; \text{diff 1} \\ \\
    En esta clase de divisiones (o distribuciones) en modo diff 1, el divisor siempre es menor o igual al cociente, nunca mayor. ¿Cómo podemos saber si un número es divisible diff 1. El primer test que ha de pasar el número es comprobar si es triangular:

    \displaystyle n={\frac {{\sqrt {8x+1}}-1}{2}}
    si en la formula de arriba, el número x, que es entero positivo, da como resultado el número n, y además vemos que es también un entero positivo, entonces x es triangular, y por lo tanto es divisible diff 1 por n. El siguiente test es para los número no triangulares. Decía yo antes, que los número no triangulares que son divisibles diff 1, son fragmentos de números triangulares. Eso expresado matemáticamente quiere decir que son la diferencia entre dos dos números triangulares. Por ejemplo, el 12 y 18, que no son triangulares, son divisibles diff 1, por que 12 = 15 – 3, donde 15 y 3 son triangulares. De igual forma 18 = 21 – 3, donde 21 y 3 son triangulares. Por lo tanto el test de divisibilidad diff 1, para los no triangulares, será ver que existen unos números x e y que son triangulares, con:

    \displaystyle y-x=p \\ \\
    con y > x, donde y es el menor número triangular conteniendo al número p. Si p es divisible por q diff 1, entonces

    \displaystyle q={\frac {{\sqrt {8(x+p)+1}}-1}{2}}
    q es el número de grupos que se pueden formar con p. El número de elemento del primer grupo (el más numeroso) será

    \displaystyle \frac{p}{q} = c_1,\;\; \text{diff 1} \\ \\
    y el número de elementos del grupo menos numeroso será:

    \displaystyle c_q=c_1 - q +1
    ¿Existen números primos diff 1?. Veamos. Construyamos una tabla de diferencias para números triangulares hasta el T10 = 55. Al hacer esto sabremos que números son triangulares y que otros son diferencias entre ellos. Por lo tantos, los que no estén en esa tabla deberán ser números primos diff 1.

    Según esta tabla de diferencias, el primer número primo diff 1 es el 16, porque no aparece en ella. El segundo candidato a número primo Diff 1 es el 23. Y los siguientes serían 28, 29, 31, 32, 36, 37, 38, 41, 43, 46, 47, 48, 50, 51, 53. Es decir, tendríamos los primos diff 1 siguientes:

    \displaystyle \{16, 23, 28, 29, 31, 32, 36, 37, 38, 41, 43, 46, 47, 48, 50, 51, 53,\dots\}
    Las celdas de la tabla que he rellenado en color rojo, corresponden a diferencias entre núeros triangulares consecutivos, pero entonces no darían lugar a distribuir en 2 ó más grupos, por lo tanto esos números de la diagonal se desechan. ¿Por qué es el número 16 primo diff 1?. Intentemos formar dos grupos de objetos que sumen 16 pero exista una diferencia de una unidad entre ellos. No se puede porque 16 es número par. Si Formamos dos grupos de 8, y le quitamos 1 a uno de ellos y se lo sumamos al otro tendremos 2 de diferencia, pero estaos en modo diff 1. Por lo tanto, no se pueden formar 2 grupos porque 16 es par. Intentemos formar 3 grupos. Si el primer hrupos tiene 7 objetos, el segundo ha de tener 6, y el tercero 5, pero entonces 7 + 6 + 5 = 18 > 16, no suma 16. Probemos con 5 elementos para el primer grupo. tendremos 5 + 4 + 3 = 12 < 16, tampoco suma 16. Y para las restantes agrupaciones resultan números aún menores. Luego 16 es el primer número primo diff 1. ¿por qué es 23 un número candidato a ser primo diff 1?. En principio , vemos que no es número par, luego podemos formar dos grupos, uno con 11 elementos y el otro con 12. Pero, el número triangular que es divisible diff1 por 2, para dar 12 de cociente, es el 78, es decir, un número mayor al 55, que no lo tenemos tabulado. Por lo tanto, 23 no es primo diff 1, pero sus divisores diff1 dan cocientes mayores a 10, En resumen, 23 es divisible por 2 diff 1, y no tiene más divisores:

    \displaystyle  \frac{23}{2} = 12 ,\;\; \text{diff 1}
    Luego todos los números impares de la lista de candidatos a números primos diff 1, se nos caen de ella porque siempre es posible encontrar para cada uno de ellos un divisor para formar dos grupos de objetos. Luego, los números primos diff 1 han de ser todos pares. Los números impares son todos divisibles por 2 diff 1. Y nuestra lista de números primos diff 1 quedaría asi:

    \displaystyle \{16,  28, 32, 36, 38, 43, 46,  48, 50, \dots\}
    ¿Por qué es 50 un número primo diff 1?. El mínimo número triangular que lo contiene es el 55, que posee 10 grupos, con 10 elementos para el mas numeroso y 1 para el menos numeroso. Pero, no existe ningún número triangular para sustraer tal que dé 50. El que más se le aproxima es el triangular 6 que tiene 3 grupos, pero daría 55 – 6 = 49:

    Los números triangulares pertenecen a una clase de números llamados números poligonales, De esta forma podemos seguir nuestro método de división, y definir qué significa que un número sea divisible diff 2. Se trata de formar grupos que tengan dos unidades de diferencia entre consecutivos, Y así entramos directamente en el territorio de los números cuadrados. Estas divisiones también generan sus números primos, los llamados números primos diff 2. En general, los número poligonales son de la forma

    \displaystyle P(s,n) = \frac{n^2(s-2)-n(s-4)}{2}
    Donde s es el número de lados del polígono. Los números primos estándar, 2,3,5,7,11,…, pertenecen al criterio de divisibilidad diff 0, y teóricamente pertenecerian a la sucesión de números definidos por polígonos de 2 lados, pero eso geométricamente es imposible. Si aplicamos el valor s = 2, a la fórmula, tenemos:

    \displaystyle P(2,n) = \frac{n^2(2-2)-n(2-4)}{2} = \frac{2n}{2}=n
    que es la sucesión de los números naturales, como no podía ser de otra forma. Así, hemos visto, en este pequeño artículo, cómo es posible definir diferentes sucesiones de números primos según el criterio de divisibilidad que apliquemos. Todos los númros primos estándar 2,3,5,7,11,… son divisibles diff 1 excepto el 2, por que son impares. Se me olvidó decir que el número 2 es obviamente el primer número primo diff 1, porque aunque admite dos grupos, la diferencia de sus elementos no es la unidad, sino 0. Y como broche final, un pequeño ejercicio:

    Halla el número de divisores diff 1 del número primo Mersenne que descubrió Euler en 1772. Es decir, tenemos el número primo estándar, diff 0, siguiente:

    \displaystyle M_{31}= 2^{31}-1= 2147483647

    Saludos

Posted in Matemáticas | Etiquetado: , , , , , , , , , , , , , , | Leave a Comment »

Los primeros treinta árboles Mersenne

Posted by Albert Zotkin en enero 20, 2018

Hola, único lector de Tardígrados. Gracias por seguirme. Hoy voy a ir a mi jardín y plantar los primeros treinta árboles Mersenne. Ya sabes que un número Mersenne m es un número entero positivo que posee la forma m = 2n -1, donde n es otro entero positivo. Y ahora, siguiendo el método, ideado por mí, para construir árboles (grafos en forma de árbol) de números primos correspondientes a sus factorizaciones unarias, dibujaré los primeros treinta. Es decir, dibujaré árboles para los números {3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647}. Esta lista escrita desde los exponentes sería asi:

\displaystyle \{ 2^2-1,\;2^3-1,\;2^4-1,\;2^5-1,\;2^6-1,\;2^7-1,\;2^81,\;2^91,\;2^{10}-1,\; \\  2^{11}-1,\;2^{12}-1,\;2^{13}-1,\;2^{14}-1,\;2^{15}-1,\;2^{16}-1,\; \\ 2^{17}-1,\;2^{18}-1,\;2^{19}-1,\;2^{20}-1,\;2^{21}-1,\;2^{22}-1,\; \\ 2^{23}-1,\;2^{24}-1,\;2^{25}-1,\;2^{26}-1,\;2^{27}-1,\;2^{28}-1,\; \\ 2^{29}-1,\;2^{30}-1,\;2^{31}-1 \}
Para aquellos números de esta lista que no sean primos, al dibujar su árbol, sugeriré una continuación hacia la cúspide para culminar con el correspodiente número primo:

He coloreado en verde las extensiones de los árboles que completan los números Mersenne que no son primos, sugiriendo una continuación hacia un número primo, el cual a su vez no tiene por que ser necesariamente Mersenne.

Las etiquetas numéricas de los nodos se pueden obviar (omitir), si el árbol es completo, es decir, si están todos los nodos de la factorización unaria, hasta llegar a los nodos terminales de la unidad. Por ejemplo, el último árbol que he dibujado, que representa el número Mersenne 2147483647, el cual es un número primo, sin las etiquetas numéricas sería así:

Saludos

Posted in Matemáticas | Etiquetado: , , , , , , , , , , | Leave a Comment »

Árboles y bosques: factorización unaria de un número entero

Posted by Albert Zotkin en enero 15, 2018

La factorizaración unaria de un número primo, que me inventé hace tiempo, y que ayer me atreví a escribir en un post, no la encontrarás en ningún libro de texto, ni documento, ni en ningún foro de matemáticas. Y si la empiezas a verla en foros o en referencias, la primera referencia será la mía. Esta factorización da mucho juego, más del que se podía pensar. No sólo sirve para factorizar recursivamente números primos sino números compuestos. De hecho la factorización estándar que vemos en los libros de texto es simplemente una factorización unaria parcial, que sólo llega hasta el segundo nivel dejando los exponentes sin factorizar. Por ejemplo sea el numero compuesto

\displaystyle 2^9 \times 5^{29791}\times 41\times 509 (1)
Vemos que los exponentes no han sido factorizados, ni siquiera de forma estándar. Por lo tanto se trata de una factorización parcial, basica, porque sólo se presenta en los números primos bases de sus respectivas potencias. Una factorización estándar completa sería de esta forma

\displaystyle 2^{3 \times 3} \times 5^{31^3}\times 41 \times 509
Ésta factorización sí es completa, porque todos los números que aparecen son primos, incluso los exponentes, y los exponentes de los exponentes, pero sigue siendo estándar. Aún no es una factorización unaria completa, ya que los distintos números primos que aparecen no han sido recursivamente desintegrados en sus factores primos. La factorización de este número compuesto que he puesto como ejemplo daría no un único árbol, sino 4 árboles, ya que 4 son las bases de la factorización, es decir, {2, 5, 41, 509}. Vemos pues que los números primos se representan unariamente mediante un árbol, y los números compuestos por un bosque. El de ejemplo sería el siguiente:

Vemos que el factor 5 en el nivel 1 se respite 29791 porque está elevado a ese exponente, por lo tanto en el grafo en árbol no puedo dibujar 29791 ves el 5 sin que el dibujo que de mostruosa, monona y ridiculamente largo. Asi la opción es usar puntos suspensivos para indicar esa repetición. Eso significa que sólo en ese nivel los números que se repiten se multiplican, pero en los niveles inferiores no. En el párrafo anterior al gráfico de arriba decía yo que ese número compuesto del ejemplo era un bosque compuesto por 4 árboles. Pero, al observar detenidamente el gráfico, vemos que en realidad está compuesto por 29796 árboles. 3 veces el 2, más 29791 veces el 5, más el 41 y más el 509. También se nos podría ocurrir completar el bosque para construir un único árbol, integrando las bases, pero el resultado no sería único, sino que se presentarían una serie de combinaciones. Veamos cual sería el resultado de una de esas integraciones posibles (dibujaré la más inmediata y obvia):

Donde A y B son dos números primos, pero son demasiado grandes como para incluirlos en el grafo. Es fácil ver que A = P(529791), que 235513 = P(41 x 509), y que 19 = P(8). Con lo cual el número primo B que está en la cúspide del árbol es B = P(19 x A x 235513). En general si un número compuesto se compone de n árboles entonces el número total de número primos que podemos integrar desde el sería n!. En el caso del ejemplo, y si consideramos sólo combinaciones en las que aparecen todos los 5’s en bloque y todos los 2’s bloque tambíen, tendriamos 4 árboles para integrar, con lo que serían permutaciones de 4 elementos, es decir, 4! = 24 números primos diferentes integrados desde el número compuesto inicial. Dibujemos una más de las posibles permutaciones:
En este caso el número primo A posee este valor: A = P(529791 x 41), y 38653 = P(23 x 509), por lo que el número primo B está construido de la siguiente forma: B = P(38653 x A).

Lo increiblemente maravilloso de todo este resultado es saber que existen conjuntos de números primos que están representados por un único número compuesto. Es decir, que desde un número compuesto determinado podemos construir muchos números primos. Muchos números primos poseen las mismas bases, aunque en cada uno aparecen combinadas de diferente forma. Hemos otro caso trivial de integración del número compuesto del ejemplo:

En este ultimo caso, el más trivial de todos, el número primo A esta construido mediante esta combinación de bases: A = P(23 x 529791 x 41 x 509).

Y como detalle final a este pequeño artículo de hoy, decir, que no sólo es interesante elaboran listas de números primos monstruosos, como las de GIMPS, sino también catalogar a cada número primo dentro de la familia a la que pertenece. Y para ello, lo primero que debemos hacer es disponer de una fórmula que nos genere cualquier número compuesto que deseemos. Al igual que tenemos la función P(n) que nos da el n-ésimo número primo, ahora buscamos otra función C(n) generadora que sólo nos de compuestos de la siguiente sucesión:

\displaystyle \{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32,\dots\}
La pregunta ahora es, ¿cuántos números primos desde el número compuesto C(1) = 4 pueden ser construidos con el método que he explicado arriba?. Puesto que 4 = 2 x 2, sólo tenemos una base, el 2. Por lo tanto la respuesta es que sólo podemos construir un único número primo, el P(2) = 3. Veamos ahora el siguiente compuesto, el C(2) = 6. Para ese caso tenemos las bases (2, 3), por los que las opciones combinatorias también son reducidas, pero en este caso podemos construir 2 primos distintos: el P(P(2) x P(3)) = 47 y el P(2 x 3) = 13. Para el siguiente número compuesto, C(3) = 8, tendremos ya tres copias del 2 para empezar. Así podemos construir los siguientes números primos: P(2 x 2 x 2), P(P(2) x 2 x 2), P(P(2) x P(2) x 2), P(P(2) x P(2) x P(2)). Establezcamos un par de normas para la construcción de números primos con este método:

1. todas las bases, repetidas o no deben estar en el mismo nivel de partida. 2. El número de elementos (números primos) obtenidos en cada nivel inmediato superior debe ser menor, nunca igual o mayor, que el del nivel inferior.

Siguiendo estos dos criterios, podemos integrar los casos C(3) = 8 y C(4) = 9:

“A veces los árboles no nos dejan ver el bosque”

Saludos 😉

Posted in Matemáticas | Etiquetado: , , , , , , , , , , , , , | Leave a Comment »

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 🙂

Posted in Matemáticas | Etiquetado: , , , , , , , , , | Leave a Comment »

Cómo romper los códigos criptográficos RSA: factorizacion de semiprimos y las raices rectangulares

Posted by Albert Zotkin en noviembre 18, 2016

riemann-estela
En la actualidad, usamos algunas de las propiedades de los números primos para codificar mensajes, de modo que ningún intruso pueda leer fácilmente nuestras comunicaciones. Para ello usamos la propiedad siguiente de los número semiprimos: Elegimos dos números primos suficientemente grandes, y obtenemos el semiprimo multiplicándolos. El número semiprimo será parte de la llave pública para nuestro método de encriptación, y con los dos números primos se construyen las llaves privadas. Dado un semiprimo suficientemente grande, es prácticamente imposible hallar en tiempo razonablemente corto, sus dos factores primos. Eso es incluso casi intratable usando supercomputadores. esta dificultad se llama Problema RSA.
Si estás interesado en desencriptar los códigos que protegen el acceso a tarjetas de crédito bancarias o a páginas web seguras, quizás estés interesado en participar en esta clase de Competición de factorización RSA. Veamos un semiprimo catalogado por la RSA y que tiene un premio de 100.000 dólares para quien halle sus dos factores primos. Este semiprimo es el RSA1024, es decir, posee 1024 cifras binarias (309 cifras decimales):

\displaystyle \text{RSA}_{1024} = \\ 13506641086599522334960321627880596993888147560566702752448514385152651060 \\ 48595338339402871505719094417982072821644715513736804197039641917430464965 \\ 89274256239341020864383202110372958725762358509643110564073501508187510676 \\ 59462920556368552947521350085287941637732853390610975054433499981115005697 \\ 7236890927563
Si queremos factorizar con éxito un número semiprimo de la RSA, lo primero que debemos hacer es estimar lo grande que serán sus dos factores primos. Así, para ese RSA1024, los dos factores primos estarán muy cerca relativamente de su raíz cuadrada, es decir, números primos cercanos a las 154 cifras decimales, o lo que es lo mismo, números primos de entre 100 y 200 cifras decimales. Por ejemplo, si uno de los primos resulta tener 120 cifras decimales, el otro estaría muy próximo a las 188. Pero, veamos, ¿cuántos números primos hay que tengan entre 100 y 200 cifras decimables?. Usemos la función contador de números primos, p(x), aproximémosla a x/log(x), porque según Gauss, esa es una buena aproximación para un x suficientemente grande. Así los números primos que tienen entre 100 y 200 cifras decimales son aproximadamente :

\displaystyle 2.17 \times 10^{197}
Supongamos que disponemos del superordenador más potente del mundo, el reciente Sunway TaihuLight, capaz de operar a máximo rendimiento, que es de 125.43 petaFLOPS. Conseguiría resolver el número RSA1024 1 petaFlop es 1 opración de coma flotando por cada femtosegundo. 10¹5 femtosegundos son 1 segundo. En total tardaríamos un maximo de :

\displaystyle 2.17 \times 10^{197} \times 10^{-15} = 2.17 \times 10^{182} \; \text{segundos,}
un tiempo demasiado largo como para tener alguna esperanza de llegar en vida hasta el final del cálculo y verlo con nuestros propios ojos 😛

Veamos ahora qué es una raíz rectangular. Cuando calculamos una raíz cuadrada en realidad estamos calculando dos números, pero como ambos son iguales, no nos damos cuenta que en realidad es un par de números. Por ejemplo, la raices cuadradas de 64 son el par (8, 8):

\displaystyle \sqrt{64}=(8,8)
Podemos calcular para 64 su raices rectangulares, ya que si nos fijamos 64 puede escribirse como 2 elevado a diferentes exponentes, es decir:

\displaystyle 64 = 2^6 = 2^3 \times 2^3 =  2^2 \times 2^4 = 2^1 \times 2^5
Es decir, el número 64 posee dos pares de raíces rectangulares y un par de raíces cuadradas:

\displaystyle 64 = (8,8) = (4,16) = (2,32)
Así, para entendernos, pondremos el par de exponentes de las raices rectangulares entre corchetes, de modo que siempre tendremos la equivalencia:

\displaystyle 1 = \left[\frac{3}{6}, \frac{3}{6}\right] = \left[\frac{2}{6}, \frac{4}{6}\right] = \left[\frac{1}{6}, \frac{5}{6}\right]
Con esto, lo único que estamos haciendo es dividir la unidad en dos partes, de modo que su suma sea esa misma unidad. ¿Por qué el número 64 posee esas raices rectangulare y no otras?. En realidad posee muchas más, pero las que he escrito arriba son las que dan raices enteras. Veamos estos casos:

\displaystyle 64 = 64^{\tfrac{1}{4}}\times 64^{\tfrac{3}{4}}= (2\sqrt{2}) (16\sqrt{2}) \\  64 = 64^{\tfrac{1}{5}}\times 64^{\tfrac{4}{5}}= (2\sqrt[5]{2}) (16\sqrt[5]{2^4}) \\
en general, para cualquier par de número enteros m y n, que sean coprimos,tendremos las raices rectangulares de un número N:

\displaystyle N= N^{\tfrac{m}{n}}\times N^{1-\tfrac{m}{n}}
Veamos ahora cómo aplicamos esto a la factorizaación de números RSA: sean los números primos p = 486023 y q = 598727, por lo que su producto es N = 290995092721. Empezaremos nuestros cálculos con su raíz cuadrada:

\displaystyle \sqrt{N}=539439.60989252541168458987732327730802813682656081\ldots
Igualmente sabemos que ha de ser:

\displaystyle p= N^{\tfrac{m}{n}} \\  q= N^{1-\tfrac{m}{n}}

y puesto que sabemos los valores de p y q, es fácil resolver m y n:

\displaystyle \frac{m}{n}=\frac{\log p}{\log(pq)} \\ \\ \\  1-\frac{m}{n}=1-\frac{\log p}{\log(pq)}=\frac{\log q}{\log(N)}
Por otro lado, si pensamos un poquito, nos daremos cuenta de que factorizar un número RSA no es muy difícil en principio, la dificultad reside en que los números primos, p y q, que forman el semiprimo N, sean muy grandes. Así, es incluso posible presentar una ecuación matemática con la que podemos resolver cualquier número RSA, y es esta:

\displaystyle \mathrm{mcd} (N, \lfloor\sqrt{N}\rfloor !)=\min (p,q) (1)
Aquí N es producto de los dos primos p y q, mcd es el máximo común divisor de dos números, \lfloor\ r\rfloor ! es el factorial de la parte entera del número real r. Podemos incluso optimizar un poco esa ecuación (1) si usamos el primorial en lugar del factorial,

\displaystyle \mathrm{mcd} (N, \lfloor\sqrt{N}\rfloor \#)=\min (p,q) (2)
Si N ya es en principio un número muy grande (más de 1024 digitos binarios), el factorial (o el primorial) de la parte entera de su raíz cuadrada será incluso más grande aún, prácticamente intratable. De ahí que las fórmulas (1) y (2) aunque sean correctas, no son muy útiles para el cálculo. En realidad, para calcular un mcd de dos números primero hay que factorizar esos dos números. Es evidente que factorizar N es más fácil que factorizar el primorial de la parte entera de su raíz cuadrada.

Posted in informática, Matemáticas | Etiquetado: , , , , , , , , , , , , , , , , , , , | Leave a Comment »

Números primos: Acotando la conjetura de Gilbreath

Posted by Albert Zotkin en abril 4, 2013

Queridos y amables lectores. Hoy voy a hablar de la conjetura de Gilbreath, la cual aún no ha podido ser resuelta (demostrada). Esta conjetura puede ser formulada como sigue:

Definamos la diferencia entre dos números primos consecutivos asi, d_n \equiv p_{n+1}-p_n y definamos también la diferencia k-ésima, d_n^k como:

\displaystyle   d_n^k \equiv \begin{cases}  d_n    & \text{para k=1} \\   |d_{n-1}^{k-1}-d_{n}^{k-1}| &  \text{para } k > 1 \end{cases}    (1)

N. L. Gilbreath afirmaba que d_{1}^{k}=1 para todo k (Guy 1994). En 1959, dicha afirmación fue verificada para k < 63419. En 1993 Odlyzko extendió la afirmación a todos los números primos hasta \pi(10^{13}).

La conjetura de Gilbreath es equivalente a afirmar que para una disposición triangular de números primos, donde vamos tomando el valor absoluto de la diferencia entre dos términos consecutivos, los primeros términos de cada linea son siempre igual a 1,

\displaystyle   2,3,5,7,11,13,17,19,23,29,... \\ 1,2,2,4,2,4,2,4,6,... \\ 1,0,2,2,2,2,2,2,... \\ 1,2,0,0,0,0,0,... \\ 1,2,0,0,0,0,... \\ 1,2,0,0,0,... \\ 1,2,0,0,... \\ 1,2,0,... \\ 1,2,... \\ 1,...  \\ (2)

Intentemos ahora expresar esas diferencias de forma genérica, sin el valor absoluto, así

\displaystyle   p_1,\ p_2,\ p_3,\ p_4,\ p_5,\ p_6,\ p_7,\ p_8,\ p_9,\ p_{10},... \\ p_2-p_1,\ p_3-p_2\ ,p_4-p_3,\ p_5-p_4,\ p_6-p_7,\ p_8-p_9,\ p_{10}-p_9,... \\ \dots (3)

Se ve claramente que los primeros términos de cada fila de diferencias pueden ser expresados así:

\displaystyle   d_1^k = \sum_{i=0}^k {k \choose i}p_{i+1} (-1)^{k+i} (4)

pero, como digo, eso es sin aplicar el valor absoluto en cada diferencia. Por lo tanto, cuando aplicamos un valor absoluto estamos destruyendo la información sobre el signo.

Veamos ahora el siguiente bonito limite y su notable resultado,

\displaystyle    \lim_{n \to \infty}\sqrt[p_n]{p_n\#} = e  (5)

donde obviamente p_n es el n-ésimo número primo, p_n\# es el primorial de pn, y e es el número de Euler (base de los logaritmos naturales).

Estudiemos por lo tanto un poco la función

\displaystyle   F(n)=\sqrt[p_n]{p_n\#}  (6)

cuyo plot es este, observando también cómo converge asintóticamente hacia número e,

Tomenos ahora el logaritmo natural a ambos lados de (6),

\displaystyle   \ln F(n)= \ln \sqrt[p_n]{p_n\#}  \\ \\  \ln F(n) = \cfrac{\ln p_n\#}{p_n}   \\ \\  \ln F(n) = \cfrac{1}{p_n}\sum_{k=1}^n \ln p_k  \\ \\  (7)

esto significa que

\displaystyle   \lim_{n \to \infty} \ln F(n) = 1  (8)

y esto nos sugiere que podemos definir una nueva función G(x) tal que

\displaystyle   p_n = \sum_{k=1}^n G(k) (9)

tendriamos pues que los primeros valores de G serían,

\displaystyle   G(1)=3,\ G(2)=2,\ G(3)=2,\ G(4)=4,\ G(5)=2, \dots (10)

ya que, según la definición de G, debe ser,

\displaystyle  G(1) = 3 \\ G(1) +G(2) = 5 \\  G(1) + G(2) + G(3) = 7 \\  G(1) + G(2) + G(3) + G(4) = 11 \\  G(1) + G(2) + G(3) + G(4) +G(5) = 13   \dots (11)

vemos que la función G se define como la diferencia de dos números primos consecutivos,

\displaystyle   p_n = G(n) + p_{n-1} \dots (12)

y por lo tanto tiene mucho que ver con la conjetura de Gilbreath, y con las funciones de Chebyshev.

Posted in Matemáticas | Etiquetado: , , , , , , , | Leave a Comment »

La función Gamma Γ (x) entra en juego: otra fórmula más que genera números primos

Posted by Albert Zotkin en febrero 26, 2013

La siguiente función, basada en el teorema de Wilson, la cual asigna la unidad si n es número primo y cero si no lo es

\displaystyle F(n)=\left \lfloor \cos^2 \left ( \cfrac{(n-1)! +1}{n}\right ) \right \rfloor = \begin{cases} 1 & \small \text{si \textit{n}=1 \'o \textit{n} es primo} \\ 0 & \small \text{en caso contrario} \end{cases} (1)
me abrió los ojos. En realidad, (n-1)! no es más que la función Gamma, \Gamma, Es decir:

\displaystyle \Gamma(n) = (n-1)! (2)
Con lo cual (1) también puede expresarse así:

\displaystyle F(n)=\left \lfloor \cos^2 \left ( \cfrac{\Gamma (n) +1}{n}\right ) \right \rfloor = \begin{cases} 1 & \small \text{si \textit{n}=1 \'o \textit{n} es primo} \\ 0 & \small \text{en caso contrario} \end{cases} (3)

Pero, la cosa no quedó ahí. Al final, observando un poquito, y haciendo algunas pruebas, pude construir esta otra función, que funciona para n\ge 5 :

\displaystyle \boxed{Q(x)=\text{frac} \left (\cfrac{\Gamma(x)}{x} \right )\cfrac{x^2}{x-1}= \begin{cases} x & \small \text{si \textit{x} es primo} \\ 0 & \small \text{en caso contrario} \end{cases}} (4)
donde \text{frac} es la función parte fraccionaria. Esta función Q(x) tiene dos excepciones, en el intervalo 0<x<5:

\displaystyle Q(1)=\infty,\ Q(4)=\frac{8}{3} (5)

ya que los casos Q(2)=2 y Q(3)=3 sí cumplen la definición.

Parecería sorprendente que esta simple función Q(x), la cual mapea tan perfectamente los números primos, sea otra primicia mía, y por lo tanto no me queda otra opción que buscar referencias en la literatura de la historia de las matemáticas, para que nadie me pueda endosar a mi la autoría de tan trivial hallazgo.

Quien aún no esté del todo convencido de que Q(x) funciona puede usar el programa Mathematica, por ejemplo, para computar lo siguiente:

Teorema: Para todo entero n > 0, con n ? 1 y n ? 4, si n no es primo, entonces G(n) es divisible por n. Lo cual implica que si n es primo, entonces G(n) no es divisible por n:

\displaystyle \small \text{si \textit{n} no es primo, entonces}\\ \\ \Gamma (n) \equiv 0 \pmod n (6)

Posted in Matemáticas | Etiquetado: , , , , , , | 2 Comments »

Una fórmula que calcula el n-ésimo número primo

Posted by Albert Zotkin en febrero 25, 2013

El Teorema de Wilson dice que si p es un número primo, entonces (p-1)! + 1 es múltiplo de p. Es decir:

\displaystyle (p-1)! \equiv -1 \mod{p} (1)

Basándomos en este teorema es posible construir una función tal que:

\displaystyle F(n)=\left \lfloor \cos^2 \left (\pi \cfrac{(n-1)! +1}{n}\right )  \right \rfloor = \begin{cases} 1    & \small \text{si \textit{n}=1 \'o \textit{n} es primo} \\ 0 & \small \text{en caso contrario} \end{cases}  (2)
donde \lfloor x \rfloor es la función suelo. Pero, es precisamente esta función suelo lo que menos me gusta de esta fórmula (2). Por lo tanto, la pregunta es si es posible modificar esa función (2) tal que no aparezca ningún tipo de función suelo o función techo. La respuesta es sí. Fijémonos en la siguiente función, para n \ge 1:

\displaystyle G(n)=\sin^2 \left (\pi \cfrac{(n-1)! +1}{n} \right )  = \begin{cases} \sin^2 (\frac{\pi}{n})    & \small \text{si \textit{n} no es primo} \\ 0 & \small \text{si \textit{n} es primo} \end{cases}  (3)
Es decir, para n \ge 1 la función G(n) nos da la secuencia

\displaystyle  G(n)= \left \{0,\ 0,\ 0,\ \cfrac{1}{2},\ 0,\ \cfrac{1}{4},\ 0,\ \sin^2\left(\cfrac{\pi }{8}\right),\ \sin^2\left(\cfrac{\pi }{9}\right),\ \cfrac{1}{16} \left(-1+\sqrt{5}\right)^2, \ \dots \right \} (4)
Por lo tanto, sólo tenemos que dividir G(n) por \sin^2 \pi/n , para obtener :

\displaystyle H(n)=\cfrac{\sin^2 \left ( \pi \cfrac{(n-1)! +1}{n} \right )}{\sin^2 \frac{\pi}{n}}  = \begin{cases} 1    & \small \text{si \textit{n} no es primo} \\ 0 & \small \text{si \textit{n} es primo} \end{cases}  (5)

Es decir, ya que para n=1 da indeterminado, para n \ge 2 la función H(n) nos da la secuencia

\displaystyle H(n)= \left \{0,\ 0,\ 1,\ 0,\ 1,\ 0,\ 1,\ 1,\ 1, \ \dots \right \} (6)

Pero si lo que estamos buscando es la función

\displaystyle  P(n)= \begin{cases} 0    & \small \text{si \textit{n} no es primo} \\ 1 & \small \text{si \textit{n} es primo} \end{cases}  (7)

Sólo tenemos que establecerla como complementaria de H(n):

\displaystyle  \boxed {P(n)= 1- H(n) = 1 - \cfrac{\sin^2 \left (\pi \cfrac{(n-1)! +1}{n} \right )}{\sin^2 \frac{\pi}{n}}} (8)

con lo cual hemos obtenido una función similar a F(n), pero sin la función suelo.


Algunos consejos para su uso en Mathematica

Define la función que genera la lista (cero si no es número primo), por ejemplo esta función :
  

In[1]:=

Define ahora la función que quitará los ceros, por ejemplo esta :

In[2]:=

Veamos ahora algunos ejemplos. Primero veamos cómo la función F[x] genera una lista de números primos :

In[3]:=

Out[3]=

Veamos ahora un ejemplo de cómo la función P[x] quita los ceros . Pero, antes de eso quiero advertir que la función P[x] es muy ineficiente para esa tarea (tarda mucho) y sólo debe ser considerada como una curiosidad matemática, nada más. Aconsejo no usarla en calculos prácticos con Mathematica. Por lo tanto, como muestra, sólo la usaré para un cálculo hasta n=10:

In[4]:=

Out[4]=

Para quien posea curiosidad por saber cúanto tiempo tarda Mathematica en hacer esta última tarea, haré lo siguiente :

In[5]:=

Out[5]=

Lo cual significa que esta última operación ha tardado unos 20 segundos en realizarse (una velocidad muy pobre si tenemos en cuenta que sólo calculó hasta n = 10).

Pero, si aún deseamos quitar eficientemente los ceros a la lista que genera la función F[x], podemos usar el algoritmo Deletecases, así:

In[6]:=

Out[6]=

Otros ejemplos de funciones generadoras:

In[9]:=

In[11]:=

Out[11]=

In[12]:=

In[13]:=

Out[13]=

Posted in Matemáticas | Etiquetado: , , , , | 4 Comments »

 
A %d blogueros les gusta esto: