Posible descubrimiento del primo de Mersenne número 45

El día 23 de agosto el grupo GIMPS recibió el aviso del descubrimiento de un nuevo primo de Mersenne, número que todavía no han hecho público. Los primos de Mersenne (como ya vimos en posible descubrimiento del 44) son los números primos de la forma 2^n-1, con n un número primo. El mayor conocido hasta ahora es precisamente el número 44:

2^{32582657}-1

Éste rozó los 10 millones de cifras (concretamente 9808358), y se esperaba que el próximo en ser encontrado las superara. Pues tendremos que esperar unos días, al parecer unas dos semanas, para 1) que se verifique que el número encontrado es primo; y 2) en ese caso saber el número de cifras.

En God Plays Dice, sitio donde he visto la noticia, han publicado su predicción sobre el número de cifras y, aunque está ciertamente fundamentada, a mí me parece muy grande. Paso a explicarla:

Según la enciclopedia de las sucesiones, el número de primos de Mersenne hasta el de exponente N es aproximadamente K \; \log(N), para cierta constante K.

En el caso de primo de Mersenne número 44, 44 \approx K \; \log(32582657). Despejando obtenemos K=2,5434. Utilizando ese valor de K para el primo de Mersenne número 45 obtendríamos que tiene ¡¡14,5 millones de cifras!!.

Lo que he dicho antes, me parece demasiado.

De todas formas habrá que estar atentos a las noticias sobre el tema en los próximos días.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

