Как стать автором
Обновить

Найдено 48-е простое число Мерсенна

Время на прочтение 5 мин
Количество просмотров 71K
Математики из распределённого проекта по поиску простых чисел GIMPS объявили об обнаружении нового простого числа Мерсенна. Это важное событие для математического сообщества, потому что до сих пор было известно только 47 таких чисел, последнее было найдено в июне 2009 года.

48-е простое число Мерсенна — 257.885.161-1, с 17.425.170 десятичными разрядами. См. полную запись числа в текстовом формате.

Числа Мерсенна имеют вид 2n-1, где n — натуральное число. Простые числа Мерсенна являются самыми большими простыми числами, известными науке. Предыдущий мировой рекорд принадлежал числу 243.112.609-1, имеющему 12.978.189 десятичных разрядов.

Распределённый проект по поиску простых чисел GIMPS был запущен в 1997 году, и ныне считается самым длительным непрерывным процессом распределённых вычислений в истории человечества: он продолжается уже почти 17 лет. Сейчас в пиковые моменты в GIMPS участвует 360.000 процессоров с суммарной производительностью 150 трлн операций в секунду.

За время работы GIMPS участники этого проекта нашли 14 простых чисел Мерсенна. Последнее из них 257.885.161-1 было обнаружено 25 января 2013 года в 23:30:26 UTC, после чего его перепроверили несколько раз на разном оборудовании и программном обеспечении. В частности, программа MLucas проверяла 48-е простое число Мерсенна шесть суток на 32-ядерном сервере, и подтвердила его. На Nvidia GPU в программе CUDALucas число проверили за 3,6 суток и тоже подтвердили его.

Разработчики программного обеспечения GIMPS и участники проекта уже поделили приз $100 000 за прошлое простое число Мерсенна с как минимум 10 миллионами десятичных разрядов. Следующий приз — $150 000 за число с как минимум 100 миллионами десятичных разрядов. За только что найденное число дадут всего лишь $3000.

В списке самых больших простых чисел, известных на сегодняшний день, десять первых мест занимают числа Мерсенна.

