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

Самое большое известное простое число — 2 82,589,933 − 1 , число, состоящее из 24 862 048 цифр при записи по основанию 10 . Он был найден с помощью компьютера, добровольно предоставленного Патриком Ларошем из Great Internet Mersenne Prime Search (GIMPS) в 2018 году. [1]

График количества цифр самого большого известного простого числа за 2020 год со времен появления электронного компьютера. Вертикальный масштаб логарифмический .

Простое число — это натуральное число больше 1, у которого нет делителей , кроме 1 и самого себя. Согласно теореме Евклида, простых чисел бесконечно много, поэтому наибольшего простого числа не существует.

Многие из самых больших известных простых чисел — это простые числа Мерсенна , числа, которые на единицу меньше степени двойки, поскольку для них можно использовать специализированный тест на простоту, который быстрее обычного. По состоянию на июнь 2023 г. , шесть крупнейших известных простых чисел — это простые числа Мерсенна. [2] Последние семнадцать рекордных простых чисел были простыми числами Мерсенна. [3] [4] Двоичное представление любого простого числа Мерсенна состоит из всех единиц, поскольку двоичная форма числа 2 к − 1 — это просто k единиц. [5]

Текущая запись [ править ]

На данный момент рекорд принадлежат 2 82,589,933 − 1 с 24 862 048 цифр, найден GIMPS в декабре 2018 года. [1] Ниже показаны первые и последние 120 цифр его значения:

148894445742041325547806458472397916603026273992795324185271289425213239361064475310309971132180337174752834401423587560 ...

(пропущено 24 861 808 цифр)

... 062107557947958297531595208807192693676521782184472526640076912114355308311969487633766457823695074037951210325217902591 [6]

По состоянию на февраль 2024 г. , это простое число удерживало рекорд более 5 лет, дольше, чем любое другое простое число, начиная с M 19937 (который удерживал рекорд в течение 7 лет с 1971 по 1978 год).

Призы [ править ]

(EFF) предлагает несколько призов Фонд Electronic Frontier Foundation за рекордные простые числа. [7] Простое число с одним миллионом цифр было найдено в 1999 году, за что первооткрыватель получил премию в размере 50 000 долларов США. [8] В 2008 году десятимиллионное простое число получило приз в размере 100 000 долларов США и премию Cooperative Computing Award от EFF. [7] Time назвал это простое число 29-м лучшим изобретением 2008 года. [9]

Оба этих простых числа были обнаружены с помощью Великого Интернет-поиска простых чисел Мерсенна (GIMPS), который координирует усилия по поиску на большие расстояния среди десятков тысяч компьютеров и тысяч добровольцев. Приз в размере 50 000 долларов достался первооткрывателю, а приз в 100 000 долларов достался GIMPS. GIMPS разделит приз в размере 150 000 долларов США за первое простое число из более чем 100 миллионов цифр с победителем. Следующий приз предлагается за первое простое число, содержащее не менее одного миллиарда цифр. [7]

GIMPS также предлагает награду в размере 3000 долларов США участникам, которые откроют новое простое число Мерсенна, состоящее менее чем из 100 миллионов цифр. [10]

История крупнейших известных простых чисел

Памятный штемпель, используемый математическим факультетом UIUC после доказательства того, что M 11213 является простым.

В следующей таблице приведена прогрессия наибольшего известного простого числа в порядке возрастания. [3] Здесь М п = 2 п − 1 — число Мерсенна с показателем p , где p — простое число. Самым длинным известным рекордсменом было M 19 = 524 287 , что было самым большим известным простым числом за 144 года. Никаких записей до 1456 года не известно.

Число Десятичное расширение
(частично для номеров > M 1000 ) 		Цифры Год найден Первооткрыватель
М 13 8,191 4 1456 Анонимный
М 17 131,071 6 1588 Пьетро Катальди
М 19 524,287 6 1588 Пьетро Катальди
6,700,417 7 1732 Леонард Эйлер ?
Эйлер не опубликовал явно простоту числа 6 700 417, но методы, которые он использовал для факторизации 2, 32 +1 означало, что он уже проделал большую часть работы, необходимой для доказательства этого, и некоторые эксперты полагают, что он знал об этом. [11]
М 31 2,147,483,647 10 1772 Леонард Эйлер
999,999,000,001 12 1851 Включен (но со знаком вопроса) в список простых чисел Луффа. Учитывая его неуверенность, некоторые не включают это в список рекордов.
67,280,421,310,721 14 1855 Томас Клаузен (но никаких доказательств предоставлено не было).
М 127 170,141,183,460,469, 231,731,687,303,715, 884,105,727 39 1876 Эдвард Лукас
20,988,936,657,440, 586,486,151,264,256, 610,222,593,863,921 44 1951 Эме Ферье с механическим калькулятором; самый большой рекорд, не установленный компьютером.
180×(М 127 ) 2 +1

