¿Cómo encontrar el valor de n cuando 2 elevado a la enésima potencia menos 1 es igual a un número primo?
Cuando 2^n-1 es un número primo, se convierte en un número primo de Mersenne. La siguiente es una introducción a los primos de Mersenne. Y la historia de las personas que lo calculan.
Recompensa de 100.000 dólares: búsqueda en Internet de números primos de Mersenne
1 Números primos por valor de 50.000 dólares
El 6 de abril de 2000 vivía en Nayan Hajratwala de Plymouth. , Michigan, EE.UU.
El Sr. Nayan Hajratwala recibió un premio de matemáticas de 50.000 dólares porque
encontró que el mayor número primo conocido hasta ahora es un primo de Mersenne:
2 ^6972593-1.
Este es también el primer número primo que conocemos con más de un millón de dígitos. Para ser precisos, si
este número primo se escribe en la forma decimal familiar, tiene 2.098.000
novecientos sesenta dígitos. Si lo escribiéramos en esta forma, sería. tome entre 150 y 200 artículos
la extensión de este artículo.
Pero el Sr. Hajiratwala no es matemático y puede que ni siquiera sepa nada sobre la teoría matemática para encontrar números primos, aunque esto le ha valido este bono. Lo único que hizo
fue descargar un programa de Internet. Este programa se ejecuta silenciosamente cuando no está usando su computadora Pentium II350. Después de 111 días de cálculo, se descubrió el número primo mencionado anteriormente.
2. Número primo de Mersenne
Llamamos número primo a un número natural mayor que 1, si sólo 1 y él mismo pueden dividirlo.
Si un número natural mayor que 1 no es primo, lo llamamos número compuesto. 1 no es ni primo ni compuesto.
Por ejemplo, puedes comprobar fácilmente que 7 es un número primo y 15 es un número compuesto, porque
Además de 1 y 15, 3 y 5 pueden dividir 15. . Por definición, el 2 es un número primo, es el único número primo par. Ya en la antigua era griega del año 300 a. C., el gran matemático Euclides
Reed demostró que existen infinitos números primos.
Respecto a los números primos, hay muchas preguntas sencillas y bonitas, pero extremadamente difíciles, que no tienen respuesta
hasta el momento. Entre ellas se encuentra la famosa conjetura de Goldbach, que establece que cualquier número par mayor que 6 puede expresarse como la suma de dos números primos impares. También está el problema de los primos gemelos. Los pares de números primos que difieren en 2, como 5 y 7, 41
y 43, se llaman números primos gemelos. El problema de los primos gemelos es: ¿Existe un número infinito de pares de primos gemelos?
Por cierto, cabe mencionar aquí que las soluciones a estos problemas matemáticos aparentemente simples deben ser extremadamente complejas y requerir las herramientas matemáticas más avanzadas. Si no eres tan arrogante como para pensar que cientos o incluso miles de años han dedicado a estos problemas innumerables matemáticos ingeniosos (muchos de los cuales son muy grandes) y entusiastas de las matemáticas
p>Si no todos ellos son tan Por muy inteligente que seas, no intentes utilizar métodos elementales para resolver estos problemas. Es una pérdida de tiempo y energía.
Los antiguos griegos también se interesaban por otro tipo de números. Lo llaman el número perfecto. Un número natural mayor que 1 se llama número perfecto si la suma de todos sus factores (incluido 1 pero no él mismo) es igual a sí mismo. Por ejemplo, 6=1+2+3 es el número perfecto más pequeño. Los antiguos griegos lo consideraban Venus, que también es un símbolo del amor. 28=1+2+4+7+14 es otro número perfecto. La prueba de Euclides
Claramente: un número par es un número perfecto si y sólo si tiene la siguiente forma:
2^(p-1)(2^p-1)
Donde 2^p-1 es un número primo. Los anteriores 6 y 28 corresponden a los casos de p=2 y 3.
Siempre que encontremos un número primo con la forma 2^p-1, también conocemos un número par perfecto, solo necesitamos encontrar todos los números primos en; la forma de 2^p-1 Números primos, es decir, se encuentran todos los números pares perfectos. Así que el Sr. Hajiratwala no sólo encontró el número primo más grande conocido en el mundo, sino que también encontró el número perfecto par más grande conocido en el mundo. Bueno, preguntas, ¿qué pasa con los números perfectos impares? La respuesta es:
No hemos encontrado ni un número perfecto impar y ni siquiera sabemos si
existen números perfectos impares. Sólo sabemos que si hay un número perfecto impar, ¡debe ser muy, muy grande! La cuestión de si existen números perfectos impares es también un problema matemático bien conocido que, como se mencionó anteriormente, es a la vez simple y hermoso, pero extremadamente difícil.
Durante mucho tiempo la gente pensó que para todos los números primos p,
M_p=2^p-1
son números primos (tenga en cuenta que 2^ p -1 es un número primo, p en sí mismo debe ser un número primo, piénselo
¿Por qué) Pero en 1536, Hudalricus Regius señaló,
M_11= 2^11-? 1=2047=23*89 no es un número primo.
Pietro Cataldi realizó por primera vez un estudio sistemático de este tipo de números
. En los resultados anunciados en 1603, dijo que para p = 17, 19, 23, 29, 31 y 37, 2^p-1 es un número primo. Pero en 1640 Fermat utilizó el famoso Pequeño Teorema de Fermat (que no debe confundirse con el último teorema de Fermat) para demostrar que los resultados de Cataldi sobre p=23 y 37 estaban equivocados.
p>
Mal, Euler demostró que el resultado de p=29 también era erróneo en 1738, y más tarde demostró que la conclusión sobre p=31 era correcta. Cabe señalar que Cataldi llegó a su conclusión comprobando manualmente cada cálculo uno por uno, mientras que Fermat y Euler utilizaron los métodos más avanzados de su época.
El conocimiento de las matemáticas evita muchos cálculos complejos y los errores que conllevan; puede resultar.
El sacerdote francés Marin Mersenne publicó sus resultados en 1644. Afirmó que para p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 y 257, 2^p-1 es primo, Para otros números primos p menores que 257, 2^p-1 es un número compuesto. Hoy llamamos primos a los números en la forma
M_p=2^p-1 llamados primos de Mersenne. La M en M_p es la primera letra del apellido de Mersenne.
Es bastante difícil juzgar a mano si un número grande es primo, y el propio padre Mason
admitió que sus cálculos no eran necesariamente precisos. Hubo que esperar hasta un siglo después, en 1750, para que Euler anunciara que había descubierto el error del padre Mason: M_41 y M_47 también son números primos. Pero
Un gran hombre como Euler también puede cometer errores de cálculo; de hecho, ni M_41 ni M_47 son números primos. Sin embargo, esto no significa que el resultado del padre Mason sea correcto. No fue hasta 1883, más de doscientos años después de que se anunciaran los resultados de Mason, que se descubrió el primer error: M_61 es un número primo.
Luego se encontraron otros cuatro errores: M_67 y M_257 no eran números primos, mientras que M_89 y
M_107 eran números primos. No fue hasta 1947 que se determinó el resultado correcto para el primo de Mersenne M_p para p<=257, es decir, cuando p=2, 3, 5, 7, 13, 17, 19, 31, 61, At 89, 107 y
127, M_p es un número primo. Ahora esta tabla ha sido verificada repetidamente y no debe haber errores.
Aquí hay una lista de todos los números primos de Mersenne que conocemos ahora: (Observamos que el nombre del padre Mersenne no aparece en ella; dichos números primos ya llevan su nombre, así que dale el honor
al confirmador final.
)
La persona de confirmación correspondiente a los dígitos del número de serie p M_p
La edad del número perfecto
Dígitos
1 2 1 1 ---- ----
2 3 1 2 ---- ----
3 5 2 3 ---- ----
4 7 3 4 ---- ----
5 13 4 8 1456 Anónimo
6 17 6 10 1588 Cataldi
7 19 6 12 1588 Cataldi
8 31 10 19 1772 Euler
9 61 19 37 1883 Pervushin
10 89 27 54 1911 Poderes
11 107 33 65 1914 Poderes
12 127 39 77 1876 Lucas
13 521 157 314 1952 Robinson
14 607 183 366 1952 Robinson
15 1279 386 770 1952 Robinson
16 2203 664 1327 1952 Robinson
17 2281 687 1373 1952 Robinson
18 3217 969 1937 1957 Riesel
p>19 4253 1281 2561 1961 Hurwitz
20 4423
1332 2663 1961 Hurwitz
21 9689 2917 5834 1963 Gillies
22 9941 2993 5985 1963 Gillies
23 11213 3376 6751 1963 Gillies
24 19937 6002 12003 1971 Tuckerman
25 21701 6533 13066 1978 Noll & Nickel
26 23209 6987 13973 1979 Noll
27 44497 13395 26790 9 79 Nelson y Slowinski
28 86243 25962 51924 1982 Slowinski
29 110503 33265 66530 1988 Colquitt & Welsh
30 132049 39751 79502 1983 Slowinski
31 2160 91 65050 130100 1985 Slowinski
32 756839 227832 455663 1992 Slowinski y Gage
33 859433 258716 517430 1994 Slowinski y Gage
34 1257787 863 2 757263 1996 Slowinski y Calibre
35 1398269 420921 841842 1996 GIMPS
36 2976221 895932 1791864 1997 GIMPS
37 3021377 909526 1819050 1998 GIMPS
3 8 6972593 2098960 4197919 1999 GIMPS
39 13466917 4053947
40 20996011 6320431
41 24036583 7235734
42 2
5964951 7816230 2005
¿Hay infinitos primos de Mersenne? Los matemáticos aún no son capaces de responder a esta pregunta.
3. Buscando números primos más grandes
¿Por qué buscar números primos de Mersenne? ¿Por qué batir el récord del número primo más grande conocido? ¿De qué sirve esto
?
Si la utilidad de la que hablas se refiere a la capacidad de crear riqueza material directamente, entonces tengo que decirte
Los números primos de Mersenne son de poca utilidad si los conoces. número primo grande Parece ser inútil
. Incluso si conociéramos un Mersenne prime infinitamente enorme, no agregaría ni un centavo a nuestras billeteras (¡Oye, espera! Si solo estás interesado en el dinero, por favor no lo hagas). Deje a un lado mi artículo de inmediato. Lo que realmente quise decir es que lo que dije anteriormente debe excluir el bono de $ 100,000 que mencioné en el título de este artículo: su billetera tal vez lo anime.
Así que tenga paciencia. .
Pero los humanos no sólo necesitamos riqueza material. ¿Cuáles son los usos de los diamantes en los museos?
¿Por qué los coleccionamos los humanos? Porque son hermosos y raros. Como cristalización de la sabiduría humana,
Los números primos, los números primos de Mersenne y los números perfectos estrechamente relacionados con ellos son muy hermosos. Sus definiciones
son simples, pero tan misteriosas, como las grandes matemáticas de Euclides, Descartes, Fermat, Leibniz y Euler
Todos han investigado mucho al respecto debido a su belleza; todos
también han visto que después de más de dos mil años e incontables generaciones de arduo trabajo, solo hemos recolectado un *** p>
Hay 38 números primos de Mersenne, que son muy raros. . Para los matemáticos, coleccionar números primos, números primos y números perfectos es tan divertido como coleccionar diamantes.
La humanidad también necesita gloria, quizás más que riqueza. En los deportes, ¿poder correr más rápido y saltar más alto realmente tiene algún uso material práctico? No,
Nos gusta asumir retos y queremos ganar. Batir un récord deportivo mundial, escalar el Monte Everest, cruzar el Pacífico navegando en solitario… son desafíos a los límites de la capacidad física humana y buscar algo más grande Los números primos son un desafío a la sabiduría humana; Siempre nos sentimos extremadamente orgullosos cuando realizamos una tarea sin precedentes. En 1963, cuando se descubrió el número primo número 23 de Mersenne, el Departamento de Matemáticas de la Universidad de Illinois, que lo descubrió, estaba tan orgulloso que envió todas las matemáticas del departamento. todos estampados con el matasellos "2^11213-1 es un número primo".
Después de que Euler demostró que M_31 es un número primo, Landry obtuvo el récord del siguiente número primo más grande
(Landry) en 1867: M_59/179951=3203431780337. Esta no es una excelente opción. Este récord se mantuvo durante nueve años.
En 1876, Edward Lucas utilizó un método más avanzado que Fermat y Euler
para demostrar que M_127 es un número primo. Este récord se mantuvo durante setenta y cinco años. Hasta que Ferrier utilizó una computadora manual en 1951 para demostrar que (2^148+1)/17 es un número primo con 41 dígitos.
Si el método que utiliza una computadora manual debe considerarse como un método de cálculo manual o como un método informático
es probablemente una cuestión que puede discutirse. Sin embargo, el desarrollo de la tecnología de repente ha hecho que este debate sea innecesario
. Vale la pena señalar que en el viaje humano para encontrar números primos grandes, mejorar la teoría matemática es mucho más importante que tener una potencia informática sólida y tenaz. Después de que Lehmer simplificó el método de Lucas en 1930, la prueba de Lucas-Lehmer se convirtió en el método estándar actual para encontrar números primos de Mersenne.
(Prueba de Lucas-Lemay: para todo p impar mayor que 1, M_p es primo si y sólo si M_p
divide S(p-1), donde S( n) es definido recursivamente por S(n+1)=S(n)^2-2, S(1)=4
4 14 194 37634 1416317954 2005956546822746114
Esta prueba. p>
La prueba es especialmente adecuada para operaciones informáticas, porque la operación de dividir por M_p=2^p-1 se puede realizar en binario.
Simplemente utilice las operaciones de desplazamiento y suma que realizan las computadoras. Particularmente bueno en la implementación. El método para determinar si un número de Mersenne es un número primo es mucho más simple que el método para determinar si otro tipo de número de tamaño similar es un número primo. , la mayoría de los registros son primos de Mersenne)
En 1951, Miller y Wheeler usaron la computadora EDSAC (este tipo de computadora no era tan buena como la nuestra ahora usando una calculadora general, que solo tiene 5K de). memoria), descubrí el número primo de 79 bits 180(M_127)^2+1. Este récord todavía no duró mucho. Al año siguiente,
Robinson utilizó la computadora SWAC y descubrió los números primos 13 y 14 de Mersenne a principios de 1952:
M_521 y M_607 también se descubrieron en el mismo. año Descubiertos uno tras otro: M_1279,
M_2203 y M_2281.
En los años siguientes, los ordenadores utilizados para batir el enorme récord de números primos se hicieron cada vez más potentes, incluido el famoso ordenador IBM 360 y la serie de superordenadores Cray. Todos pueden consultar la tabla de números primos de Mersenne anterior para comprender el proceso de competencia. Sólo una vez durante este período un número primo que no era un primo de Mersenne se sentó en el trono del "número primo más grande conocido". Fue 39158*2^216193-1 en el año 1989. M_1257787, descubierto en 1996, fue el último primo de Mersenne descubierto hasta ahora por una supercomputadora que los matemáticos utilizaron Cray T94.
Entonces llegó la era de GIMPS.
4. GIMPS - Búsqueda en Internet de primos de Mersenne
En 1995, el programador George Woltman comenzó a recopilarlos y organizarlos
Acerca de los datos de Mersenne para cálculos de números primos. Compiló un programa para encontrar números primos de Mersenne y lo puso en la web para que los entusiastas de las matemáticas lo utilizaran de forma gratuita. Esta es la "Gran Búsqueda de Mersenne Prime en Internet" (GIMPS, la Gran Búsqueda de Mersenne Prime en Internet). En este
proyecto, más de una docena de expertos en matemáticas y miles de entusiastas de las matemáticas están buscando el siguiente número primo de
Mersenne más grande y verificando las brechas entre los registros anteriores de números primos de Mersenne A. brecha a explorar. Por ejemplo, en la tabla de números primos de Mersenne anterior, se desconoce el número de serie del último número primo. No sabemos si hay otros números desconocidos entre el número primo de Mersenne 37 y él.
En 1997, Scott Kurowski y otros establecieron PrimeNet para asignar intervalos de búsqueda y enviar datos a la automatización de informes GIMPS. Ahora sólo necesitas
ir a la página de inicio de GIMPS para descargar el programa gratuito y podrás unirte inmediatamente al proyecto GIMPS
para buscar números primos de Mersenne. Hay versiones disponibles para casi todas las plataformas informáticas habituales. El programa se ejecuta en su computadora con la prioridad más baja, por lo que casi no tiene impacto en su uso normal de la computadora. El programa también se puede detener en cualquier momento, y la próxima vez que se inicie continuará los cálculos desde donde se detuvo
.
De 1996 a 1998, el proyecto GIMPS descubrió tres números primos de Mersenne: M_1398269,
M_2976221 y M_3021377, todos ellos utilizando ordenadores Pentium.
En marzo de 1999, la Electronic Frontier Foundation (EFF,
Electronic Frontier Foundation), una asociación activa en Internet, anunció un proyecto financiado por una persona anónima para encontrar
Un bono para números primos enormes. Estipula que se otorgará un premio de 50.000 dólares al primer individuo o institución que encuentre un número primo con más de un millón de dígitos. Esta es la hajira de la que hablamos al principio
Twala recibió un bono. Las siguientes bonificaciones son: más de 10 millones de plazas, 100.000 dólares estadounidenses;
Superar los 100 millones de plazas, 150.000 dólares estadounidenses;
La verificación de los resultados de búsqueda y la concesión de bonificaciones son muy estrictas. Por ejemplo, el resultado debe ser explícito: no puedes afirmar que tu resultado es la solución de un sistema de cien ecuaciones sin Unravel it. Los resultados deben ser verificados de forma independiente por otra computadora.
Todas estas normas están explicadas en la web de la EFF.
Cabe señalar que la esperanza de recibir bonificaciones por participar en el programa GIMPS es bastante pequeña.
La computadora utilizada por Hajiratwala era una de las 21.000 computadoras que había en ese momento. Cada participante verifica los diferentes números de Mersenne que se le han asignado y, por supuesto, la gran mayoría de ellos no son números primos: sólo tiene una probabilidad entre 30.000 de que Sex acierte un número primo.
El próximo premio de 100.000 dólares se otorgará a la primera persona o institución que encuentre un número primo con más de 10 millones de dígitos
. La cantidad de cálculo esta vez será aproximadamente 125 veces mayor que la de la última vez. Ahora
GIMPS tiene una potencia informática de 700 mil millones de operaciones de punto flotante por segundo, lo que equivale a las capacidades operativas de una de las
computadoras supervectoriales más avanzadas de la actualidad, como la Cray T932. Pero si GIMPS quisiera utilizar una supercomputadora de este tipo, tendría que pagar unos 200.000 dólares al día. Pero ahora los gastos que necesitan son sólo para respaldar el funcionamiento del sitio web y un total de cientos de miles de dólares en bonificaciones.
5. Plan de computación distribuida en línea
GIMPS es solo uno de los muchos planes de computación distribuida en Internet.
Están disponibles en la página de inicio de GIMPS. al plano.
La computación distribuida es una disciplina informática que estudia cómo dividir un problema que requiere una potencia informática muy grande
en muchas partes pequeñas y luego asignar estas partes
Se utilizan muchas computadoras para el procesamiento y, finalmente, los resultados de estos cálculos se combinan para obtener el resultado final
A veces, la cantidad de cálculo es tan grande que se necesitan miles o incluso más computadoras en todo el mundo para trabajar juntas para obtener resultados en un tiempo razonable. El proyecto GIMPS realiza este tipo de computación distribuida.
Pero no es la iniciativa de informática distribuida más conocida. El proyecto SETI@HOME de "Búsqueda de Civilización Extraterrestre" (Proyecto SETI), dedicado a la búsqueda de vida inteligente en el universo, ha reclutado a 2,9 millones de personas en todo el mundo. Un (!) voluntario utiliza un protector de pantalla para procesarlo. la gran cantidad de señales de radio que reciben los radiotelescopios del universo. Si te unes a este proyecto, tal vez algún día puedas descifrar los saludos de los extraterrestres en tu computadora.
También puedes utilizar la potencia informática sobrante de tu ordenador para contribuir a la conquista del cáncer por parte de la humanidad.
Los científicos británicos han diseñado un protector de pantalla informático distribuido similar al proyecto SETI@HOME. Descarga datos de sitios web relevantes, analiza las propiedades anticancerígenas de las moléculas químicas y luego envía los resultados del análisis. volver a los investigadores a través de Internet como referencia para el desarrollo de nuevos fármacos contra el cáncer.
Este proyecto se lanzará oficialmente el 3 de abril de 2001 en California, EE. UU.
Las actualizaciones de hardware informático son vertiginosas. Las últimas computadoras personales adquiridas en la primera mitad del año se vuelven populares en la segunda mitad del año.
Las CPU de hace tres o cuatro años ya no valen nada -
Quizás no se pueda decir que no se puedan comprar en absoluto - incluso las CPU más baratas del mercado
Mucho más potentes que ellos. Un ordenador doméstico normal puede funcionar de forma continua durante cinco años sin ningún problema.
Por tanto, la actitud más económica ante un ordenador es: dejarlo funcionar.
Y los humanos todavía tenemos mucho que calcular, tantas preguntas que encontrar
respuestas y tantas dificultades que superar. Necesitamos cada vez más potencia informática.
También tenemos esa potencia informática, pero una gran parte está inactiva y se desperdicia.
Internet ha hecho posibles proyectos de computación distribuida a gran escala. Ahora lo único que necesitamos es la voluntad y la confianza de los usuarios de ordenadores en cada nodo de esta red.