В математике , А Мерсенна является простым числом , то есть один меньше , чем степень два . То есть это простое число вида M n = 2 n - 1 для некоторого целого n . Они названы в честь Марина Мерсенна , французского монаха-миним , изучавшего их в начале 17 века. Если п является составным числом , то так 2 п - 1 . Следовательно, эквивалентное определение простых чисел Мерсенна состоит в том, что они являются простыми числами вида M p = 2p - 1для некоторого простого числа p .
Названный в честь | Марин Мерсенн |
---|---|
Количество известных терминов | 51 |
Предполагаемый нет. условий | Бесконечный |
подпоследовательности из | Числа Мерсенна |
Первые триместры | 3 , 7 , 31 , 127 , 8191 |
Самый большой известный термин | 2 82,589,933 - 1 (7 декабря 2018 г.) |
Индекс OEIS |
|
Показатели степени n, которые дают простые числа Мерсенна, равны 2, 3, 5, 7, 13, 17, 19, 31, ... (последовательность A000043 в OEIS ), а результирующие простые числа Мерсенна равны 3 , 7 , 31 , 127 , 8191, 131071, 524287, 2147483647 , ... (последовательность A000668 в OEIS ).
Числа вида M n = 2 n - 1 без требования простоты могут называться числами Мерсенна . Иногда, однако, к числам Мерсенна добавляется дополнительное требование, чтобы n было простым. Наименьшее составное число Мерсенна с простым показателем n равно 2 11 - 1 = 2047 = 23 × 89 .
Простые числа Мерсенна изучались в древности из-за их тесной связи с совершенными числами : теорема Евклида – Эйлера утверждает взаимно однозначное соответствие между четными совершенными числами и простыми числами Мерсенна. Многие из самых больших известных простых чисел являются простыми числами Мерсенна, потому что числа Мерсенна легче проверить на простоту.
По состоянию на октябрь 2020 [ссылка]года известно 51 простое число Мерсенна. Самым крупным известным простым числом , 2 82589933 - 1 , является простым Мерсенна. [1] С 1997 года все вновь обретенной простые числа Мерсенна были обнаружены Большой Интернет Мерсенна Поиск , в распределенной вычислительной проекта. В декабре 2020 года была пройдена важная веха в проекте после того, как все экспоненты ниже 100 миллионов были проверены хотя бы один раз. [2]
О простых числах Мерсенна
Бесконечно много простых чисел Мерсенна?
Многие фундаментальные вопросы о простых числах Мерсенна остаются нерешенными. Неизвестно даже, конечно или бесконечно множество простых чисел Мерсенна. Гипотеза Ленстры – Померанса – Вагстаффа утверждает, что существует бесконечно много простых чисел Мерсенна, и предсказывает порядок их роста . Также неизвестно, являются ли составными бесконечно много чисел Мерсенна с простыми показателями , хотя это следовало бы из широко распространенных гипотез о простых числах, например, бесконечности простых чисел Софи Жермен, конгруэнтных 3 ( mod 4 ). Для этих простых чисел р , 2 р + 1 (который также является первичным) , разделит М р , например, 23 | M 11 , 47 | M 23 , 167 | M 83 , 263 | M 131 , 359 | M 179 , 383 | M 191 , 479 | M 239 и 503 | M 251 (последовательность A002515 в OEIS ). Поскольку для этих простых чисел p , 2 p + 1 конгруэнтно 7 по модулю 8, поэтому 2 является квадратичным вычетом по модулю 2 p + 1 , а мультипликативный порядок 2 по модулю 2 p + 1 должен делить= p . Поскольку p простое число, оно должно быть p или 1. Однако оно не может быть 1, посколькуи 1 не имеет простых делителей , поэтому это должно быть p . Следовательно, 2 p + 1 делит а также не может быть простым.
Первые четыре простых числа Мерсенна - это M 2 = 3 , M 3 = 7 , M 5 = 31 и M 7 = 127, и поскольку первое простое число Мерсенна начинается с M 2 , все простые числа Мерсенна конгруэнтны 3 (mod 4). За исключением M 0 = 0 и M 1 = 1 , все другие числа Мерсенна также конгруэнтны 3 (mod 4). Следовательно, при простой факторизации числа Мерсенна ( ≥ M 2 ) должен быть хотя бы один простой множитель, конгруэнтный 3 (mod 4).
Основная теорема о числах Мерсенна утверждает, что если M p простое, то показатель p также должен быть простым. Это следует из тождества
Это исключает простоту чисел Мерсенна с составным показателем, например M 4 = 2 4 - 1 = 15 = 3 × 5 = (2 2 - 1) × (1 + 2 2 ) .
Хотя приведенные выше примеры могут предполагать, что M p является простым для всех простых чисел p , это не так, и наименьший контрпример - это число Мерсенна.
- М 11 = 2 11 - 1 = 2047 = 23 × 89 .
Имеющиеся данные свидетельствуют о том, что случайно выбранное число Мерсенна с гораздо большей вероятностью будет простым, чем произвольно выбранное случайным образом нечетное целое число аналогичного размера. [3] Тем не менее, простые значения M p, по- видимому, становятся все более редкими с увеличением p . Например, восемь из первых 11 простых чисел p приводят к простому числу Мерсенна M p (правильные члены в исходном списке Мерсенна), в то время как M p является простым только для 43 из первых двух миллионов простых чисел (до 32 452 843).
Отсутствие какого-либо простого теста для определения того, является ли данное число Мерсенна простым, делает поиск простых чисел Мерсенна сложной задачей, поскольку числа Мерсенна растут очень быстро. Тест на простоту Лукаса – Лемера (LLT) - это эффективный тест на простоту, который значительно помогает в решении этой задачи, значительно упрощая проверку простоты чисел Мерсенна по сравнению с большинством других чисел того же размера. Поиск самого большого из известных простых чисел стал чем-то вроде культа . Следовательно, на поиск новых простых чисел Мерсенна было затрачено большое количество компьютерных мощностей, большая часть которых теперь выполняется с использованием распределенных вычислений .
Арифметика по модулю числа Мерсенна особенно эффективна на двоичном компьютере , что делает их популярным выбором, когда требуется простой модуль, например, генератор случайных чисел Парка – Миллера . Чтобы найти примитивный многочлен порядка чисел Мерсенна, необходимо знать факторизацию этого числа, поэтому простые числа Мерсенна позволяют находить примитивные многочлены очень высокого порядка. Такие примитивные трехчлены используются в генераторах псевдослучайных чисел с очень большими периодами, таких как твистер Мерсенна , обобщенный регистр сдвига и генераторы Фибоначчи с запаздыванием .
Совершенные числа
Простые числа Мерсенна M p тесно связаны с совершенными числами . В 4 веке до нашей эры Евклид доказал, что если 2 p - 1 простое число, то 2 p - 1 (2 p - 1 ) - совершенное число. В XVIII веке Леонард Эйлер доказал, что, наоборот, все четные совершенные числа имеют такую форму. [4] Это известно как теорема Евклида – Эйлера . Неизвестно, есть ли какие-нибудь нечетные совершенные числа .
История
2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
---|---|---|---|---|---|---|---|
23 | 29 | 31 год | 37 | 41 год | 43 год | 47 | 53 |
59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 |
137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 |
269 | 271 | 277 | 281 | 283 | 293 | 307 | 311 |
Первые 64 простых показателя степени, соответствующие простым числам Мерсенна, заштрихованы голубым и жирным шрифтом, а те, которые, как полагал Мерсенн, сделали красным и жирным шрифтом. |
Простые числа Мерсенна получили свое название от французского ученого 17-го века Марина Мерсенна , который составил список простых чисел Мерсенна с показателями до 257. Показатели, перечисленные Мерсенном, были следующими:
- 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.
Его список воспроизводил известные простые числа своего времени с показателями до 19. Его следующая запись, 31, была правильной, но затем список стал в значительной степени неверным, поскольку Мерсенн ошибочно включил M 67 и M 257 (которые являются составными) и пропустил M 61. , M 89 и M 107 (простые). Мерсенн не дал особых указаний на то, как он составил свой список. [5]
Эдуард Лукас доказал в 1876 году, что M 127 действительно простое, как утверждал Мерсенн. Это было самое большое известное простое число за 75 лет и самое большое, когда-либо найденное вручную (без помощи компьютеров). [ необходима цитата ] M 61 был определен как простое число в 1883 году Иваном Михеевичем Первушиным , хотя Мерсенн утверждал, что оно составное, и по этой причине его иногда называют числом Первушина. Это было второе по величине известное простое число, и оставалось им до 1911 года. Лукас показал еще одну ошибку в списке Мерсенна в 1876 году. Не найдя множителя, Лукас продемонстрировал, что M 67 на самом деле составное. Никакой фактор не был найден до знаменитого выступления Фрэнка Нельсона Коула в 1903 году. [6] Не говоря ни слова, он подошел к доске и возвысил 2 до 67-й степени, а затем вычел единицу. На другой стороне доски он умножил 193 707 721 × 761 838 257 287 и получил то же число, затем вернулся на свое место (под аплодисменты), не говоря ни слова. [7] Позже он сказал, что на поиск результата у него ушло «три года воскресенья». [8] Правильный список всех простых чисел Мерсенна в этом диапазоне чисел был завершен и тщательно проверен только примерно через три столетия после того, как Мерсенн опубликовал свой список.
Поиск простых чисел Мерсенна
Доступны быстрые алгоритмы поиска простых чисел Мерсенна, и по состоянию на июнь 2019 г.[Обновить]семь самых больших известных простых чисел - простые числа Мерсенна.
Первые четыре простых числа Мерсенна M 2 = 3 , M 3 = 7 , M 5 = 31 и M 7 = 127 были известны в древности. Пятый, M 13 = 8191 , был обнаружен анонимно до 1461 года; следующие два ( M 17 и M 19 ) были обнаружены Пьетро Катальди в 1588 году. Спустя почти два столетия Леонард Эйлер в 1772 году подтвердил , что M 31 является простым числом. Следующим (в историческом, а не в числовом порядке) был M 127 , найденная Эдуар Лукас в 1876 году, а затем М 61 от Ivan Михеевич Первушиным в 1883. еще два ( М 89 и М 107 ) были обнаружены в начале 20 - го века, на RE Сил в 1911 и 1914, соответственно.
Лучшим известным в настоящее время методом проверки простоты чисел Мерсенна является критерий простоты Лукаса – Лемера . В частности, можно показать , что для простого р > 2 , М р = 2 р - 1 является простым тогда и только тогда , когда M P делит S р - 2 , где ˙s 0 = 4 и S K = ( S K - 1 ) 2 - 2 при k > 0 .
В эпоху ручного расчета все показатели до 257 включительно были проверены с помощью теста Лукаса – Лемера и оказались составными. Заметный вклад внес профессор физики Йельского университета на пенсии Гораций Скаддер Улер, который провел расчеты для показателей 157, 167, 193, 199, 227 и 229. [9] К сожалению для этих исследователей, интервал, который они тестировали, содержит наибольший из известных значений. относительный разрыв между простыми числами Мерсенна: следующий показатель простого числа Мерсенна, 521, окажется более чем в четыре раза больше, чем предыдущий рекорд, равный 127.
Поиск простых чисел Мерсенна произвел революцию с появлением электронных цифровых компьютеров. Алан Тьюринг искал их на Manchester Mark 1 в 1949 году, [10] но первое успешное определение простого числа Мерсенна, M 521 , таким образом было достигнуто в 22:00 30 января 1952 года с использованием Национального бюро США. Стандарты Western Automatic Computer (SWAC) в Институте численного анализа Калифорнийского университета в Лос-Анджелесе под руководством Лемера с компьютерной поисковой программой, написанной и управляемой профессором Р. М. Робинсоном . Это было первое простое число Мерсенна, идентифицированное за тридцать восемь лет; следующий, M 607 , был обнаружен компьютером чуть менее чем через два часа. Еще три - M 1279 , M 2203 и M 2281 - были обнаружены той же программой в течение следующих нескольких месяцев. M 4253 - первое простое число Мерсенна, которое является титаническим , M 44 497 - первое гигантское , а M 6 972 593 - первое мегапростое число, которое было обнаружено, будучи простым числом , состоящим не менее чем из 1 000 000 цифр. [11] Все трое были первыми известными простыми числами такого размера. Количество цифр в десятичном представлении М п равна ⌊ п × войти 10 2⌋ + 1 , где ⌊ х ⌋ обозначает функцию пол (или , что эквивалентно ⌊log 10 М п ⌋ + 1 ).
В сентябре 2008 года математики из Калифорнийского университета в Лос-Анджелесе, участвовавшие в Большом Интернет-поиске Мерсенна Прайм (GIMPS), выиграли часть приза в 100 000 долларов от Electronic Frontier Foundation за открытие почти 13-миллионного числа Мерсенна. Приз, окончательно подтвержденный в октябре 2009 года, - это первое известное простое число с минимум 10 миллионами цифр. Простое число было обнаружено на Dell OptiPlex 745 23 августа 2008 года. Это было восьмое простое число Мерсенна, обнаруженное в Калифорнийском университете в Лос-Анджелесе. [12]
12 апреля 2009 года журнал сервера GIMPS сообщил, что, возможно, было найдено 47-е простое число Мерсенна. Находку впервые заметили 4 июня 2009 года, а неделю спустя подтвердили. Простое число - 2 42 643 801 - 1 . Хотя в хронологическом порядке это 47-е открытое простое число Мерсенна, оно меньше самого большого из известных в то время, которое было 45-м открытым.
25 января 2013 года Кертис Купер , математик из Университета Центрального Миссури , обнаружил 48-е простое число Мерсенна 2 57 885 161 - 1 (число из 17 425 170 цифр) в результате поиска, выполненного сетью серверов GIMPS. [13]
19 января 2016 года Купер опубликовал свое открытие 49-го простого числа Мерсенна 2 74 207 281 - 1 (число из 22 338 618 цифр) в результате поиска, выполненного сетью серверов GIMPS. [14] [15] [16] Это было четвертое простое число Мерсенна, обнаруженное Купером и его командой за последние десять лет.
2 сентября 2016 года система Great Internet Mersenne Prime Search завершила проверку всех тестов ниже M 37 156 667 , тем самым официально подтвердив свою позицию 45-го простого числа Мерсенна. [17]
3 января 2018 года было объявлено, что Джонатан Пейс, 51-летний инженер-электрик, живущий в Джермантауне, штат Теннесси , нашел 50-е простое число Мерсенна, 2 77 232 917 - 1 (число из 23 249 425 цифр), в результате поиск, выполняемый сетью серверов GIMPS. [18] Открытие было сделано компьютером в офисе церкви в том же городе. [19] [20]
21 декабря 2018 года было объявлено, что The Great Internet Mersenne Prime Search (GIMPS) обнаружил наибольшее известное простое число 2 82 589 933 - 1 , состоящее из 24 862 048 цифр. Компьютер, вызванный Патриком Ларошем из Окалы, Флорида, сделал находку 7 декабря 2018 г. [21]
Теоремы о числах Мерсенна
- Если a и p натуральные числа такие, что a p - 1 простое, то a = 2 или p = 1 .
- Доказательство : a ≡ 1 ( mod a - 1) . Тогда a p ≡ 1 (mod a - 1) , поэтому a p - 1 ≡ 0 (mod a - 1) . Таким образом, a - 1 | а п - 1 . Однако a p - 1 простое число, поэтому a - 1 = a p - 1 или a - 1 = ± 1 . В первом случае a = a p , следовательно, a = 0, 1 (противоречие, поскольку ни −1, ни 0 не являются простыми числами) или p = 1. Во втором случае a = 2 или a = 0 . Однако если a = 0 , 0 p - 1 = 0 - 1 = −1, что не является простым числом. Следовательно, a = 2 .
- Если 2 p - 1 простое число, то p простое число.
- Доказательство . Предположим, что p составное, поэтому можно записать p = ab с a и b > 1 . Тогда 2 p - 1 = 2 ab - 1 = (2 a ) b - 1 = (2 a - 1) ( (2 a ) b −1 + (2 a ) b −2 +… + 2 a + 1 ), поэтому 2 п - 1 составное. Напротив, если 2 p - 1 простое число, то p простое число.
- Если p нечетное простое число, то каждое простое число q, которое делит 2 p - 1, должно быть 1 плюс кратное 2 p . Это верно, даже когда 2 p - 1 простое число.
- Например, 2 5 - 1 = 31 простое число, а 31 = 1 + 3 × (2 × 5) . Составной пример: 2 11-1 = 23 × 89 , где 23 = 1 + (2 × 11) и 89 = 1 + 4 × (2 × 11) .
- Доказательство : По малой теореме Ферма , д является фактором 2 д -1 - 1 . Так как д является фактором 2 р - 1 , для всех положительных целых чисел с , д является также фактор 2 шт - 1 . Поскольку p простое число, а q не делится на 2 1 - 1 , p также является наименьшим положительным целым числом x таким, что q делится на 2 x - 1 . В результате для всех положительных целых чисел x , q является фактором 2 x - 1 тогда и только тогда, когда p является фактором x . Поэтому, поскольку д является фактором 2 д -1 - 1 , р является фактором д - 1 , так д = 1 ( по модулю р ) . Кроме того, поскольку q делится на 2 p - 1 , что нечетно, q нечетно. Следовательно, q ≡ 1 (mod 2 p ) .
- Этот факт приводит к доказательству теоремы Евклида , которая утверждает бесконечность простых чисел, в отличие от доказательства, написанного Евклидом: для каждого нечетного простого числа p все простые числа, делящие 2 p - 1 , больше p ; таким образом, всегда есть простые числа большего размера, чем любое конкретное простое число.
- Из этого факта следует, что для любого простого числа p > 2 существует хотя бы одно простое число вида 2 kp +1, меньшее или равное M p для некоторого целого числа k .
- Если p нечетное простое число, то каждое простое число q, которое делит 2 p - 1 , сравнимо с ± 1 (mod 8) .
- Доказательство : 2 p +1 2 (mod q ) , поэтому 21/2(p + 1) - квадратный корень из 2 по модулю q . По квадратичной взаимности каждый простой модуль, в котором число 2 имеет квадратный корень, конгруэнтен ± 1 ( модуль 8) .
- Простое число Мерсенна не может быть простым числом Вифериха .
- Доказательство . Мы показываем, что если p = 2 m - 1 простое число Мерсенна, то сравнение 2 p −1 ≡ 1 (mod p 2 ) неверно. По малой теореме Ферма m | п - 1 . Следовательно, можно записать p - 1 = mλ . Если данное сравнение выполняется, то p 2 | 2 mλ - 1 , поэтому 0 ≡ 2 мλ - 1/2 мес - 1 Знак равно 1 + 2 м + 2 2 м + ... + 2 ( λ - 1) м ≡ - λ mod (2 м - 1) . Следовательно, 2 m - 1 | λ , а значит, λ ≥ 2 m - 1 . Это приводит к p - 1 ≥ m (2 m - 1) , что невозможно, поскольку m ≥ 2 .
- Если т и п являются натуральные числа , то т и п являются взаимно простыми , если и только если 2 м - 1 и 2 п - 1 взаимно просты. Следовательно, простое число делит не более одного простого показателя Мерсенна. [22] То есть набор пагубных чисел Мерсенна попарно взаимно прост.
- Если р и 2 р + 1 оба штриха ( это означает , что р является главным Софи Жермен ), и р является конгруэнтно с 3 ( по модулю 4) , затем 2 р + 1 делит 2 р - 1 . [23]
- Пример : 11 и 23 являются простыми числами, и 11 = 2 × 4 + 3 , поэтому 23 делит 2 11 - 1 .
- Доказательство . Пусть q равно 2 p + 1 . По малой теореме Ферма 2 2 p 1 (mod q ) , поэтому либо 2 p ≡ 1 (mod q ), либо 2 p ≡ −1 (mod q ) . Если последнее верно, то 2 p +1 = (21/2( p + 1) ) 2 ≡ −2 (mod q ) , поэтому −2 будет квадратичным вычетом по модулю q . Однако, поскольку p конгруэнтно 3 (mod 4) , q конгруэнтно 7 (mod 8) и, следовательно, 2 является квадратичным вычетом по модулю q . Кроме того, поскольку q конгруэнтно 3 (mod 4) , −1 является квадратичным невычетом по модулю q , поэтому −2 является произведением вычета и невычета и, следовательно, является невычетом, противоречие. Следовательно, первое сравнение должно быть верным и 2 p + 1 делит M p .
- Все составные делители простых экспонент чисел Мерсенна являются сильными псевдопростыми числами с основанием 2.
- За исключением 1, число Мерсенна не может быть совершенной степенью. То есть, согласно теореме Михэилеску , уравнение 2 m - 1 = n k не имеет решений, где m , n и k - целые числа с m > 1 и k > 1 .
Список известных простых чисел Мерсенна
В таблице ниже перечислены все известные простые числа Мерсенна (последовательность A000043 ( p ) и A000668 ( M p ) в OEIS ):
# | п | M p | M p цифр | Обнаруженный | Первооткрыватель | Используемый метод |
---|---|---|---|---|---|---|
1 | 2 | 3 | 1 | c. 430 г. до н.э. | Древнегреческие математики [24] | |
2 | 3 | 7 | 1 | c. 430 г. до н.э. | Древнегреческие математики [24] | |
3 | 5 | 31 год | 2 | c. 300 г. до н.э. | Древнегреческие математики [25] | |
4 | 7 | 127 | 3 | c. 300 г. до н.э. | Древнегреческие математики [25] | |
5 | 13 | 8191 | 4 | 1456 [26] | Аноним [27] [28] [26] | Судебное отделение |
6 | 17 | 131071 | 6 | 1588 [29] [26] | Пьетро Катальди [26] | Судебное отделение [30] |
7 | 19 | 524287 | 6 | 1588 [26] | Пьетро Катальди [26] | Судебное отделение [31] |
8 | 31 год | 2147483647 | 10 | 1772 г. | Леонард Эйлер [32] [33] | Пробное деление с модульными ограничениями [34] |
9 | 61 | 2305843009213693951 | 19 | 1883 Ноябрь [35] | Иван Михайлович Первушин | Последовательности Лукаса |
10 | 89 | 618970019642 ... 137449562111 | 27 | 1911 июнь [36] | Ральф Эрнест Пауэрс | Последовательности Лукаса |
11 | 107 | 162259276829 ... 578010288127 | 33 | 1914 г. 1 [37] [38] [39] июня | Ральф Эрнест Пауэрс [40] | Последовательности Лукаса |
12 | 127 | 170141183460 ... 715884105727 | 39 | 1876 г. 10 января [41] | Эдуард Лукас | Последовательности Лукаса |
13 | 521 | 686479766013 ... 291115057151 | 157 | 1952, 30 января [42] | Рафаэль М. Робинсон | LLT / SWAC |
14 | 607 | 531137992816 ... 219031728127 | 183 | 1952, 30 января [42] | Рафаэль М. Робинсон | LLT / SWAC |
15 | 1,279 | 104079321946 ... 703168729087 | 386 | 1952 25 июня [43] | Рафаэль М. Робинсон | LLT / SWAC |
16 | 2 203 | 147597991521 ... 686697771007 | 664 | 1952 7 октября [44] | Рафаэль М. Робинсон | LLT / SWAC |
17 | 2281 | 446087557183 ... 418132836351 | 687 | 1952 г., 9 октября [44] | Рафаэль М. Робинсон | LLT / SWAC |
18 | 3 217 | 259117086013 ... 362909315071 | 969 | 1957 8 сентября [45] | Ганс Ризель | LLT / BESK |
19 | 4 253 | 190797007524 ... 815350484991 | 1,281 | 1961 г. 3 ноября [46] [47] | Александр Гурвиц | LLT / IBM 7090 |
20 | 4 423 | 285542542228 ... 902608580607 | 1,332 | 1961 г. 3 ноября [46] [47] | Александр Гурвиц | LLT / IBM 7090 |
21 год | 9 689 | 478220278805 ... 826225754111 | 2 917 | 1963 11 мая [48] | Дональд Б. Гиллис | LLT / ILLIAC II |
22 | 9 941 | 346088282490 ... 883789463551 | 2 993 | 1963 16 мая [48] | Дональд Б. Гиллис | LLT / ILLIAC II |
23 | 11 213 | 281411201369 ... 087696392191 | 3 376 | 2 июня 1963 г. [48] | Дональд Б. Гиллис | LLT / ILLIAC II |
24 | 19 937 | 431542479738 ... 030968041471 | 6 002 | 1971 4 марта [49] | Брайант Такерман | LLT / IBM 360/91 |
25 | 21 701 | 448679166119 ... 353511882751 | 6 533 | 1978 30 октября [50] | Лэндон Курт Нолл и Лаура Никель | LLT / CDC Cyber 174 |
26 год | 23 209 | 402874115778 ... 523779264511 | 6 987 | 1979 Февраль 9 [50] | Лэндон Курт Нолл | LLT / CDC Cyber 174 |
27 | 44 497 | 854509824303 ... 961011228671 | 13 395 | 1979 8 [51] [52] апреля | Гарри Л. Нельсон и Дэвид Словински | LLT / Cray 1 |
28 год | 86 243 | 536927995502 ... 709433438207 | 25 962 | 1982 25 сентября | Дэвид Словински | LLT / Cray 1 |
29 | 110 503 | 521928313341 ... 083465515007 | 33 265 | 1988 29 января [53] [54] | Уолтер Колкитт и Люк Уэлш | LLT / NEC SX-2 [55] |
30 | 132 049 | 512740276269 ... 455730061311 | 39 751 | 19 сентября 1983 г. [56] | Дэвид Словински | LLT / Cray X-MP |
31 год | 216 091 | 746093103064 ... 103815528447 | 65 050 | 1 сентября 1985 г. [57] [58] | Дэвид Словински | LLT / Cray X-MP / 24 |
32 | 756 839 | 174135906820 ... 328544677887 | 227 832 | 1992 17 февраля | Дэвид Словински и Пол Гейдж | LLT / Harwell Lab 's Cray-2 [59] |
33 | 859 433 | 129498125604 ... 243500142591 | 258 716 | 1994 4 [60] [61] [62] января | Дэвид Словински и Пол Гейдж | LLT / Cray C90 |
34 | 1,257,787 | 412245773621 ... 976089366527 | 378 632 | 3 сентября 1996 г. [63] | Дэвид Словински и Пол Гейдж [64] | LLT / Cray T94 |
35 год | 1,398,269 | 814717564412 ... 868451315711 | 420 921 | 13 ноября 1996 г. | GIMPS / Жоэль Арменго [65] | LLT / Prime95 на базе Pentium 90 МГц |
36 | 2 976 221 | 623340076248 ... 743729201151 | 895 932 | 1997 24 августа | GIMPS / Гордон Спенс [66] | LLT / Prime95 на Pentium 100 МГц |
37 | 3 021 377 | 127411683030 ... 973024694271 | 909 526 | 1998 27 января | GIMPS / Роланд Кларксон [67] | LLT / Prime95 на Pentium 200 МГц |
38 | 6 972 593 | 437075744127 ... 142924193791 | 2,098,960 | 1 июня 1999 г. | GIMPS / Наян Хаджратвала [68] | LLT / Prime95 на 350 МГц Pentium II IBM Aptiva |
39 | 13 466 917 | 924947738006 ... 470256259071 | 4 053 946 | 14 ноября 2001 г. | GIMPS / Майкл Кэмерон [69] | LLT / Prime95 на Athlon T-Bird 800 МГц |
40 | 20 996 011 | 125976895450 ... 762855682047 | 6 320 430 | 17 ноября 2003 г. | GIMPS / Майкл Шафер [70] | LLT / Prime95 на 2 ГГц Dell Dimension |
41 год | 24 036 583 | 299410429404 ... 882733969407 | 7 235 733 | 2004 15 мая | GIMPS / Джош Финдли [71] | LLT / Prime95 на Pentium 4 2,4 ГГц |
42 | 25 964 951 | 122164630061 ... 280577077247 | 7 816 230 | 2005 18 февраля | GIMPS / Мартин Новак [72] | LLT / Prime95 на Pentium 4 2,4 ГГц |
43 год | 30 402 457 | 315416475618 ... 411652943871 | 9 152 052 | 2005 15 декабря | GIMPS / Кертис Купер и Стивен Бун [73] | LLT / Prime95 на Pentium 4 2 ГГц |
44 год | 32 582 657 | 124575026015 ... 154053967871 | 9 808 358 | 2006 4 сентября | GIMPS / Кертис Купер и Стивен Бун [74] | LLT / Prime95 на 3 ГГц Pentium 4 |
45 | 37 156 667 | 202254406890 ... 022308220927 | 11 185 272 | 6 сентября 2008 г. | GIMPS / Ханс-Михаэль Эльвенич [75] | LLT / Prime95 на базе Core 2 Duo с тактовой частотой 2,83 ГГц |
46 | 42 643 801 | 169873516452 ... 765562314751 | 12 837 064 | 4 июня 2009 г. [n 1] | GIMPS / Одд М. Стриндмо [76] [n 2] | LLT / Prime95 на 3 ГГц Core 2 |
47 | 43 112 609 | 316470269330 ... 166697152511 | 12 978 189 | 2008 23 августа | GIMPS / Эдсон Смит [75] | LLT / Prime95 на Dell Optiplex 745 |
56 000 000 | 16 857 679 | Самый низкий непроверенный этап [n 3] | ||||
48 [n 4] | 57 885 161 | 581887266232 ... 071724285951 | 17 425 170 | 2013 25 января | GIMPS / Кертис Купер [77] | LLT / Prime95 на процессоре Intel Core2 Duo E8400 с тактовой частотой 3 ГГц [78] |
49 [n 4] | 74 207 281 | 300376418084 ... 391086436351 | 22 338 618 | 2016 7 января [n 5] | GIMPS / Кертис Купер [14] | LLT / Prime95 на Intel Core i7-4790 |
50 [n 4] | 77 232 917 | 467333183359 ... 069762179071 | 23 249 425 | 2017 Декабрь 26 | GIMPS / Джон Пейс [79] | LLT / Prime95 на процессоре Intel Core i5-6600 с тактовой частотой 3,3 ГГц [80] |
51 [n 4] | 82 589 933 | 148894445742 ... 325217902591 | 24 862 048 | 2018 7 декабря | GIMPS / Патрик Ларош [1] | LLT / Prime95 на Intel Core i5-4590T |
104 000 000 | 31 307 119 | Самый низкий непроверенный этап [n 3] |
- ^ Хотя M 42643801 было впервые сообщено в машине 12 апреля 2009 года, ничеловек не обратил внимание на этот факт до 4 июня 2009 года.
- ^ Стриндмо также использует псевдоним Стиг М. Вальстад.
- ^ a b По состоянию на 5 июня 2021 г. по данным GIMPS .
- ^ a b c d Не проверено, существуют ли какие-либо неоткрытые простые числа Мерсенна между 47-м ( M 43 112 609 ) и 51-м ( M 82 589 933 ) на этой диаграмме; поэтому рейтинг является предварительным.
- ^ Хотя M 74207281 было впервые сообщено в машине 17 сентября 2015 года, ничеловек не обратил внимание на этот факт до 7 января 2016 года.
Все числа Мерсенна ниже 51-го простого числа Мерсенна ( M 82 589 933 ) были проверены по крайней мере один раз, но некоторые из них не проверялись дважды. Простые числа не всегда обнаруживаются в порядке возрастания. Например, 29-е простое число Мерсенна было обнаружено после 30-го и 31-го. Точно так же за M 43 112 609 последовали два меньших простых числа Мерсенна, сначала через две недели, а затем через 9 месяцев. [81] M 43,112,609 было первым обнаруженным простым числом с более чем 10 миллионами десятичных цифр.
Наибольшее известное простое число Мерсенна (2 82 589 933 - 1) также является наибольшим известным простым числом . [1]
Самым большим известным простым числом было простое число Мерсенна с 1952 года, за исключением периода с 1989 по 1992 год. [82]
Факторизация составных чисел Мерсенна
Поскольку это простые числа, простые числа Мерсенна делятся только на 1 и сами по себе. Однако не все числа Мерсенна являются простыми числами Мерсенна, и составные числа Мерсенна можно разложить на множители нетривиально. Числа Мерсенна являются очень хорошими тестовыми примерами для алгоритма сита специального числового поля , поэтому часто наибольшее число, факторизованное с помощью этого алгоритма, было числом Мерсенна. По состоянию на июнь 2019 г.[Обновить], 2 1,193 - 1 является рекордсменом [83] , факторизовавшимся с помощью варианта решета специального числового поля, позволяющего разложить на множители сразу несколько чисел. Ссылки на дополнительную информацию см. В записях целочисленной факторизации . Сито специального числового поля может факторизовать числа с более чем одним большим множителем. Если число имеет только один очень большой множитель, тогда другие алгоритмы могут факторизовать большие числа, сначала находя маленькие множители, а затем выполняя проверку на простоту кофактора. По состоянию на июнь 2019 г.[Обновить], наибольшее факторизация с вероятными допустимыми простыми множителями составляет 2 7 313 983 - 1 = 305 492 080 276 193 × q , где q - вероятное простое число из 2 201 714 цифр. Его открыл Оливер Круз. [84] По состоянию на июнь 2019 г.[Обновить], число Мерсенна M 1277 - наименьшее составное число Мерсенна без известных факторов; у него нет простых множителей меньше 2 67 . [85]
В таблице ниже показаны факторизации первых 20 составных чисел Мерсенна (последовательность A244453 в OEIS ).
п | M p | Факторизация M p |
---|---|---|
11 | 2047 | 23 × 89 |
23 | 8388607 | 47 × 178 481 |
29 | 536870911 | 233 × 1 103 × 2089 |
37 | 137438953471 | 223 × 616 318 177 |
41 год | 2199023255551 | 13,367 × 164,511,353 |
43 год | 8796093022207 | 431 × 9719 × 2 099 863 |
47 | 140737488355327 | 2351 × 4513 × 13 264 529 |
53 | 9007199254740991 | 6 361 × 69 431 × 20 394 401 |
59 | 57646075230343487 | 179 951 × 3 203 431 780 337 (13 цифр) |
67 | 147573952589676412927 | 193,707,721 × 761,838,257,287 (12 цифр) |
71 | 2361183241434822606847 | 228,479 × 48,544,121 × 212,885,833 |
73 | 9444732965739290427391 | 439 × 2,298,041 × 9,361,973,132,609 (13 цифр) |
79 | 604462909807314587353087 | 2,687 × 202,029,703 × 1,113,491,139,767 (13 цифр) |
83 | 967140655691 ... 033397649407 | 167 × 57,912,614,113,275,649,087,721 (23 цифры) |
97 | 158456325028 ... 187087900671 | 11,447 × 13,842,607,235,828,485,645,766,393 (26 цифр) |
101 | 253530120045 ... 993406410751 | 7,432,339,208,719 (13 цифр) × 341,117,531,003,194,129 (18 цифр) |
103 | 101412048018 ... 973625643007 | 2,550,183,799 × 3,976,656,429,941,438,590,393 (22 цифры) |
109 | 649037107316 ... 312041152511 | 745,988,807 × 870,035,986,098,720,987,332,873 (24 цифры) |
113 | 103845937170 ... 992658440191 | 3,391 × 23,279 × 65,993 × 1,868,569 × 1,066,818,132,868,207 (16 цифр) |
131 | 272225893536 ... 454145691647 | 263 × 10,350,794,431,055,162,386,718,619,237,468,234,569 (38 цифр) |
Количество факторов для первых 500 чисел Мерсенна можно найти по адресу (последовательность A046800 в OEIS ).
Числа Мерсенна в природе и в других местах
В математической задаче Tower of Hanoi решение головоломки с башней из n дисков требует M n шагов при условии, что не было сделано никаких ошибок. [86] Число зерен риса на всей шахматной доске в пшеницы и шахматной доске задачи является М 64 .
Астероид с малой планетой номер 8191 назван 8191 Мерсенна после Мерсенн, потому что 8191 является простым Мерсенна ( 3 Juno , 7 Iris , 31 Евфросиния и 127 Johanna найденние и назван в течение 19 - го века). [87]
В геометрии целочисленный прямоугольный треугольник, который является примитивным и имеет четную ногу в степени 2 ( ≥ 4 ), порождает уникальный прямоугольный треугольник, внутренний радиус которого всегда является числом Мерсенна. Например, если четный отрезок равен 2 n + 1, то, поскольку он примитивен, он ограничивает нечетный отрезок равным 4 n - 1 , гипотенузу - 4 n + 1, а ее внутренний радиус - 2 n - 1 . [88]
Числа Мерсенна были изучены относительно общего числа приемных путей недетерминированных машин Тьюринга с полиномиальным временем в 2018 году [89], и были обнаружены интересные включения.
Простые числа Мерсенна – Ферма
Номер Мерсенн-Ферма определяется как2 п р - 1/2 п р - 1 - 1, с простым p , натуральным числом r и может быть записано как MF ( p , r ) . Когда r = 1 , это число Мерсенна. Когда p = 2 , это число Ферма . Единственные известные простые числа Мерсенна – Ферма с r > 1 - это
- MF (2, 2), MF (2, 3), MF (2, 4), MF (2, 5), MF (3, 2), MF (3, 3), MF (7, 2) и MF (59, 2) . [90]
Фактически, MF ( p , r ) = Φ p r (2) , где Φ - круговой многочлен .
Обобщения
Простейшие обобщенные простые числа Мерсенна - это простые числа вида f (2 n ) , где f ( x ) - многочлен низкой степени с малыми целыми коэффициентами . [91] Пример: 2 64 - 2 32 + 1 , в данном случае n = 32 и f ( x ) = x 2 - x + 1 ; другой пример - 2 192 - 2 64 - 1 , в данном случае n = 64 , а f ( x ) = x 3 - x - 1 .
Также естественно попытаться обобщить простые числа вида 2 n - 1 на простые числа вида b n - 1 (для b ≠ 2 и n > 1 ). Однако (см. Также теоремы выше ), b n - 1 всегда делится на b - 1 , поэтому, если последнее не является единицей , первое не является простым. Это можно исправить, разрешив b быть алгебраическим целым числом вместо целого:
Комплексные числа
В кольце целых чисел (на вещественных числах ), если b - 1 - единица , то b равно 2 или 0. Но 2 n - 1 - обычные простые числа Мерсенна, и формула 0 n - 1 ни к чему не приводит. интересно (поскольку он всегда равен −1 для всех n > 0 ). Таким образом, мы можем рассматривать кольцо «целых чисел» на комплексных числах вместо действительных чисел , таких как гауссовские целые числа и целые числа Эйзенштейна .
Гауссовы простые числа Мерсенна
Если мы рассмотрим кольцо гауссовских целых чисел , мы получим случай b = 1 + i и b = 1 - i , и можем спросить ( WLOG ), для какого n число (1 + i ) n - 1 является гауссовым простым числом, которое будет затем называть гауссовым простым числом Мерсенна . [92]
(1 + i ) n - 1 является гауссовским простым числом для следующих n :
- 2, 3, 5, 7, 11, 19, 29, 47, 73, 79, 113, 151, 157, 163, 167, 239, 241, 283, 353, 367, 379, 457, 997, 1367, 3041, 10141, 14699, 27529, 49207, 77291, 85237, 106693, 160423, 203789, 364289, 991961, 1203793, 1667321, 3704053, 4792057, ... (последовательность A057429 в OEIS )
Как и последовательность показателей для обычных простых чисел Мерсенна, эта последовательность содержит только (рациональные) простые числа.
Что касается всех гауссовских простых чисел, нормы (то есть квадраты абсолютных значений) этих чисел являются рациональными простыми числами:
- 5, 13, 41, 113, 2113, 525313, 536903681, 140737471578113, ... (последовательность A182300 в OEIS ).
Простые числа Эйзенштейна-Мерсенна
Можно встретить случаи, когда такое простое число Мерсенна также является простым числом Эйзенштейна , имея вид b = 1 + ω и b = 1 - ω . В этих случаях такие числа называются простыми числами Эйзенштейна-Мерсенна .
(1 + ω ) n - 1 является простым числом Эйзенштейна для следующих n :
- 2, 5, 7, 11, 17, 19, 79, 163, 193, 239, 317, 353, 659, 709, 1049, 1103, 1759, 2029, 5153, 7541, 9049, 10453, 23743, 255361, 534827, 2237561, ... (последовательность A066408 в OEIS )
Нормы (то есть квадраты абсолютных значений) этих простых чисел Эйзенштейна являются рациональными простыми числами:
- 7, 271, 2269, 176419, 129159847, 1162320517, ... (последовательность A066413 в OEIS )
Разделить целое число
Перегруппировать простые числа
Другой способ справиться с тем фактом, что b n - 1 всегда делится на b - 1 , - просто вычесть этот множитель и спросить, какие значения n дают
быть первоклассным. (Целое число b может быть как положительным, так и отрицательным.) Если, например, мы возьмем b = 10 , мы получим n значений:
- 2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, ... (последовательность A004023 в OEIS ),
соответствующие простым числам 11, 1111111111111111111, 11111111111111111111111, ... (последовательность A004022 в OEIS ).
Эти простые числа называются простыми числами повторного объединения. Другой пример: когда мы берем b = −12 , мы получаем n значений:
- 2, 5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, ... (последовательность A057178 в OEIS ),
соответствующие простым числам −11, 19141, 57154490053, ....
Это гипотеза, что для любого целого числа b, которое не является совершенной степенью , существует бесконечно много значений n таких, чтоб н - 1/б - 1простое. (Когда b - идеальная степень, можно показать, что существует не более одного значения n такое, чтоб н - 1/б - 1 простое)
Как минимум n таких, чтоб н - 1/б - 1простое число (начиная с b = 2 , 0, если такого n не существует)
- 2, 3, 2, 3, 2, 5, 3, 0, 2, 17, 2, 5, 3, 3, 2, 3, 2, 19, 3, 3, 2, 5, 3, 0, 7, 3, 2, 5, 2, 7, 0, 3, 13, 313, 2, 13, 3, 349, 2, 3, 2, 5, 5, 19, 2, 127, 19, 0, 3, 4229, 2, 11, 3, 17, 7, 3, 2, 3, 2, 7, 3, 5, 0, 19, 2, 19, 5, 3, 2, 3, 2, ... (последовательность A084740 в OEIS )
Для отрицательных оснований b они равны (начиная с b = −2 , 0, если такого n не существует)
- 3, 2, 2, 5, 2, 3, 2, 3, 5, 5, 2, 3, 2, 3, 3, 7, 2, 17, 2, 3, 3, 11, 2, 3, 11, 0, 3, 7, 2, 109, 2, 5, 3, 11, 31, 5, 2, 3, 53, 17, 2, 5, 2, 103, 7, 5, 2, 7, 1153, 3, 7, 21943, 2, 3, 37, 53, 3, 17, 2, 7, 2, 3, 0, 19, 7, 3, 2, 11, 3, 5, 2, ... (последовательность A084742 в OEIS ) (обратите внимание, что эта последовательность OEIS не допускает n = 2 )
Наименьшее основание b такое, чтоb простое ( n ) - 1/б - 1 просты
- 2, 2, 2, 2, 5, 2, 2, 2, 10, 6, 2, 61, 14, 15, 5, 24, 19, 2, 46, 3, 11, 22, 41, 2, 12, 22, 3, 2, 12, 86, 2, 7, 13, 11, 5, 29, 56, 30, 44, 60, 304, 5, 74, 118, 33, 156, 46, 183, 72, 606, 602, 223, 115, 37, 52, 104, 41, 6, 338, 217, ... (последовательность A066180 в OEIS )
Для отрицательных оснований b они равны
- 3, 2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (последовательность A103795 в OEIS )
Другие обобщенные простые числа Мерсенна
Другое обобщенное число Мерсенна
с a , b любыми взаимно простыми целыми числами, a > 1 и - a < b < a . (Поскольку a n - b n всегда делится на a - b , деление необходимо для того, чтобы была возможность найти простые числа. Фактически, это число совпадает с числом Люка U n ( a + b , ab ) , так как и б являются корни этого квадратного уравнения х 2 - ( + б ) х + AB = 0 , и это число равно 1 , когда п = 1 ) Мы можем спросить , какие п делает это число , взаимно простое. Можно показать, что такие n сами должны быть простыми или равными 4, а n может быть 4 тогда и только тогда, когда a + b = 1 и a 2 + b 2 простое число. (С а 4 - б 4/а - б= ( a + b ) ( a 2 + b 2 ) . Таким образом, в этом случае пара ( a , b ) должна быть ( x + 1, - x ), а x 2 + ( x + 1) 2 должна быть простой. То есть x должен быть в OEIS : A027861 .) Это гипотеза, что для любой пары ( a , b ) такой, что для любого натурального числа r > 1 , a и b не являются одновременно совершенными r -ыми степенями, а −4 ab не идеальная четвертая степень . существует бесконечно много значений n таких, чтоа н - б н/а - бпростое. (Когда a и b оба являются совершенными степенями r для r > 1 или когда −4 ab является совершенной четвертой степенью, можно показать, что существует не более двух значений n с этим свойством, поскольку если это так, тоа н - б н/а - бможно факторизовать алгебраически) Однако это не было доказано ни для одного значения ( a , b ) .
а | б | числа n такие, чтоа н - б н/а - бявляется простым (некоторые большие члены являются только вероятными простыми числами , эти n проверяются до 100000 для | b | ≤ 5 или | b | = a - 1 , 20000 для 5 <| b | < a - 1 ) | Последовательность OEIS |
---|---|---|---|
2 | 1 | 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 431605801 ... ..., 74207281, ..., 77232917, ..., 82589933, ... | A000043 |
2 | −1 | 3, 4 * , 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807 , 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, ..., 13347311, 13372531, ... | A000978 |
3 | 2 | 2, 3, 5, 17, 29, 31, 53, 59, 101, 277, 647, 1061, 2381, 2833, 3613, 3853, 3929, 5297, 7417, 90217, 122219, 173191, 256199, 336353, 485977, 591827, 1059503, ... | A057468 |
3 | 1 | 3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177, 9011, 9551, 36913, 43063, 49681, 57917, 483611, 877843, ... | A028491 |
3 | −1 | 2 * , 3, 5, 7, 13, 23, 43, 281, 359, 487, 577, 1579, 1663, 1741, 3191, 9209, 11257, 12743, 13093, 17027, 26633, 104243, 134227, 152287, 700897 , 1205459, ... | A007658 |
3 | −2 | 3, 4 * , 7, 11, 83, 149, 223, 599, 647, 1373, 8423, 149497, 388897, ... | A057469 |
4 | 3 | 2, 3, 7, 17, 59, 283, 311, 383, 499, 521, 541, 599, 1193, 1993, 2671, 7547, 24019, 46301, 48121, 68597, 91283, 131497, 148663, 184463, 341233, ... | A059801 |
4 | 1 | 2 (других нет) | |
4 | −1 | 2 * , 3 (других нет) | |
4 | −3 | 3, 5, 19, 37, 173, 211, 227, 619, 977, 1237, 2437, 5741, 13463, 23929, 81223, 121271, ... | A128066 |
5 | 4 | 3, 43, 59, 191, 223, 349, 563, 709, 743, 1663, 5471, 17707, 19609, 35449, 36697, 45259, 91493, 246497, 265007, 289937, ... | A059802 |
5 | 3 | 13, 19, 23, 31, 47, 127, 223, 281, 2083, 5281, 7411, 7433, 19051, 27239, 35863, 70327, ... | A121877 |
5 | 2 | 2, 5, 7, 13, 19, 37, 59, 67, 79, 307, 331, 599, 1301, 12263, 12589, 18443, 20149, 27983, ... | A082182 |
5 | 1 | 3, 7, 11, 13, 47, 127, 149, 181, 619, 929, 3407, 10949, 13241, 13873, 16519, 201359, 396413, 1888279, ... | A004061 |
5 | −1 | 5, 67, 101, 103, 229, 347, 4013, 23297, 30133, 177337, 193939, 266863, 277183, 335429, ... | A057171 |
5 | −2 | 2 * , 3, 17, 19, 47, 101, 1709, 2539, 5591, 6037, 8011, 19373, 26489, 27427, ... | A082387 |
5 | −3 | 2 * , 3, 5, 7, 17, 19, 109, 509, 661, 709, 1231, 12889, 13043, 26723, 43963, 44789, ... | A122853 |
5 | −4 | 4 * , 5, 7, 19, 29, 61, 137, 883, 1381, 1823, 5227, 25561, 29537, 300893, ... | A128335 |
6 | 5 | 2, 5, 11, 13, 23, 61, 83, 421, 1039, 1511, 31237, 60413, 113177, 135647, 258413, ... | A062572 |
6 | 1 | 2, 3, 7, 29, 71, 127, 271, 509, 1049, 6389, 6883, 10613, 19889, 79987, 608099, ... | A004062 |
6 | −1 | 2 * , 3, 11, 31, 43, 47, 59, 107, 811, 2819, 4817, 9601, 33581, 38447, 41341, 131891, 196337, ... | A057172 |
6 | −5 | 3, 4 * , 5, 17, 397, 409, 643, 1783, 2617, 4583, 8783, ... | A128336 |
7 | 6 | 2, 3, 7, 29, 41, 67, 1327, 1399, 2027, 69371, 86689, 355039, ... | A062573 |
7 | 5 | 3, 5, 7, 113, 397, 577, 7573, 14561, 58543, ... | A128344 |
7 | 4 | 2, 5, 11, 61, 619, 2879, 2957, 24371, 69247, ... | A213073 |
7 | 3 | 3, 7, 19, 109, 131, 607, 863, 2917, 5923, 12421, ... | A128024 |
7 | 2 | 3, 7, 19, 79, 431, 1373, 1801, 2897, 46997, ... | A215487 |
7 | 1 | 5, 13, 131, 149, 1699, 14221, 35201, 126037, 371669, 1264699, ... | A004063 |
7 | −1 | 3, 17, 23, 29, 47, 61, 1619, 18251, 106187, 201653, ... | A057173 |
7 | −2 | 2 * , 5, 23, 73, 101, 401, 419, 457, 811, 1163, 1511, 8011, ... | A125955 |
7 | −3 | 3, 13, 31, 313, 3709, 7933, 14797, 30689, 38333, ... | A128067 |
7 | −4 | 2 * , 3, 5, 19, 41, 47, 8231, 33931, 43781, 50833, 53719, 67211, ... | A218373 |
7 | −5 | 2 * , 11, 31, 173, 271, 547, 1823, 2111, 5519, 7793, 22963, 41077, 49739, ... | A128337 |
7 | −6 | 3, 53, 83, 487, 743, ... | A187805 |
8 | 7 | 7, 11, 17, 29, 31, 79, 113, 131, 139, 4357, 44029, 76213, 83663, 173687, 336419, 615997, ... | A062574 |
8 | 5 | 2, 19, 1021, 5077, 34031, 46099, 65707, ... | A128345 |
8 | 3 | 2, 3, 7, 19, 31, 67, 89, 9227, 43891, ... | A128025 |
8 | 1 | 3 (других нет) | |
8 | −1 | 2 * (других нет) | |
8 | −3 | 2 * , 5, 163, 191, 229, 271, 733, 21059, 25237, ... | A128068 |
8 | −5 | 2 * , 7, 19, 167, 173, 223, 281, 21647, ... | A128338 |
8 | −7 | 4 * , 7, 13, 31, 43, 269, 353, 383, 619, 829, 877, 4957, 5711, 8317, 21739, 24029, 38299, ... | A181141 |
9 | 8 | 2, 7, 29, 31, 67, 149, 401, 2531, 19913, 30773, 53857, 170099, ... | A059803 |
9 | 7 | 3, 5, 7, 4703, 30113, ... | A273010 |
9 | 5 | 3, 11, 17, 173, 839, 971, 40867, 45821, ... | A128346 |
9 | 4 | 2 (других нет) | |
9 | 2 | 2, 3, 5, 13, 29, 37, 1021, 1399, 2137, 4493, 5521, ... | A173718 |
9 | 1 | (никто) | |
9 | −1 | 3, 59, 223, 547, 773, 1009, 1823, 3803, 49223, 193247, 703393, ... | A057175 |
9 | −2 | 2 * , 3, 7, 127, 283, 883, 1523, 4001, ... | A125956 |
9 | −4 | 2 * , 3, 5, 7, 11, 17, 19, 41, 53, 109, 167, 2207, 3623, 5059, 5471, 7949, 21211, 32993, 60251, ... | A211409 |
9 | −5 | 3, 5, 13, 17, 43, 127, 229, 277, 6043, 11131, 11821, ... | A128339 |
9 | −7 | 2 * , 3, 107, 197, 2843, 3571, 4451, ..., 31517, ... | A301369 |
9 | −8 | 3, 7, 13, 19, 307, 619, 2089, 7297, 75571, 76103, 98897, ... | A187819 |
10 | 9 | 2, 3, 7, 11, 19, 29, 401, 709, 2531, 15787, 66949, 282493, ... | A062576 |
10 | 7 | 2, 31, 103, 617, 10253, 10691, ... | A273403 |
10 | 3 | 2, 3, 5, 37, 599, 38393, 51431, ... | A128026 |
10 | 1 | 2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, ... | A004023 |
10 | −1 | 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... | A001562 |
10 | −3 | 2 * , 3, 19, 31, 101, 139, 167, 1097, 43151, 60703, 90499, ... | A128069 |
10 | −7 | 2 * , 3, 5, 11, 19, 1259, 1399, 2539, 2843, 5857, 10589, ... | |
10 | −9 | 4 * , 7, 67, 73, 1091, 1483, 10937, ... | A217095 |
11 | 10 | 3, 5, 19, 311, 317, 1129, 4253, 7699, 18199, 35153, 206081, ... | A062577 |
11 | 9 | 5, 31, 271, 929, 2789, 4153, ... | A273601 |
11 | 8 | 2, 7, 11, 17, 37, 521, 877, 2423, ... | A273600 |
11 | 7 | 5, 19, 67, 107, 593, 757, 1801, 2243, 2383, 6043, 10181, 11383, 15629, ... | A273599 |
11 | 6 | 2, 3, 11, 163, 191, 269, 1381, 1493, ... | A273598 |
11 | 5 | 5, 41, 149, 229, 263, 739, 3457, 20269, 98221, ... | A128347 |
11 | 4 | 3, 5, 11, 17, 71, 89, 827, 22307, 45893, 63521, ... | A216181 |
11 | 3 | 3, 5, 19, 31, 367, 389, 431, 2179, 10667, 13103, 90397, ... | A128027 |
11 | 2 | 2, 5, 11, 13, 331, 599, 18839, 23747, 24371, 29339, 32141, 67421, ... | A210506 |
11 | 1 | 17, 19, 73, 139, 907, 1907, 2029, 4801, 5153, 10867, 20161, 293831, ... | A005808 |
11 | −1 | 5, 7, 179, 229, 439, 557, 6113, 223999, 327001, ... | A057177 |
11 | −2 | 3, 5, 17, 67, 83, 101, 1373, 6101, 12119, 61781, ... | A125957 |
11 | −3 | 3, 103, 271, 523, 23087, 69833, ... | A128070 |
11 | −4 | 2 * , 7, 53, 67, 71, 443, 26497, ... | A224501 |
11 | −5 | 7, 11, 181, 421, 2297, 2797, 4129, 4139, 7151, 29033, ... | A128340 |
11 | −6 | 2 * , 5, 7, 107, 383, 17359, 21929, 26393, ... | |
11 | −7 | 7, 1163, 4007, 10159, ... | |
11 | −8 | 2 * , 3, 13, 31, 59, 131, 223, 227, 1523, ... | |
11 | −9 | 2 * , 3, 17, 41, 43, 59, 83, ... | |
11 | −10 | 53, 421, 647, 1601, 35527, ... | A185239 |
12 | 11 | 2, 3, 7, 89, 101, 293, 4463, 70067, ... | A062578 |
12 | 7 | 2, 3, 7, 13, 47, 89, 139, 523, 1051, ... | A273814 |
12 | 5 | 2, 3, 31, 41, 53, 101, 421, 1259, 4721, 45259, ... | A128348 |
12 | 1 | 2, 3, 5, 19, 97, 109, 317, 353, 701, 9739, 14951, 37573, 46889, 769543, ... | A004064 |
12 | −1 | 2 * , 5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, ... | A057178 |
12 | −5 | 2 * , 3, 5, 13, 347, 977, 1091, 4861, 4967, 34679, ... | A128341 |
12 | −7 | 2 * , 3, 7, 67, 79, 167, 953, 1493, 3389, 4871, ... | |
12 | −11 | 47, 401, 509, 8609, ... | A213216 |
* Примечание: если b <0 и n четно, то числа n не входят в соответствующую последовательность OEIS.
Гипотеза, связанная с обобщенными простыми числами Мерсенна: [3] [103] (гипотеза предсказывает, где находится следующее обобщенное простое число Мерсенна, если гипотеза верна, то существует бесконечно много простых чисел для всех таких пар ( a , b ) )
Для любых целых чисел a и b, удовлетворяющих условиям:
- а > 1 , - а < Ь < а .
- и б являются взаимно простыми . (таким образом, b не может быть 0)
- Для любого натурального числа г > 1 , и б не как идеальный г - й степеней. (поскольку, когда a и b оба являются совершенными степенями r , можно показать, что существует не более двух значений n таких, чтоа н - б н/а - бявляется простым, и эти п значения г себя или корень из г , или 2)
- −4 ab не является совершенной четвертой степенью (если это так, то число имеет безболевую факторизацию ).
имеет простые числа вида
для простого p простые числа будут распределены около линии наилучшего соответствия
где
и есть около
простые числа этой формы меньше , чем N .
- e - основание натурального логарифма .
- γ - постоянная Эйлера – Маскерони .
- log a - логарифм по основанию a .
- R ( a , b ) ( n ) - n- е простое число видаа п - б п/а - бдля простого p .
- C - константа соответствия данных, которая изменяется в зависимости от a и b .
- δ - константа соответствия данных, которая изменяется в зависимости от a и b .
- m - наибольшее натуральное число, такое что a и - b являются точными 2 m - 1- й степенями.
У нас также есть следующие три свойства:
- Количество простых чисел вида а п - б п/а - б(с простым p ), меньшим или равным n, составляет примерно e γ log a (log a ( n )) .
- Ожидаемое количество простых чисел вида а п - б п/а - бс простым p между n и an около e γ .
- Вероятность того, что номер формы а п - б п/а - бпростое (для простого p ) примерноe γ/p log e ( а ).
Если эта гипотеза верна, то для всех таких пар ( a , b ) пусть q будет n- м простым числом видаа п - б п/а - б, график зависимости log a (log a ( q )) от n почти линейен. (См. [3] )
Когда a = b + 1 , это ( b + 1) n - b n , разность двух последовательных совершенных степеней n , и если a n - b n простое число, тогда a должно быть b + 1 , потому что это делится на a - b .
Наименьшее n таких, что ( b + 1) n - b n простое число, равны
- 2, 2, 2, 3, 2, 2, 7, 2, 2, 3, 2, 17, 3, 2, 2, 5, 3, 2, 5, 2, 2, 229, 2, 3, 3, 2, 3, 3, 2, 2, 5, 3, 2, 3, 2, 2, 3, 3, 2, 7, 2, 3, 37, 2, 3, 5, 58543, 2, 3, 2, 2, 3, 2, 2, 3, 2, 5, 3, 4663, 54517, 17, 3, 2, 5, 2, 3, 3, 2, 2, 47, 61, 19, ... (последовательность A058013 в OEIS )
Наименьшие b такие, что ( b + 1) prime ( n ) - b prime ( n ) простое число, являются
- 1, 1, 1, 1, 5, 1, 1, 1, 5, 2, 1, 39, 6, 4, 12, 2, 2, 1, 6, 17, 46, 7, 5, 1, 25, 2, 41, 1, 12, 7, 1, 7, 327, 7, 8, 44, 26, 12, 75, 14, 51, 110, 4, 14, 49, 286, 15, 4, 39, 22, 109, 367, 22, 67, 27, 95, 80, 149, 2, 142, 3, 11, ... (последовательность A222119 в OEIS )
Смотрите также
- Repunit
- Ферма Прайм
- Сила двух
- Константа Эрдеша – Борвейна
- Гипотезы Мерсенна
- Твистер Мерсенна
- Двойное число Мерсенна
- Prime95 / MPrime
- Отличный Интернет-поиск Mersenne Prime (GIMPS)
- Наибольшее известное простое число
- Титаник Прайм
- Гигантский прайм
- Мегапрайм
- Виферих прайм
- Вагстафф Прайм
- Каллен Прайм
- Вудалл Прайм
- Proth Prime
- Солинас Прайм
- Гипотеза Гиллиса
- Число Вильямса
Рекомендации
- ^ a b c «Проект GIMPS обнаруживает наибольшее известное простое число: 2 82 589 933 -1» . Мерсенна Research, Inc . 21 декабря 2018 . Проверено 21 декабря 2018 года .
- ^ «Отчет о вехах GIMPS» . Mersenne.org . Мерсенна Research, Inc . Дата обращения 5 декабря 2020 .
- ^ а б в Колдуэлл, Крис. «Эвристика: вывод гипотезы Вагстаффа Мерсенна» .
- ^ Крис К. Колдуэлл, Простые числа Мерсенна: история, теоремы и списки
- ↑ Prime Pages, гипотеза Мерсенна .
- ^ Коул, FN (1 декабря 1903 г.). «О факторинге больших чисел» . Бюллетень Американского математического общества . 10 (3): 134–138. DOI : 10.1090 / S0002-9904-1903-01079-9 .
- ^ Белл, ET и математическая ассоциация Америки (1951). Математика, царица и служанка науки . Макгроу-Хилл Нью-Йорк.п. 228.
- ^ «h2g2: Числа Мерсенна» . BBC News . Архивировано из оригинала на 5 декабря 2014 года.
- ^ Гораций С. Улер (1952). «Краткая история исследований чисел Мерсенна и последних огромных простых чисел» . Scripta Mathematica . 18 : 122–131.
- ^ Брайан Нэппер, математический факультет и Mark 1 .
- ^ Премьер Страницы, Премьер Глоссарий: Megaprime .
- ^ Мо II, Томас Х. (27 сентября 2008 г.). «Математики Калифорнийского университета в Лос-Анджелесе открывают простое число, состоящее из 13 миллионов цифр» . Лос-Анджелес Таймс . Проверено 21 мая 2011 .
- ^ Тиа Гхош. «Обнаружено наибольшее простое число» . Scientific American . Проверено 7 февраля 2013 .
- ^ а б Купер, Кертис (7 января 2016 г.). "Открытие простого числа Мерсенна - 2 74207281 - 1 - простое число !" . Мерсенна Research, Inc . Проверено 22 января +2016 .
- ^ Брук, Роберт (19 января 2016 г.). «Простое число с 22 миллионами цифр - самое большое из когда-либо найденных» . Новый ученый . Проверено 19 января +2016 .
- ^ Чанг, Кеннет (21 января 2016 г.). «Новое наибольшее простое число = от 2 до 74 миллионов ... эээ, оно большое» . Нью-Йорк Таймс . Проверено 22 января +2016 .
- ^ «Вехи» . Архивировано из оригинала на 2016-09-03.
- ^ "Мерсенн Прайм Дискавери - 2 ^ 77232917-1 - Прайм!" . www.mersenne.org . Проверено 3 января 2018 .
- ^ «Наибольшее известное простое число, найденное на церковном компьютере» . christianchronicle.org . 12 января 2018.
- ^ «Найдено: особое, невероятно большое простое число» . 5 января 2018.
- ^ «GIMPS обнаруживает наибольшее известное простое число: 2 ^ 82,589,933-1» . Проверено 1 января 2019 .
- ^ Мерсенна страница будет Эджингтон по архивации 2014-10-14 в Wayback Machine
- ^ Колдуэлл, Крис К. «Доказательство результата Эйлера и Лагранжа о делителях Мерсенна» . Prime Pages .
- ^ a b Древние египтяне не упоминали простые числа, и у них не было никакого известного сегодня понятия простых чисел. В папирусе Ринда (1650 г. до н.э.) разложения египетских дробей имеют довольно разные формы для простых и составных чисел, поэтому можно утверждать, что они знали о простых числах. «Египтяне использовали ($) в таблице выше для первых простых чисел r = 3, 5, 7 или 11 (также для r = 23). Вот еще одно интригующее наблюдение: египтяне прекратили использование ($) в 11 предполагает, что они поняли (по крайней мере, некоторые части) Решета Эратосфена за 2000 лет до того, как Эратосфен «открыл» его ». Ринд 2 / п Таблица [найдено 2012-11-11]. В школе Пифагора (р. Около 570 - р. Около 495 г. до н.э.) и пифагорейцев мы находим первые достоверные наблюдения простых чисел. Следовательно, первые два простых числа Мерсенна, 3 и 7, были известны и, возможно, даже были открыты ими. Однако здесь нет ссылки на их особую форму 2 2 - 1 и 2 3 - 1 как таковую. Источники знания простых чисел у пифагорейцев запаздывают. Философ-неоплатоник Ямвлих , н.э. ок. 245 – с. 325, утверждает, что греческий философ-платоник Спевсипп , ок. 408 - 339/8 до н.э., написал книгу под названием « О числах Пифагора» . Согласно Ямвлиху, эта книга была основана на трудах пифагорейца Филолая , ок. 470 – ок. 385 г. до н.э., живший через столетие после Пифагора , 570 - ок. 495 г. до н.э. В своей « Теологии арифметики» в главе «Десятилетие» Ямвлих пишет: «Спевсипп, сын Потона, сестры Платона, и глава Академии до Ксенократа, составил отточенную маленькую книжку из пифагорейских писаний, которые особенно ценились в любое время. и особенно из сочинений Филолая; он озаглавил книгу « О числах Пифагора» . В первой половине книги он элегантно излагает линейные числа [то есть простые числа], многоугольные числа и всевозможные плоские числа, твердые числа и пять фигур, которые относятся к элементам вселенной, обсуждая как их индивидуальные атрибуты, так и их общие черты, а также их соразмерность и взаимность ». Ямвлих «Богословие арифметики» в переводе Робина Уотерфилда, 1988, стр. 112f. [Проверено 11 ноября 2012 г.]. Ямвлих также дает нам прямую цитату из Speusippus книги " , где Speusippus между прочим пишет:« Во- вторых, необходимо для идеального числа [понятие „совершенное число“ не используется здесь в современном смысле] , чтобы содержать равное количество простые и составные числа, вторичные и составные числа ». Ямвлих «Богословие арифметики» в переводе Робина Уотерфилда, 1988, стр. 113. [Проверено 11 ноября 2012 г.]. О греческом оригинальном тексте см. Спевсипп Афинский: Критическое исследование со сборником родственных текстов и комментариями Леонардо Тарана, 1981, с. 140 линий 21-22 [Проверены 2012-11-11] В своих комментариях к Никомаху из Gerasas «ы Введению в арифметику , Ямвлихи также упоминает , что Тимаридас , ca. 400 г. до н.э. - ок. 350 г. до н.э., использует термин прямолинейный для простых чисел, и что Теон из Смирны , эт. 100 г. н.э. в качестве альтернативных терминов используются эвтиметрический и линейный . Никомах Герасинский, Введение в арифметику, 1926, стр. 127 [Проверено 11 ноября 2012 г.] Однако неясно, когда это говорит о том, что Тимарид жил. «В весьма подозрительном отрывке из Ямвлиха Фимарид указан как ученик самого Пифагора». Пифагореизм [Проверено 11.11.2012] До Филолая , ок. 470 – ок. 385 г. до н.э., у нас нет никаких доказательств знания простых чисел.
- ^ а б «Элементы Евклида, книга IX, предложение 36» .
- ^ a b c d e f Арабский математик Исмаил ибн Ибрагим ибн Фаллус (1194–1239) знал первые семь совершенных чисел за много лет до того, как они были обнаружены в Европе; см. Совершенные числа из архива истории математики MacTutor . Справка: Брентьес, Соня (1987). "Die ersten sieben vollkommenen Zahlen und drei Arten befreundeter Zahlen in einem Werk zur elementaren Zahlentheorie von Ismā'īl b. Ibrāhīm b. Fallūs" [Первые семь совершенных чисел и три вида дружественных чисел в работе Исмы по элементарной теории чисел īl b. Ибрахим б. Фаллус]. NTM Schriftenreihe für Geschichte der Naturwissenschaften, Technik und Medizin (на немецком языке). 24 (1): 21–30. OCLC 812888599 . Zbl 0625.01005 ..
- ^ Основные страницы, простые числа Мерсенна: история, теоремы и списки .
- ^ Мы находим самую старую (бесспорную) заметку о результате в Кодексе №. 14908, который происходит от Bibliotheca monasterii ord. S. Benedicti ad S. Emmeramum Ratisbonensis теперь в архиве Bayerische Staatsbibliothek, см. "Хальм, Карл / Лаубманн, Георг фон / Мейер, Вильгельм: Catalogus codicum latinorum Bibliothecae Regiae Monacensis, Bd .: 2,2, Monachii, 1876, стр. 250 ". [проверено 17 сентября 2012 г.] Кодекс №. 14908 состоит из 10 различных средневековых работ по математике и смежным предметам. Авторы большинства этих произведений известны. Некоторые авторы считают монаха Фридерикуса Герхарта (Амман), 1400–1465 (Frater Fridericus Gerhart monachus ordinis sancti Benedicti astrologus profus in monasterio sancti Emmerani diocesis Ratisponensis et in ciuitate eiusdem) автором части, где упоминается простое число 8191. Geschichte Der Mathematik [обнаружено 17 сентября 2012 г.] Вторая рукопись Codex nr. 14908 имеет название «Regulae et instance arithmetica, algebraica, geometrya» и 5-е совершенное число, и все факторы, включая 8191, упомянуты на листе №. 34 a tergo (оборотная сторона стр. 34). Части рукописи были опубликованы в Archiv der Mathematik und Physik, 13 (1895), стр. 388–406 [данные получены 23 сентября 2012 г. ]
- ^ "A i lettori. Nel trattato de 'numeri perfetti, che giàfino dell anno 1588 composi, oltrache se era passato auáti à Trouarne molti auertite molte cose, se era anco ampamente dilatatala Tauola de' numeri composti, di ciascuno de 'quali per ordine li components, onde preposto unnum. " п. 1 в Trattato de 'nvumeri perfetti Di Pietro Antonio Cataldo 1603. http://fermi.imss.fi.it/rd/bdv?/bdviewer@selid=1373775# [ постоянная мертвая ссылка ]
- ^ стр. 13–18 в Trattato de 'nvumeri perfetti Di Pietro Antonio Cataldo 1603. http://fermi.imss.fi.it/rd/bdv?/bdviewer@selid=1373775# [ постоянная мертвая ссылка ]
- ^ стр. 18–22 в Trattato de 'nvumeri perfetti Di Pietro Antonio Cataldo 1603. http://fermi.imss.fi.it/rd/bdv?/bdviewer@selid=1373775# [ постоянная мертвая ссылка ]
- ^ http://bibliothek.bbaw.de/bbaw/bibliothek-digital/digitalequellen/schriften/anzeige/index_html?band=03-nouv/1772&seite:int=36 Архивировано 31 марта 2012 г.в Wayback Machine Nouveaux Mémoires de l 'Académie Royale des Sciences et Belles-Lettres 1772, стр. 35–36 EULER, Leonhard: Extrait d'une lettre à M. Bernoulli, Concerant le Mémoire imprimé parmi ceux de 1771. p. 318 [intitulé: Recherches sur les diviseurs de quelques nombres très grands, включающих в себя сомнительную геометрическую прогрессию 1 + 101 + 102 + 103 + ... + 10T = S]. Проверено 2 октября 2011.
- ^ http://primes.utm.edu/notes/by_year.html#31 Дата и год открытия неизвестны. Возможны даты между 1752 и 1772 годами.
- ^ Крис К. Колдуэлл. «Модульные ограничения на дивизоры Мерсенна» . Primes.utm.edu . Проверено 21 мая 2011 .
- ↑ «En novembre de l'année 1883, dans la correance de Notre Académie se Trouve une communication qui contient l'assertion que le nombre 2 61 - 1 = 2305843009213693951 est un nombre premier». /… / Le tome XLVIII des Mémoires Russes de l'Académie /… / contient le compte-rendu de la séance du 20 декабря 1883 г., dans lequel l'objet de la communication du père Pervouchine est indiqué avec précision ». Бюллетень имперской академии наук Санкт-Петербурга, с. 3, т. 31, 1887 г., кол. 532–533. https://www.biodiversitylibrary.org/item/107789#page/277/mode/1up [получено 17 сентября 2012 г.] См. также Mélanges mathématiques et astronomiques tirés du Bulletin de l'Académie impériale des Sciences de Saint-Peterbourg v. 6 (1881–1888), стр. 553–554. См. Также Mémoires de l'Académie impériale des Sciences de Saint-Pétersbourg: Sciences mathématiques, Physiques et Naturelles, vol. 48
- ^ Пауэрс, RE (1 января 1911 г.). «Десятое идеальное число». Американский математический ежемесячник . 18 (11): 195–197. DOI : 10.2307 / 2972574 . JSTOR 2972574 .
- ^ "М.Э. Фокенберг и работа заместителя Феврие, et j'en ai reçu message le 7 Juin; M. Powers посланник 1 er Juin un cablógramme à M. Bromwich [секретарь Лондонского математического общества] для M 107. Sur ma demande, ces deux auteurs m'ont adressé leurs remarquables résultats, et je m'empresse de les publier dans noscolnes, avec nos felicitations ". п. 103, Андре Жерардин, Nombres de Mersenne, стр. 85, 103–108 в Sphinx-dipe. [Journal mensuel de la curiosité, de concours & de mathématiques.] V. 9, No. 1, 1914.
- ^ "Телеграмма Пауэра, объявляющая тот же результат, была отправлена в Лондонскую математическую организацию. Итак, 1 июня 1914 года" Числа Мерсенна, Scripta Mathematica , v. 3, 1935, стр. 112–119 http://primes.utm.edu/mersenne/LukeMirror/lit/lit_008s.htm [получено 13 октября 2012 г.]
- ^ «Протоколы заседаний». Труды Лондонского математического общества . s2-13 (1): iv – xl. 1914. doi : 10.1112 / plms / s2-13.1.1-s .
- ↑ Prime Pages, M 107 : Fauquembergue или Powers? .
- ^ http://visualiseur.bnf.fr/CadresFenetre?O=NUMM-3039&I=166&M=chemindefer Представлен на встрече с Академией наук (Франция) 10 января 1876 года. Дата обращения 2 октября 2011 г.
- ^ a b «Используя стандартный тест Лукаса для простых чисел Мерсенна, запрограммированный Р. М. Робинсоном, SWAC обнаружил простые числа 2 521 - 1 и 2 607 - 1 30 января 1952 года». Д.Х. Лемер, Недавние открытия больших простых чисел , Математика вычислений, т. 6, № 37 (1952), с. 61, http://www.ams.org/journals/mcom/1952-06-037/S0025-5718-52-99404-0/S0025-5718-52-99404-0.pdf [Дата обращения 18 сентября 2012 г. ]
- ^ «Программа, описанная в примечании 131 (c), произвела 15-е простое число Мерсенна 2 1279 - 1 25 июня. SWAC проверяет это число за 13 минут и 25 секунд». Д.Х. Лемер, Новое простое число Мерсенна , Математика вычислений, т. 6, № 39 (1952), с. 205, http://www.ams.org/journals/mcom/1952-06-039/S0025-5718-52-99387-3/S0025-5718-52-99387-3.pdf [Дата обращения 18сентября2012 г. ]
- ^ a b «Еще два простых числа Мерсенна, 2 2203 - 1 и 2 2281 - 1, были обнаружены SWAC 7 и 9 октября 1952 года». Д.Х. Лемер, Два новых простых числа Мерсенна , Математика вычислений, т. 7, № 41 (1952), с. 72, http://www.ams.org/journals/mcom/1953-07-041/S0025-5718-53-99371-5/S0025-5718-53-99371-5.pdf [Дата обращения 18 сентября 2012 г. ]
- ^ Ризель, Ганс (1 января 1958 г.). «Новый Мерсенн Прайм» . Математика вычислений . 12 (61): 60. DOI : 10.1090 / S0025-5718-58-99282-2 .
- ^ a b А. Гурвиц и Дж. Л. Селфридж, Числа Ферма и совершенные числа , Уведомления Американского математического общества, т. 8, 1961 г., стр. 601, аннотация 587-104.
- ^ a b «Если p простое число, M p = 2 p - 1 называется числом Мерсенна. Простые числа M 4253 и M 4423 были обнаружены путем кодирования теста Люка-Лемера для IBM 7090.» Александр Гурвиц, Новые простые числа Мерсенна , Математика вычислений, т. 16, No. 78 (1962), pp. 249–251, http://www.ams.org/journals/mcom/1962-16-078/S0025-5718-1962-0146162-X/S0025-5718-1962 -0146162-X.pdf [Проверено 18 сентября 2012 г.]
- ^ а б в Гиллис, Дональд Б. (1 января 1964 г.). «Три новых простых числа Мерсенна и статистическая теория» . Математика вычислений . 18 (85): 93–97. DOI : 10.1090 / S0025-5718-1964-0159774-6 . JSTOR 2003409 .
- ^ Такерман, Брайант (1 октября 1971 г.). «24-й прайм Мерсенна» . Труды Национальной академии наук . 68 (10): 2319–2320. Bibcode : 1971PNAS ... 68.2319T . DOI : 10.1073 / pnas.68.10.2319 . PMC 389411 . PMID 16591945 .
- ^ а б Нолл, Курт; Никель, Лаура (октябрь 1980 г.). «25-е и 26-е простые числа Мерсенна» . Математика вычислений . 35 (152): 1387. DOI : 10.1090 / S0025-5718-1980-0583517-4 . JSTOR 2006 405 .
- ↑ Дэвид Словински, «В поисках 27-го числа Мерсенна», Журнал развлекательной математики , т. 11 (4), 1978–79, стр. 258–261, MR 80g # 10013
- ^ "27-е простое число Мерсенна. Оно состоит из 13395 цифр и равно 2 44497 - 1. [...] Его простота была определена 8 апреля 1979 года с помощью теста Лукаса-Лемера. Тест был запрограммирован на компьютере CRAY-1 Дэвид Словински и Гарри Нельсон ». (стр. 15) «Результатом было то, что после применения теста Лукаса-Лемера примерно к тысяче чисел, код определил в воскресенье, 8 апреля, что 2 44497 - 1 на самом деле является 27-м простым числом Мерсенна». (стр. 17), Дэвид Словински, «В поисках 27-го прайма Мерсенна», Cray Channels , vol. 4, вып. 1. (1982), стр. 15–17.
- ^ Колкитт, Вашингтон; Уэлш, Л. (1 мая 1991 г.). «Новое простое число Мерсенна» . Математика вычислений . 56 (194): 867. Bibcode : 1991MaCom..56..867C . DOI : 10.1090 / S0025-5718-1991-1068823-9 . JSTOR 2008415 .
- ^ Петерсон И. (1988). «Подготовка к удачному удару». Новости науки . 133 (6): 85. DOI : 10,2307 / 3972461 . JSTOR 3972461 .
- ^ «Простые числа Мерсенна» . Omes.uni-bielefeld.de. 2011-01-05 . Проверено 21 мая 2011 .
- ^ «Словински, инженер-программист компании Cray Research Inc. в Чиппева-Фоллс, обнаружил число в 11:36 утра понедельника [то есть 19 сентября 1983 г.]» Джим Хиггинс, «Число неуловимых цифр выросло» и «Ученый находит большое номер »в The Milwaukee Sentinel - 24 сентября 1983 г., стр. 1 , стр. 11 [получено 23 октября 2012 г.]
- ^ Петерсон И. (1985). «Прайм-тайм для суперкомпьютеров». Новости науки . 128 (13): 199. DOI : 10,2307 / 3970245 . JSTOR 3970245 .
- ^ «Программа Словински также нашла 28-е число в 1982 году, 29-е в 1983 году и 30-е [известное в то время] в прошедшие выходные, посвященные Дню труда. [ То есть 31 августа - 1 сентября 1985 года]" Рэд Салли "," Суперкомпьютер " '/ Вычислительное устройство Chevron находит большее простое число " Houston Chronicle , Friday 20.09.1985, Раздел 1, Страница 26, 4 Star Edition [извлечено 23.10.2012]
- ↑ Prime Pages, Находка 32- го Мерсенна .
- ^ Крис Колдуэлл, Наибольшие известные простые числа .
- ^ Пресс-релиз Crays
- ^ "Электронная почта Словинскиса" .
- ^ Пресс-релиз Silicon Graphics https://web.archive.org/web/19970606011821/http://www.sgi.com/Headlines/1996/September/prime.html [последнее посещение - 30 сентября 2012 г.]
- ^ Основные страницы, лучший рекордный размер! 2 1257787 - 1 .
- ^ GIMPS Обнаруживает тридцать пятой Мерсенна .
- ^ GIMPS открывает 36-й известный Мерсенн Прайм .
- ^ GIMPS Обнаруживает тридцать седьмой Известный Мерсенна .
- ^ GIMPS находит первое простое число в миллион цифр и претендует на премию EFF в размере 50 000 долларов .
- ^ GIMPS, исследователи открывают крупнейшее многомиллионное простое число с помощью Entropia Distributed Computing Grid .
- ^ GIMPS, проект Мерсенна обнаруживает наибольшее известное простое число во всемирной компьютерной сети добровольцев .
- ^ GIMPS, проект Mersenne.org обнаруживает новое наибольшее известное простое число, 2 24 036 583 - 1 .
- ^ GIMPS, проект Mersenne.org обнаруживает новое наибольшее известное простое число, 2 25 964 951 - 1 .
- ^ GIMPS, проект Mersenne.org обнаруживает новое наибольшее известное простое число, 2 30,402,457 - 1 .
- ^ GIMPS, проект Mersenne.org обнаруживает наибольшее известное простое число, 2 32 582 657 - 1 .
- ^ a b « Титаник Праймз» выиграл гонку за исследовательскую премию в размере 100 000 долларов . Проверено 16 сентября 2008.
- ^ «12 апреля [2009], 47-е известное простое число Мерсенна, 2 42 643 801 - 1, 12 837 064 цифры было найдено Odd Magnar Strindmo из Мелхуса, Норвегия! Это простое число является вторым по величине известным простым числом,« всего лишь »141 125 цифры меньше, чем простое число Мерсенна, найденное в августе прошлого года. ", Домашняя страница списка наибольших известных простых чисел, http://primes.utm.edu/primes/page.php?id=88847 [получено 18сентября2012 г.]
- ^ «GIMPS обнаруживает 48-й прайм Мерсенна, 2 57,885,161 - 1 теперь самый крупный известный прайм» . Отличный поиск Мерсенн Прайм в Интернете . Проверено 19 января 2016 .
- ^ «Список известных простых чисел Мерсенна» . Проверено 29 ноября 2014 .
- ^ «Проект GIMPS обнаружил наибольшее известное простое число: 2 77 232 917 -1» . Мерсенна Research, Inc . 3 января 2018 . Проверено 3 января 2018 .
- ^ «Список известных простых чисел Мерсенна» . Проверено 3 января 2018 .
- ^ Отчет о вехах GIMPS . Дата обращения 17 мая 2019
- ^ Колдуэлл, « Самый большой известный премьер по годам: краткая история » свеб-сайта Prime Pages , Университет Теннесси в Мартине .
- ^ Кляйнджунг, Торстен; Bos, Joppe W .; Ленстра, Арьен К. (2014). «Фабрика факторизации Мерсенна». Достижения в криптологии - ASIACRYPT 2014 . Конспект лекций по информатике. 8874 . С. 358–377. DOI : 10.1007 / 978-3-662-45611-8_19 . ISBN 978-3-662-45607-1.
- ^ Анри Лифшиц и Рено Лифшиц. "PRP Top Records" . Проверено 21 марта 2018 .
- ^ «Статус экспонента для M1277» . Проверено 22 июня 2018 .
- ^ Петкович, Миодраг (2009). Известные загадки великих математиков . Книжный магазин AMS. п. 197. ISBN 978-0-8218-4814-2.
- ^ Алан Чемберлин. "Браузер базы данных малых тел JPL" . Ssd.jpl.nasa.gov . Проверено 21 мая 2011 .
- ^ «OEIS A016131» . Он-лайн энциклопедия целочисленных последовательностей.
- ^ Тайфун Пэй и Джеймс Л. Кокс. «Обзор некоторых классов семантической и синтаксической сложности» .
- ^ «Исследование простых чисел Мерсенна и Ферма» . Архивировано из оригинала на 2012-05-29.
- ^ Солинас, Джером А. (1 января 2011 г.). «Обобщенное прайм Мерсенна». В Тилборге, фургон Хенк Калифорния; Jajodia, Sushil (ред.). Энциклопедия криптографии и безопасности . Springer США. С. 509–510. DOI : 10.1007 / 978-1-4419-5906-5_32 . ISBN 978-1-4419-5905-8.
- ↑ Chris Caldwell: The Prime Glossary: Gaussian Mersenne (часть Prime Pages )
- ^ Зальнежад, Али; Зальнежад, Хоссейн; Шабани, Гасем; Зальнежад, Мехди (март 2015 г.). «Отношения и алгоритм для достижения наибольших простых чисел». arXiv : 1503.07688 [ math.NT ].
- ^ ( x , 1) и ( x , −1) для x = от 2 до 50
- ^ ( x , 1) для x = от 2 до 160
- ^ ( x , −1) для x = 2 до 160
- ^ ( x + 1, x ) для x = от 1 до 160
- ^ ( x + 1, - x ) для x = от 1 до 40
- ^ ( x + 2, x ) для нечетных x = от 1 до 107
- ^ ( x , −1) для x = от 2 до 200
- ^ Записи PRP, поиск (a ^ nb ^ n) / c, то есть ( a , b )
- ^ Записи PRP, поиск (a ^ n + b ^ n) / c, то есть ( a , - b )
- ^ «Обобщенная гипотеза о воссоединении» .
Внешние ссылки
- «Число Мерсенна» , Математическая энциклопедия , EMS Press , 2001 [1994]
- Домашняя страница GIMPS
- Статус GIMPS - на странице статуса представлена различная статистика по прогрессу поиска, обычно обновляемая каждую неделю, включая прогресс в доказательстве порядка наибольших известных простых чисел Мерсенна.
- GIMPS, известные множители чисел Мерсенна
- M q = (8 x ) 2 - (3 qy ) 2 Свойство составных чисел Мерсенна с простой экспонентой (PDF)
- M q = x 2 + d · y 2 математическая диссертация (PS)
- Грайм, Джеймс. «Число 31 и Мерсенна» . Numberphile . Брэди Харан . Архивировано из оригинала на 2013-05-31 . Проверено 6 апреля 2013 .
- Библиография Мерсенна с гиперссылками на оригинальные публикации
- отчет о простых числах Мерсенна - подробное обнаружение (на немецком языке)
- GIMPS вики
- Страница Уилла Эджингтона Мерсенна - содержит множители для малых чисел Мерсенна
- Известные факторы чисел Мерсенна
- Десятичные цифры и английские названия простых чисел Мерсенна
- Основные редкости: 2305843009213693951
- http://www.leyland.vispa.com/numth/factorization/cunningham/2-.txt Архивировано 5 ноября 2014 г. в Wayback Machine
- http://www.leyland.vispa.com/numth/factorization/cunningham/2+.txt Архивировано 2 мая 2013 г. на Wayback Machine
- Последовательность OEIS A250197 (числа n такие, что левая примитивная часть Аурифейля 2 ^ n + 1 является простой) - факторизация чисел Мерсенна M n ( n до 1280)
- Факторизация полностью факторизованных чисел Мерсенна
- Проект Каннингема, факторизация b n ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12
- http://www.leyland.vispa.com/numth/factorization/cunningham/main.htm Архивировано 4 марта 2016 г. в Wayback Machine.
- http://www.leyland.vispa.com/numth/factorization/anbn/main.htm Архивировано 2 февраля 2016 г. в Wayback Machine.
Ссылки MathWorld
- Вайсштейн, Эрик В. «Число Мерсенна» . MathWorld .
- Вайсштейн, Эрик В. "Прайм Мерсенна" . MathWorld .