521064401567922879406069432539 095585333589848390805645835218 3851018372555735221

79 1951 JCP Miller и DJ Wheeler [12]
Использование компании Cambridge EDSAC компьютера
М 521

686479766013060971498190079908 139321726943530014330540939446 345918554318339765605212255964 066145455497729631139148085803 712198799971664381257402829111 5057151

157 1952 Рафаэль М. Робинсон
М 607

531137992816767098689588206552 468627329593117727031923199444 138200403559860852242739162502 265229285668889329486246501015 346579337652707239409519978766 587351943831270835393219031728127

183 1952 Рафаэль М. Робинсон
М 1279 104079321946...703168729087 386 1952 Рафаэль М. Робинсон
М 2203 147597991521...686697771007 664 1952 Рафаэль М. Робинсон
М 2281 446087557183...418132836351 687 1952 Рафаэль М. Робинсон
М 3217 259117086013...362909315071 969 1957 Ганс Ризель
М 4423 285542542228...902608580607 1,332 1961 Александр Гурвиц
М 9689 478220278805...826225754111 2,917 1963 Дональд Б. Гиллис
М 9941 346088282490...883789463551 2,993 1963 Дональд Б. Гиллис
М 11213 281411201369...087696392191 3,376 1963 Дональд Б. Гиллис
М 19937 431542479738...030968041471 6,002 1971 Брайант Такерман
М 21701 448679166119...353511882751 6,533 1978 Лаура А. Никель и Лэндон Курт Нолл [13]
М 23209 402874115778...523779264511 6,987 1979 Лэндон Курт Нолл [13]
М 44497 854509824303...961011228671 13,395 1979 Дэвид Словински и Гарри Л. Нельсон [13]
М 86243 536927995502...709433438207 25,962 1982 Дэвид Словински [13]
М 132049 512740276269...455730061311 39,751 1983 Дэвид Словински [13]
М 216091 746093103064...103815528447 65,050 1985 Дэвид Словински [13]
148140632376...836387377151 65,087 1989 Группа «Амдал Сикс»: Джон Браун, Лэндон Курт Нолл , Б. К. Паради, Джин Уорд Смит, Джоэл Ф. Смит, Серджио Э. Зарантонелло. [14] [15]
Самое большое простое число, не являющееся числом Мерсенна, которое на момент открытия было самым большим из известных простых чисел.
М 756839 174135906820...328544677887 227,832 1992 Дэвид Словински и Пол Гейдж [13]
М 859433 129498125604...243500142591 258,716 1994 Дэвид Словински и Пол Гейдж [13]
М 1257787 412245773621...976089366527 378,632 1996 Дэвид Словински и Пол Гейдж [13]
М 1398269 814717564412...868451315711 420,921 1996 ГИМПС , Джоэл Арменго
М 2976221 623340076248...743729201151 895,932 1997 GIMPS , Гордон Спенс
М 3021377 127411683030...973024694271 909,526 1998 GIMPS , Роланд Кларксон
М 6972593 437075744127...142924193791 2,098,960 1999 GIMPS , Наян Хаджратвала
М 13466917 924947738006...470256259071 4,053,946 2001 GIMPS , Майкл Кэмерон
М 20996011 125976895450...762855682047 6,320,430 2003 GIMPS , Майкл Шафер
М 24036583 299410429404...882733969407 7,235,733 2004 GIMPS , Джош Финдли
М 25964951 122164630061...280577077247 7,816,230 2005 ГИМПС , Мартин Новак
М 30402457 315416475618...411652943871 9,152,052 2005 GIMPS , Университета Центрального Миссури профессора Кертис Купер и Стивен Бун
М 32582657 124575026015...154053967871 9,808,358 2006 GIMPS , Кертис Купер и Стивен Бун
М 43112609 316470269330...166697152511 12,978,189 2008 ГИМПС , Эдсон Смит
М 57885161 581887266232...071724285951 17,425,170 2013 GIMPS , Кертис Купер
М 74207281 300376418084...391086436351 22,338,618 2016 GIMPS , Кертис Купер
М 77232917 467333183359...069762179071 23,249,425 2017 ГИМПС , Джонатан Пейс
М 82589933 148894445742...325217902591 24,862,048 2018 GIMPS , Патрик Ларош

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

Двадцать крупнейших простых чисел известных