Топ-100
-----  ---------------------------- ------- ----- ---- --------------
Место           Описание           Разрядов  Кто Год  Описание
-----  ---------------------------- ------- ----- ---- --------------
    1  2^57885161-1                17425170   G13 2013 Мерсенн 48??
    2  2^43112609-1                12978189   G10 2008 Мерсенн 47??
    3  2^42643801-1                12837064   G12 2009 Мерсенн 46??
    4  2^37156667-1                11185272   G11 2008 Мерсенн 45?
    5  2^32582657-1                 9808358    G9 2006 Мерсенн 44?
    6  2^30402457-1                 9152052    G9 2005 Мерсенн 43?
    7  2^25964951-1                 7816230    G8 2005 Мерсенн 42
    8  2^24036583-1                 7235733    G7 2004 Мерсенн 41
    9  2^20996011-1                 6320430    G6 2003 Мерсенн 40
   10  2^13466917-1                 4053946    G5 2001 Мерсенн 39
   11  19249*2^13018586+1           3918990  SB10 2007
   12  475856^524288+1              2976633 L3230 2012 Обобщённое Ферма
   13  356926^524288+1              2911151 L3209 2012 Обобщённое Ферма
   14  341112^524288+1              2900832 L3184 2012 Обобщённое Ферма
   15  27653*2^9167433+1            2759677   SB8 2005
   16  90527*2^9162167+1            2758093 L1460 2010 
   17  75898^524288+1               2558647  p334 2011 Обобщённое Ферма
   18  28433*2^7830457+1            2357207   SB7 2004 
   19  3*2^7033641+1                2117338 L2233 2011 Делит ОФ(7033639,3)
   20  33661*2^7031232+1            2116617  SB11 2007
   21  2^6972593-1                  2098960    G4 1999 Мерсенн 38
   22  6679881*2^6679881+1          2010852  L917 2009 Каллена
   23  1582137*2^6328550+1          1905090  L801 2009 Каллена
   24  3*2^6090515-1                1833429 L1353 2010
   25  7*2^5775996+1                1738749 L3325 2012
   26  252191*2^5497878-1           1655032 L3183 2012
   27  258317*2^5450519+1           1640776  g414 2008 
   28  773620^262144+1              1543643 L3118 2012 Обобщённое Ферма
   29  3*2^5082306+1                1529928  L780 2009 
          Делит ОФ(5082303,3), ОФ (5082305,5)
   30  676754^262144+1              1528413 L2975 2012 Обобщённое Ферма
   31  5359*2^5054502+1             1521561   SB6 2003 
   32  525094^262144+1              1499526  p338 2012 Обобщённое Ферма
   33  265711*2^4858008+1           1462412  g414 2008 
   34  1271*2^4850526-1             1460157 L1828 2012 
   35  361658^262144+1              1457075  p332 2011 Обобщённое Ферма
   36  9*2^4683555-1                1409892 L1828 2012 
   37  121*2^4553899-1              1370863 L3023 2012
   38  145310^262144+1              1353265  p314 2011 Обобщённое Ферма
   39  353159*2^4331116-1           1303802 L2408 2011
   40  141941*2^4299438-1           1294265  L689 2011
   41  3*2^4235414-1                1274988  L606 2008
   42  191*2^4203426-1              1265360 L2484 2012 
   43  40734^262144+1               1208473  p309 2011 Обобщённое Ферма
   44  9*2^4005979-1                1205921 L1828 2012 
   45  27*2^3855094-1               1160501 L3033 2012
   46  24518^262144+1               1150678  g413 2008 Обобщённое Ферма
   47  123547*2^3804809-1           1145367 L2371 2011
   48  415267*2^3771929-1           1135470 L2373 2011
   49  938237*2^3752950-1           1129757  L521 2007 Вудала
   50  65531*2^3629342-1            1092546 L2269 2011
   51  485767*2^3609357-1           1086531  L622 2008 
   52  5*2^3569154-1                1074424  L503 2009 
   53  1019*2^3536312-1             1064539 L1828 2012 
   54  7*2^3511774+1                1057151  p236 2008 Делит ОФ(3511773,6)
   55  428639*2^3506452-1           1055553 L2046 2011
   56  9*2^3497442+1                1052836 L1780 2012 Обобщённое Ферма
   57  1273*2^3448551-1             1038121 L1828 2012 
   58  191249*2^3417696-1           1028835 L1949 2010
   59  59*2^3408416-1               1026038  L426 2010 
   60  81*2^3352924+1               1009333 L1728 2012 Обобщённое Ферма
   61  1087*2^3336385-1             1004355 L1828 2012 
   62  3139*2^3321905-1              999997  L185 2008 
   63  4847*2^3321063+1              999744   SB9 2005 
   64  223*2^3264459-1               982703 L1884 2012 
   65  9*2^3259381-1                 981173 L1828 2011 
   66  113983*2^3201175-1            963655  L613 2008 
   67  1087*2^3164677-1              952666 L1828 2012 
   68  15*2^3162659+1                952057  p286 2012
   69  19*2^3155009-1                949754 L1828 2012 
   70  3*2^3136255-1                 944108  L256 2007 
   71  1019*2^3103680-1              934304 L1828 2012 
   72  5*2^3090860-1                 930443 L1862 2012 
   73  21*2^3065701+1                922870  p286 2012
   74  5*2^3059698-1                 921062  L503 2008 
   75  383731*2^3021377-1            909531  L466 2011 
   76  2^3021377-1                   909526    G3 1998 Мерсенн 37
   77  7*2^3015762+1                 907836  g279 2008
   78  1095*2^2992587-1              900862 L1828 2011 
   79  15*2^2988834+1                899730  p286 2012
   80  4348099*2^2976221-1           895939  L466 2008 
   81  2^2976221-1                   895932    G2 1997 Мерсенн 36
   82  198677*2^2950515+1            888199 L2121 2012 
   83  7*2^2915954+1                 877791  g279 2008 Делит ОФ(2915953,12)
   84  427194*113^427194+1           877069  p310 2012 Обобщённое Каллена
   85  1207*2^2861901-1              861522 L1828 2011 
   86  222361*2^2854840+1            859398  g403 2006 
   87  177*2^2816050+1               847718  L129 2012 
   88  96*10^846519-1                846521 L2425 2011 Почти репдигит
   89  15*2^2785940+1                838653  p286 2012
   90  17*2^2721830-1                819354  p294 2010 
   91  165*2^2717378-1               818015 L2055 2012 
   92  45*2^2711732+1                816315 L1349 2012 
   93  1372930^131072+1              804474  g236 2003 Обобщённое Ферма
   94  1361244^131072+1              803988  g236 2004 Обобщённое Ферма
   95  1176694^131072+1              795695  g236 2003 Обобщённое Ферма
   96  13*2^2642943-1                795607 L1862 2012 
   97  342673*2^2639439-1            794556   L53 2007 
   98  1243*2^2623707-1              789818 L1828 2011 
   99  13*2^2606075-1                784508 L1862 2011 
  100  334310*211^334310-1           777037  p350 2012 Обобщённое Вудала

Над поиском максимально больших простых чисел в своё время бились Катальди, Декарт, Ферма, Мерсенн, Лейбниц, Эйлер и многие другие математики. По ходу решения этой загадки были разработаны многие разделы теории чисел (например, малая теорема Ферма и квадратичный закон взаимности). В 20-м веке этот поиск привёл к созданию новых быстрых способов перемножения целых чисел: в 1968 году математик Фолкер Штрассен придумал, как использовать для этого быстрое преобразование Фурье. Сейчас этот метод известен как алгоритм Штрассена, его улучшенная версия используется в программном обеспечении GIMPS и повсеместно для быстрого перемножения матриц.

Загадка простых чисел Мерсенна и поиск новых простых чисел привили любовь к математике многим школьникам, которые в результате выбрали для себя научную и инженерную карьеру.

Вообще, поиск новых простых чисел, а особенно чисел Мерсенна, можно сравнить с коллекционированием редких вещей.
Теги:
Хабы:
+85
Комментарии 140
Комментарии Комментарии 140

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн