Наибольшее известное простое число

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Изменение во времени величины наибольшего известного простого числа с момента создания первой ЭВМ. По вертикальной оси отложено количество цифр в числе в логарифмическом масштабе. Красная линия — это экспоненциальная кривая наилучшего приближения (англ.) : y = exp(0.187394 t - 360.527), где время t измеряется в годах.

7 января 2016 года наибольшим известным простым числом стало число 274 207 281 − 1, которое содержит 22 338 618 десятичных цифр[1]. Открытие сделал Кёртис Купер (англ.) в рамках проекта GIMPS.

Согласно теореме Евклида, количество простых чисел бесконечно. Следовательно, количество простых чисел, превышающих наибольшее известное, тоже бесконечно. Многие учёные-математики, а также любители, занимаются поиском рекордных по величине простых чисел, за нахождение которых организацией Electronic Frontier Foundation было предложено несколько наград в зависимости от величины числа. Так, в 2009 году была вручена премия в 100 000 долларов США, назначенная сообществом Electronic Frontier Foundation за нахождение простого числа, десятичная запись которого содержит не менее 10 миллионов цифр

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа. Один из рекордов поставил в 1772 году Эйлер, найдя простое число 231 — 1 = 2 147 483 647[2].

Быстрейший из известных тестов простоты — реализация с использованием быстрого преобразования Фурье теста Люка — Лемера для чисел Мерсенна. В связи с этим, большинство из найденных в последнее время больших простых чисел — числа Мерсенна, и исключительно они занимают первую десятку. На двенадцатом месте — наибольшее известное простое число, не являющееся числом Мерсенна[3]. Последние шестнадцать найденных рекордных по величине простых чисел — также числа Мерсенна[3].

Текущий рекорд[править | править вики-текст]

Рекорд принадлежит простому числу 274 207 281 − 1 с 22 338 618 цифрами, открытому проектом GIMPS в 2016 году[1]. Оно равняется

3003764180846061820529860983591660500568758630303014848439416933455477232190679942968936553007726883
… (22 338 418 цифр опущено) …
3646879425801445107393100212927181629335931494239018213879217671164956287190498687010073391086436351

Первые и последние 100 цифр показаны сверху. По объёму это число примерно равняется семи романам «Война и мир»[4].

История[править | править вики-текст]

В таблице ниже представлены наибольшие известные простые числа в порядке открытия. Числа Мерсенна по основанию n обозначены Mn= 2n − 1.

Число Количество десятичных цифр Год нахождения
M127 39 1876
180×(M127)2 + 1 79 1951
M521 157 1952
M607 183 1952
M1279 386 1952
M2203 664 1952
M2281 687 1952
M3217 969 1957
M4423 1332 1961
M9689 2917 1963
M9941 2993 1963
M11 213 3376 1963
M19 937 6002 1971
M21 701 6533 1978
M23 209 6987 1979
M44 497 13 395 1979
M86 243 25 962 1982
M132049 39 751 1983
M216 091 65 050 1985
391 581⋅2216 193 − 1 65 087 1989
M756 839 227 832 1992
M859 433 258 716 1994
M1 257 787 378 632 1996
M1 398 269 420 921 1996
M2 976 221 895 932 1997
M3 021 377 909 526 1998
M6 972 593 2 098 960 1999
M13 466 917 4 053 946 2001
M20 996 011 6 320 430 2003
M24 036 583 7 235 733 2004
M25 964 951 7 816 230 2005
M30 402 457 9 152 052 2005
M32 582 657 9 808 358 2006
M43 112 609 12 978 189 2008
M57 885 161 17 425 170 2013
M74 207 281 22 338 618 2016

Десятка наибольших известных простых чисел[править | править вики-текст]

Место Число Первооткрыватель Дата нахождения Количество цифр Источник
1 274 207 281 − 1 GIMPS 7 января 2016 22 338 618 [1]
2 257 885 161 − 1 GIMPS 25 января 2013 17 425 170 [3]
3 243 112 609 − 1 GIMPS 23 августа 2008 12 978 189 [3]
4 242 643 801 − 1 GIMPS 12 апреля 2009 12 837 064 [5]
5 237 156 667 − 1 GIMPS 6 сентября 2008 11 185 272 [5]
6 232 582 657 − 1 GIMPS 4 сентября 2006 9 808 358 [5]
7 230 402 457 − 1 GIMPS 15 декабря 2005 9 152 052 [6]
8 225 964 951 − 1 GIMPS 18 февраля 2005 7 816 230 [6]
9 224 036 583 − 1 GIMPS 15 мая 2004 7 235 733 [6]
10 220 996 011 − 1 GIMPS 17 ноября 2003 6 320 430 [6]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 Mersenne Prime Number discovery - 274207281-1. GIMPS.
  2. Рекорды простых чисел по годам.  (Проверено 20 января 2016)
  3. 1 2 3 4 Chris Caldwell, The largest known primes.  (Проверено 20 января 2016)
  4. Коняев, 2016.
  5. 1 2 3 Landon Curt Noll, Mersenne Prime Digits and Names.  (Проверено 20 января 2016)
  6. 1 2 3 4 Samuel Yates, Chris Caldwell, The largest known primes.  (Проверено 20 января 2016)

Ссылки[править | править вики-текст]