Список из 5000 крупнейших известных простых чисел поддерживается PrimePages . [16] двадцать крупнейших из которых перечислены ниже. [17]

Классифицировать Число Обнаруженный Цифры Форма Ссылка
1 2 82589933 − 1 2018-12-07 24,862,048 Мерсенн [1]
2 2 77232917 − 1 2017-12-26 23,249,425 Мерсенн [18]
3 2 74207281 − 1 2016-01-07 22,338,618 Мерсенн [19]
4 2 57885161 − 1 2013-01-25 17,425,170 Мерсенн [20]
5 2 43112609 − 1 2008-08-23 12,978,189 Мерсенн [21]
6 2 42643801 − 1 2009-06-04 12,837,064 Мерсенн [22]
7 Φ 3 (−516693 1048576 ) 2023-10-02 11,981,518 Обобщенный уникальный [23]
8 Φ 3 (−465859 1048576 ) 2023-05-31 11,887,192 Обобщенный уникальный [24]
9 2 37156667 − 1 2008-09-06 11,185,272 Мерсенн [21]
10 2 32582657 − 1 2006-09-04 9,808,358 Мерсенн [25]
11 10223 × 2 31172165 + 1 2016-10-31 9,383,761 Прот [26]
12 2 30402457 − 1 2005-12-15 9,152,052 Мерсенн [27]
13 2 25964951 − 1 2005-02-18 7,816,230 Мерсенн [28]
14 2 24036583 − 1 2004-05-15 7,235,733 Мерсенн [29]
15 1963736 1048576 + 1 2022-09-24 6,598,776 Обобщенный Ферма [30]
16 1951734 1048576 + 1 2022-08-09 6,595,985 Обобщенный Ферма [31]
17 202705 × 2 21320516 + 1 2021-11-25 6,418,121 Прот [32]
18 2 20996011 − 1 2003-11-17 6,320,430 Мерсенн [33]
19 1059094 1048576 + 1 2018-10-31 6,317,602 Обобщенный Ферма [34]
20 3 × 2 20928756 − 1 2023-07-05 6,300,184 Сабит [35]

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

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

  1. ^ Jump up to: Перейти обратно: а б с «Проект GIMPS обнаружил самое большое известное простое число: 2». 82,589,933 -1» . Mersenne Research, Inc. 21 декабря 2018 г. Дата обращения 21 декабря 2018 г.
  2. ^ «Самые большие известные простые числа – результаты поиска в базе данных» . Прайм страницы . Проверено 19 марта 2023 г.
  3. ^ Jump up to: Перейти обратно: а б Колдуэлл, Крис. «Самое большое известное простое число по годам: краткая история» . Прайм страницы . Проверено 19 марта 2023 г.
  4. ^ Последнее не-Мерсенновское самое большое известное простое число было 391 581 ⋅ 2. 216,193 − 1 ; см. также «Самое большое известное простое число по годам: краткая история», первоначально написанное Колдуэллом.
  5. ^ «Идеальные числа» . Пенсильванский государственный университет . Проверено 6 октября 2019 г. Интересное примечание касается двоичного представления этих чисел...
  6. ^ «Обнаружено 51-е известное число простых чисел Мерсенна» .
  7. ^ Jump up to: Перейти обратно: а б с «Рекордное простое число из 12 миллионов цифр принесет приз в 100 000 долларов» . Фонд электронных границ . Фонд электронных границ . 14 октября 2009 года . Проверено 26 ноября 2011 г.
  8. ^ Electronic Frontier Foundation, Большой приз Big Prime Nets .
  9. ^ «Лучшие изобретения 2008 — 29. 46-е число чисел Мерсенна» . Время . Компания Time Inc. 29 октября 2008 года. Архивировано из оригинала 2 ноября 2008 года . Проверено 17 января 2012 г.
  10. ^ «GIMPS от Mersenne Research, Inc» . mersenne.org . Проверено 21 ноября 2022 г.
  11. ^ Эдвард Сандифер, К. (19 ноября 2014 г.). Как Эйлер сделал еще больше . Математическая ассоциация Америки. ISBN  9780883855843 .
  12. ^ Дж. Миллер , Большие простые числа . Природа 168, 838 (1951).
  13. ^ Jump up to: Перейти обратно: а б с д и ж г час я Лэндон Курт Нолл , Большое простое число, найденное суперкомпьютером SGI/Cray .
  14. ^ Письма в редакцию . Американский математический ежемесячный журнал 97, вып. 3 (1990), с. 214. По состоянию на 22 мая 2020 г.
  15. ^ Код подтверждения: Z , The Prime Pages .
  16. ^ «База данных простых чисел: домашняя страница списка крупнейших известных простых чисел» . t5k.org/primes . Проверено 19 марта 2023 г.
  17. ^ «Двадцать лучших: самые большие известные простые числа» . Проверено 19 марта 2023 г.
  18. ^ «Проект GIMPS обнаружил самое большое известное простое число: 2». 77,232,917 -1» . mersenne.org . Отличный интернет-поиск простых чисел Мерсенна . Получено 3 января 2018 г.
  19. ^ «Проект GIMPS обнаружил самое большое известное простое число: 2». 74,207,281 -1» . mersenne.org . Отличный поиск простых чисел Мерсенна в Интернете . Получено 29 сентября 2017 г.
  20. ^ «ГИМПС обнаруживает 48-е число простых чисел Мерсенна, 2». 57,885,161 -1 теперь является самым большим известным простым числом» . mersenne.org . Отличный поиск простых чисел Мерсенна в Интернете . 5 февраля 2013 г. Проверено 29 сентября 2017 г.
  21. ^ Jump up to: Перейти обратно: а б «GIMPS обнаружил 45-е и 46-е простые числа Мерсенна, 2 43,112,609 -1 теперь является самым большим известным простым числом» . mersenne.org . Отличный поиск простых чисел Мерсенна в Интернете . 15 сентября 2008 г. Проверено 29 сентября 2017 г.
  22. ^ «ГИМПС обнаруживает 47-е число Мерсенна, 2». 42,643,801 -1 — новейшее, но не самое большое из известных простых чисел Мерсенна» . mersenne.org . Отличный поиск простых чисел Мерсенна в Интернете . 12 апреля 2009 г. Проверено 29 сентября 2017 г.
  23. ^ «Простые числа PrimePage: Phi(3, - 516693^1048576)» . t5k.org .
  24. ^ «Простые числа PrimePage: Phi(3, - 465859^1048576)» . t5k.org .
  25. ^ «GIMPS обнаруживает 44-е число простого числа Мерсенна, 2». 32,582,657 -1 теперь является самым большим известным простым числом» . mersenne.org . Отличный поиск простых чисел Мерсенна в Интернете . 11 сентября 2006 г. Проверено 29 сентября 2017 г.
  26. ^ «Подпроект PrimeGrid «Семнадцать или крах»» (PDF) . primegrid.com . ПраймГрид . Проверено 30 сентября 2017 г.
  27. ^ «ГИМПС обнаруживает 43-е число Мерсенна-Прайм, 2». 30,402,457 -1 теперь является самым большим известным простым числом» . mersenne.org . Отличный поиск простых чисел Мерсенна в Интернете . 24 декабря 2005 г. Проверено 29 сентября 2017 г.
  28. ^ «GIMPS обнаруживает 42-й номер Мерсенна-Прайм, 2». 25,964,951 -1 теперь является самым большим известным простым числом» . mersenne.org . Отличный поиск простых чисел Мерсенна в Интернете . 27 февраля 2005 г. Проверено 29 сентября 2017 г.
  29. ^ «ГИМПС обнаруживает 41-е число Мерсенна-Прайм, 2». 24,036,583 -1 теперь является самым большим известным простым числом» . mersenne.org . Отличный поиск простых чисел Мерсенна в Интернете . 28 мая 2004 г. Проверено 29 сентября 2017 г.
  30. ^ «Обобщенный поиск простых чисел Ферма PrimeGrid» (PDF) . primegrid.com . ПраймГрид . Проверено 7 октября 2022 г.
  31. ^ «Обобщенный поиск простых чисел Ферма PrimeGrid» (PDF) . primegrid.com . ПраймГрид . Проверено 17 сентября 2022 г.
  32. ^ «Расширенная задача Серпинского PrimeGrid: поиск простых чисел» (PDF) . primegrid.com . ПраймГрид . Проверено 28 декабря 2021 г.
  33. ^ «ГИМПС обнаруживает 40-е простое число Мерсенна, 2». 20,996,011 -1 теперь является самым большим известным простым числом» . mersenne.org . Отличный поиск простых чисел Мерсенна в Интернете . 2 декабря 2003 г. Проверено 29 сентября 2017 г.
  34. ^ «Обобщенный поиск простых чисел Ферма PrimeGrid» (PDF) . primegrid.com . ПраймГрид . Проверено 7 ноября 2018 г.
  35. ^ «Поиск PrimeGrid 321 Prime» (PDF) . primegrid.com . ПраймГрид . Проверено 17 июля 2023 г.

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Largest_known_prime_number&oldid=1224149708"