30 Comentarios

  1. Es una predicción un poco ad-hoc, ¿no te parece? La expresión K \log(n) es asintótica, obtener K a partir de un único valor es bastante… digamos audaz 😀

    Lo que sí es casi seguro es que pasará los 10 millones de cifras. ¿Había un premio para el que consiguiera eso, verdad?

    Publica una respuesta
  2. ¿Este tipo de descubrimientos cómo se llevan a cabo? ¿Utilizando súper-ordenadores que van verificando todas las posibilidades, o hay métodos para cercar un poco los posibles números?

    Publica una respuesta
  3. Parece que los ordenadores lo pueden todo pero este número es gigantesco. Si no he cometido errores para almacenar este número se decesitarían 3,8 Mb. Puede parecer poco pero es que lo normal para expresar un número entero es de 4 a 8 bytes (en terminos generales).
    Teniendo en cuenta que los ordenadores trabajan con un tamaño de palabra de 64 bits (8 bytes) y que una división (dependiendo del procesador) puede llevar entre 20 y 30 ciclos de reloj. Para hacer una simple operación con este número necesitaría una friolera de 25 millones de ciclos de reloj…. Y esto una operación. En hacer la potencia tardarían aproximadamente 814 billones de clilos. Hoy en día hay superordenadores que pueden hacer operaciones en paralelo, en diferentes núcleos, con unidades de operación mejoradas … y aún así tardan varias semanas.
    Es obvio que no prueban número a número. No soy matemático pero seguro que lo acotan de cierta forma… los ordenadores operan, las personas piensan…

    Publica una respuesta
  4. El tamaño de las palabras, Alfredo, sigue siendo 16 bits desde hace bastantes años. Lo que tanto oímos y vemos en nuestros ordenadores de 32 o 64 bits no hacen referencia a la longitud de palabras que usan, sino a la longitud de los conjuntos de palabras que suelen usar.

    Es decir, un procesador de arquitectura x86-64 tiene una longitud de palabra de 16 bits. Sin embargo, suele usar operandos de 64 bits (cuadrupe-palabra).

    Un saludo!

    Publica una respuesta
  5. Alfredo debe ocupar más de 3,8 MB. El anterior, el 44, ocupaba 9,4 MB en un txt (se puede ver en el enlace del número 44 que hay en este post).

    Por otra parte, trabajan a través de la gente. Te bajas un programa, lo instalas y él mismo va ejecutando un test de primalidad para este tipo de número. Para más información:

    GIMPS: cómo trabajamos

    Publica una respuesta
  6. He hecho una prueba de un archivo de 14.500.000 digitos, en txt, y ocupa 13,8 megas.
    Salud

    Publica una respuesta
  7. Hmmm… No es seguro de que vaya a ser el 45. Existe la probabilidad de que sea menor que el 44; no han comprobado todavía todas las posibilidades entre el 39 y el 44, están todavía en ello. Entonces habría que revisar las listas.

    Publica una respuesta
  8. edmon: tu prueba es de un archivo de texto con un número decimal (cada cifra decimal: 1 byte). Pero los ordenadores trabajan en binario, y es así como guardan los números.

    Una aceptable aproximación es:

    3 dígitos decimales = 10 dígitos binarios.

    Es decir, el número que has obtenido se debe multiplicar por 10/3 para obtener el número de dígitos binarios aproximado, y después dividir el resultado por 8, para obtener el número de bytes.

    Pablo Reyes: Depende.

    En rigor, Alfredo tiene razón, lo que sucede es que el uso ha hecho que algunos informáticos ya relacionen la palabra con los 16 bits, y en muchos contextos se toma así. Pero rigurosamente hablando, y en este contexto técnicamente creo que también, Alfredo ha usado el término con más corrección.

    Una prueba de ello es que en el lenguaje C se define el tipo int como un entero con signo del tamaño de una palabra (sin especificar un número de bits concreto).

    Cuando aparecieron las versiones de Windows de 32 bits, Microsoft modificó su compilador de C para cumplir esta condición, y el tipo int pasó de tener 16 a 32 bits. Sin embargo el SDK de Windows definió el tipo WORD como entero de 16 bits.

    Con las versiones de 64 bits, Microsoft decidió no seguir en rigor lo establecido para el lenguaje C, y anunció que el tipo entero se quedaría en 32 bits, porque acertadamente (creo) pensaron que no hacerlo así crearía más problemas de los que arreglaría.

    Publica una respuesta
  9. Según mi aproximación, salen unos 6 megas para 14.5 millones de cifras decimales. Pero es más que probable que la aproximación no sea tan aceptable con números de semejante magnitud.

    Publica una respuesta
  10. edmon, bastaría con que hubieras dividido la cifra entre 1024 para obtener los KB y otra vez entre 1024 para obtener los MB. 😉

    Publica una respuesta
  11. De hecho ese 1024 del que habla Asier es el origen de la aproximación de la que hablaba, ya que 2^10 (10 dígitos binarios) es 1024, que es aproximado a 10^3 (3 dígitos decimales).

    Y por esto también en informática 1K son 1024 bytes y no 1000 bytes.

    Publica una respuesta
  12. ‘los ordenadores operan, las personas piensan…’

    Totalmente de acuerdo y hasta que no se progrese lo suficiente en Inteligencia Computacional (que se diferencia bastante de la artificial) como para que una maquina pueda pensar mejor que una persona seguire pensando que esta clase de demostraciones de ‘fuerza bruta’ son innecesarias.

    Publica una respuesta
  13. Como tantos otros yo también participo de la búsqueda de los nuevos números primos de Mersenne. Dicha búsqueda se realiza mediante el sistema de computación distribuida, como aclaró DiAmOnD. Miles de ordenadores comunes y corrientes se distribuyen la titánica tarea y a cada uno le tocará en suerte la dicha de descubrir un nuevo número primo de Mersenne o sino por lo menos el consuelo de haber participado de esta silenciosa aventura.

    Publica una respuesta
  14. Si cuando te venden un disco duro de 250 GB resulta que tiene 250.000.000.000 bytes, es de suponer que 1 KB son 1000 bytes. Sin embargo, Windows te dirá que sí, son 250.000.000.000 bytes, pero no llegan más que a 232,8 GB (siendo por tanto 1 KB = 1024 bytes). Por otra parte, los disquetes de tres pulgadas y media que tenían una capacidad de 1,44 MB… bueno, en bytes eso equivale a 1,44 x 1000 x 1024.
    Parece ser que al principio 1 KB sí eran 1024 bytes, pero para no desvirtuar los prefijos utilizados en el Sistema Internacional, se decidió que los prefijos kilo, mega, giga, etc. indican siempre potencias de 10, y para sustituir el uso binario de esos prefijos se idearon otros prefijos formados por la primera sílaba de los originales más “bi”: así, un kibibyte son 1024 bytes, un mebibyte son 1024² bytes, etc. De todas formas, no se puede decir que los prefijos binarios hayan calado mucho. 😉

    Publica una respuesta
  15. Hasta hoy en día sólo se conoce la secuencia completa de los números primos de Mersenne hasta el trigésimonoveno lugar. Este último primo de la lista, ubicado en puesto 39, tiene 4053946 dígitos.

    Publica una respuesta
  16. Hola todos, me ha gustado mucho este sitio de gaussianos y lo visitio muy seguido. Mi participación acá es para que alguien me diga que aplicación (actual o futura) puede tener este tipo de descubrimientos.

    Gracias.

    Publica una respuesta
  17. Alejandro: Este tipo de descubrimientos puede llegar a tener una importante aplicación en el futuro o quizá tal vez nunca la llegue a tener. Los matemáticos estudian patrones y a muchos de ellos no les interesa si su objeto de estudio atesora una aplicación importante o inmediata. Por ejemplo, es sabido que los números primos fueron estudiados por generaciones de matemáticos durante más de 2500 años, a pesar que no se les encontraba una utilidad provechosa fuera del ámbito académico. Sin embargo en la era de la informática estos números adquirieron una gran importancia debido a que permitieron realizar intercambios de información con gran seguridad, lo que a su vez posibilitó la explosiva expansión del comercio electrónico mundial.
    Vemos entonces que uno nunca puede llegar a saber lo que acontecerá cuando decide emprender o realizar una investigación básica.

    Publica una respuesta
  18. Yo creo que se podría hacer con logaritmos. Al fin y al cabo, el número de cifras de un número en decimal es logaritmo en base 10 del número en cuestión, redondeado hacia arriba.

    \mbox{numero de cifras de x} = \sup ( \log_{10}{x})

    Por ejemplo, el número 12345 tiene 5 cifras, puesto que

    \log_{10}{12345} \simeq 4,091, y 4,091 redondeado hacia arriba es 5 .

    Podemos hacer lo mismo con el último primo de Mersenne. Para hacer las cosas más fáciles, no tendré en cuenta el -1

    Si utilizamos la regla \log_{a}{m^n} = n \log_{a}{m}, resulta:

    \log_{10}{(2^{32582657}-1)} \simeq 32582657 \cdot \log_{10}{2} \simeq 9.808.358 cifras

    Publica una respuesta
  19. Bien, me acabo de dar cuenta de que ya lo ponía en el artículo 🙁

    Publica una respuesta
  20. Tranquilo Victor, yo acabo de darme cuenta de que el número 2^{32582657}-1 ocupa exactamente 32582657 bits, si se guarda en binario.

    Es decir, aproximadamente los 4 megas de los que hablaba Alfredo.

    Lo mío es peor ¿no crees?

    Publica una respuesta
  21. La representación en binario de un número primo de Mersenne no deja de ser curiosa, pues tiene todos sus bits significativos iguales a 1.

    Publica una respuesta
  22. De paso, lo que he escrito arriba sirve para demostrar de una forma rápida y visual, aunque no demasiado formal, que cualquier número de la forma 2^N-1 con N compuesto, es compuesto.

    Si N es compuesto, se puede descomponer como mínimo en dos factores A y B, y los bits del número se pueden agrupar en B grupos de A bits consecutivos. Por ejemplo, 2^15-1 en binario sería así con 3 grupos de 5 bits (3×5=15):

    11111 \ 11111 \ 11111_b

    Y ese número es múltiplo de este:

    00001 \ 00001 \ 00001_b

    Para verlo visualmente basta con ir multiplicando el número mentalmente por 1, por 2, por 3… para ver que van saliendo los números:

    00001 \ 00001 \ 00001_b
    00010 \ 00010 \ 00010_b
    00011 \ 00011 \ 00011_b
    00100 \ 00100 \ 00100_b

    Es decir, es como si contaramos en binario en cada grupo, a la vez, con lo que está garantizado que llegaremos a 2^{15}-1

    No es que la demostración formal sea complicada, pero esta dejará satisfecho a cualquier informático acostumbrado a trabajar en binario.

    Publica una respuesta
  23. Los primos de Mersenne tienen interesantes características que los relacionan con los números perfectos, superperfectos, repunits, triangulares y hexagonales.
    Por ejemplo:
    El enésimo número primo de Mersenne es igual a la suma de divisores del enésimo número superperfecto par:
    M(n) = Sigma(S(n))
    Es también igual al índice del número triangular que es igual al enésimo número perfecto par:
    P(n) = T(M(n))
    También es igual al número de enteros positivos (1, 2, 3,…) cuya suma es igual al enésimo número perfecto par.
    Además es igual al número de vértice en donde se encuentra el enésimo número perfecto par, en la espiral cuadrada cuyos vértices son los números triangulares.
    Con respecto a los números hexagonales, se relacionan a través de los números superperfectos pares.
    Ahora podemos escribir una hermosa igualdad:
    P(n) = T(M(n)) = H(S(n))
    En donde:
    P = Perfecto par
    n = Natural
    T = Triangular
    M = Primo de Mersenne
    H = Hexagonal
    S = Superperfecto par

    Publica una respuesta
  24. Aunque más ordenado queda:

    P(n) = H(S(n)) = T(M(n))

    Por ejemplo:
    P(1) = H(2) = T(3) = 6
    P(2) = H(4) = T(7) = 28
    P(3) = H(16) = T(31) = 496
    P(4) = H(64) = T(127) = 8128
    P(5) = H(4096) = T(8191) = 33550336

    Saludos.

    Publica una respuesta
  25. El descubrimiento de un número primo de Mersenne implica también el descubrimiento de un número perfecto.

    Publica una respuesta
  26. Con respecto a la pregunta de vengoroso, efectivamente existe un premio de 100000 dólares por encontrar un número primo de 10 millones de dígitos. (Me pregunto si también será válido para números primos de más de 10 millones de dígitos, je, je, je). El premio en cuestión tiene algunos descuentos por razones varias. Posiblemente el ganador se lleve alrededor de 50000 dólares.

    Publica una respuesta
  27. Cierto Omar. La primera verificación del posible primo de Mersenne número 45 ha confirmado que es primo. La segunda verificación está en marcha. Estaré pendiente.

    Publica una respuesta
  28. Interesante pero aunque no soy matematico, encontre datos con los que puedo demostrar que los Numeros Primos se Originan de unos cuantos a los he llamado “Primos Origen”, solo de estos salen los posibles primos que como sabemos terminan en 1, 3, 7 y 9.
    Con esto diseñe un metodo denominado PRI-BASE para Buscar numeros primos sin recurris a evaluar si son divisibles o multiplos de primos anteriores, ya que simplemente el metodome dice cuales No son Primos y son depurados.
    ○ En mi 1º Analisis, encontre varias secuencias y patrones que se repiten y se relacionan con los primos origen, lo que me dio a comprender porque no siguen un orden logico como lo ven, pero a mi modo de verlo es todo logico y hay un orden. Cada primo origen genera un Primo Multiplo que como es grande su secuencia lo sera tambien; pero si o si, solo tendra una cantidad definida de multiplos en cada secuencia y eso se aplica para todos los numeros primos. Suponiendo que se transportan a pie, recorren 5 cuadras y en esas 5 cuadras tendran 10 amigos (multiplos) y 5 primos(primos multiplos). El 1º primo (primo multiplo) ira en bicicleta 10 cuadras donde tendra 10 amigos y 5 primos o menos, ya que los amigos del origen estan presentes y de los otros primos origen, que son unos cuantos. El 2º primo multiplo ira en auto recorriendo 20 cuadras donde si o si tendra tambien 10 amigos y menos de 5 primos, porque los amigos desde el origen y demas primos multiplos ocupan los espacios para los primos.
    ○ Por esta razon es que a simple vista no parece logico que haya una secuencia y muchos afirman que se oroginan al azar, lo cual es totalmente Falso… ademas obedecen a ciertas secuencias cuya cantidad se repite en todo, que indican de que primo origen salio un numero primo, cuales son sus multiplos directos para depurarlos ya que hay una relacion contante entre los primos origen y sus primos multiplos.
    ◘ Un ultimo detalle es que no necesito tener todos los primos encontrados para obtener nuevos primos, cada uno tiene una secuencia que se obtiene de los primos origen, por lo que mi metodo PRI-BASE no realiza calculos complejos, tan solo suma, resta, multiplicacion y division.

    ○ Mi 2º Analisis lo estoy haciando para encontrar la relacion dentre los Primos Gemelos y los Primos Origen, la secuencia para determinarlos y si estos intervienen en la ausencia de numeros primos en determinados rangos, que ya se se da por la secuencia; pero entre ambas secuencias es posible encontrar un modo de obtener directamente todos los numeros primos sin calculos complicados.

    Publica una respuesta

Trackbacks/Pingbacks

  1. meneame.net - Posible descubrimiento del primo de Mersenne número 45... Un número de Mersenne es aquel que cumple la condición :…
  2. Gaussianos » Todo número de Mersenne con exponente compuesto es también compuesto - [...] en este comentario, ha dado una demostración informática de que un número de Mersenne con exponente compuesto es [...]
  3. Gaussianos » Posible descubrimiento del primo de Mersenne número 46 - [...] no nos habíamos recuperado del posible descubrimiento del primo de Mersenne número 45 cuando nos encontramos otro posible primo…
  4. ¡¡Tenemos dos nuevos primos de Mersenne!! | Gaussianos - [...] 2 en Posible descubrimiento del primo de Mersenne número 45 [...]
  5. ¡¡Tenemos dos nuevos primos de Mersenne!! « ElDigital.net - [...] se habían encontrado dos nuevos posibles primos de Mersenne, los que ocuparían las posiciones 45 y 46. Estábamos esperando…
  6. El primo de Mersenne número 45, entre los mejores descubrimientos de 2008 | Gaussianos - [...] el número 29. Como ya sabréis, en Gaussianos nos hicimos eco del descubrimiento, desde que era un posible hallazgo…
  7. Confirmado el descubrimiento del primo de Mersenne número 47 | Gaussianos - [...] Posible descubrimiento del primo de Mersenne número 45 [...]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *