Простые числа Мерсенна. Совершенные числа - ABCD42.RU

Простые числа Мерсенна. Совершенные числа

Число Мерсенна

Число́ Мерсе́нна — числа вида Mn = 2 n — 1 , где n — натуральное число. Названы в честь французского математика Мерсенна.

Последовательность чисел Мерсенна начинается так:

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, . (последовательность A000225 в OEIS)

Иногда числами Мерсенна называют числа Mp с простыми индексами p . Эта последовательность начинается так:

Содержание

Свойства

  • Если Mn является простым, то число n также простое.
  • Любой делитель числа Mp для простогоp имеет вид 2pk + 1 , где k — целое число (следствие малой теоремы Ферма).
  • Каждое чётное совершенное число имеет вид Mp(Mp + 1) / 2 = 2 p − 1 (2 p − 1) , где число Мерсенна Mp является простым (доказано Эйлером).

Простые чи́сла Мерсенна

Чи́сла Мерсенна получили известность в связи с эффективным критерием простоты Люка — Лемера, благодаря которому простые чи́сла Мерсенна давно удерживают лидерство как самые больши́е известные простые чи́сла. [1] На данный момент самым больши́м известным простым числом является число Мерсенна M43112609 = 2 43112609 − 1 , найденное в августе 2008 года в рамках проекта распределённых вычислений M43112609 составляет 12978189 десятичных цифр, что позволяет GIMPS претендовать на премию в 100000 долларов США, назначенную сообществом Electronic Frontier Foundation за нахождение простого числа длина которого превышает 10 миллионов десятичных цифр. [2]

Всего известно 46 простых числа́ Мерсенна, причём порядковые номера с уверенностью установлены только у первых 39-ти. [3] Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его.

Последовательность простых чисел Мерсенна и их показателей начинается так:

Mp : 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, . (последовательность A000668 в OEIS) p : 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, . (последовательность A000043 в OEIS)

Вариации и обобщения

  • Двойные числа Мерсенна определяются как .

Открытые проблемы

  • Бесконечность количества простых чисел Мерсенна и их асимптотика
  • Простота числа

Примечания

  1. The Largest Known Primes (англ.)
  2. EFF Cooperative Computing Awards (англ.)
  3. Mersenne Primes: History, Theorems and Lists (англ.)

Ссылки

  • GIMPS
  • Weisstein, Eric W.Mersenne Number на сайте Wolfram MathWorld. (англ.)
  • Weisstein, Eric W.Double Mersenne Numbers на сайте Wolfram MathWorld. (англ.)

Wikimedia Foundation . 2010 .

  • Роман (значения)
  • Арт-рок

Смотреть что такое «Число Мерсенна» в других словарях:

Число Вудала — В теории чисел число Вудала (Wn) любое натуральное число вида Wn = n × 2n − 1 для некоторого натурального n. Несколько первых чисел Вудала: 1, 7, 23, 63, 159, 383, 895, … последовательность A003261 в OEIS. Числа Вудала были… … Википедия

Число Прота — В теории чисел число Прота, названное в честь математика Франсуа Прота (англ.), представляет собой число вида , где является нечётным положительным целым числом и n положительное целое число, причём . Без последнего условия все… … Википедия

МЕРСЕННА ЧИСЛО — простое число вида М п= 2 п 1, где n=1, 2, 3, . . М. ч. рассматривались в 17 в. М. Мерсенном (М. Mersenne). Числа М п могут быть простыми только при простых значениях п. При n=2, 3, 5, 7 получаются соответственно простые числа М п=3,7, 31, 127 … Математическая энциклопедия

Числа Мерсенна — числа вида , где натуральное число. Названы в честь французского математика Марена Мерсенна. Последовательность чисел Мерсенна начинается так: 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, … (последовательность A000225 в OEIS) Иногда числами Мерсенна … Википедия

100 (число) — 100 сто 97 · 98 · 99 · 100 · 101 · 102 · 103 70 · 80 · 90 · 100 · 110 · 120 · 130 200 · 100 · 0 · 100 · 200 · 300 · 400 Факторизация: 2×2×5×5 … Википедия

10 (число) — У этого термина существуют и другие значения, см. 10 (значения). 10 десять 7 · 8 · 9 · 10 · 11 · 12 · 13 20 · 10 · 0 · 10 · 20 · 30 · 40 Факторизация: 2×5 Римская запись: X Двоичное … Википедия

3 (число) — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия

0 (число) — 0 Нуль (ноль) 3 · 2 · 1 · 0 · 1 · 2 · 3 Целые числа У этого термина существуют и другие значения, см. Ноль. 0 (ноль, нуль от лат. nullus никакой) целое число, разделяющее на числовой прямой … Википедия

30 (число) — 30 тридцать 27 · 28 · 29 · 30 · 31 · 32 · 33 0 · 10 · 20 · 30 · 40 · 50 · 60 Факторизация: 2×3×5 Римская запись: XXX Двоичное: 1 1110 … Википедия

Ноль (число) — 0 Нуль (ноль) 3 · 2 · 1 · 0 · 1 · 2 · 3 Целые числа Список чисел 0 (ноль, нуль от лат. nullus никакой) число, обозначаемое цифрой ноль. Ноль это нейтральный элемент для операции сложения (то есть при сложении с нулём число не меняется).… … Википедия

Простые Числа Мерсенна, совершенные числа

Простые Числа Мерсенна, совершенные числа

Среди простых чисел особую роль играют простые числа Мерсенна — числа вида 1)М р = 2 р -1 , где р — простое число. Они называются простыми числами Мерсенна по имени французского монаха Мерена Мерсенна (1588-1648), одного из основателей Парижской Академии наук, друга Декарта и Ферма. Так как М 2 =3, М 3 =7, М 5 =31, М 7 =127 , то это — простые числа Мерсенна. Однако, число 2)М 11 =2047=23 . 89 простым не является. До 1750 года было найдено всего 8 простых чисел Мерсенна: М 2 , М 3 , М 5 , М 7 , М 13 , М 17 , М 19 , М 31 . То, что М 31 — простое число, доказал в 1750 году Л. Эйлер. В 1876 году французский математик Эдуард Люка

установил, что число

3)М 127 =170141183460469231731687303715884105727

— простое. В 1883 г. Сельский священник Пермской губернии И.М.Первушин без всяких вычислительных приборов доказал, что число М 61 =2305843009213693951 является простым. Позднее было установлено, что числа М 89 и М 107 — простые. Использование ЭВМ позволило в 1952-1964 годах доказать, что числа М 521 , М 607 , М 1279 , М 2203 , М 2281 , М 3217 , М 4253 , М 4423 , М 2689 , М 9941 , М 11213 — простые. К настоящему времени известно уже более 30 простых чисел Мерсенна, одно из которых М 216091 имеет 65050 цифр. Большой интерес к простым числам Мерсенна вызван их тесной связью с совершенными числами.

Натуральное число Р называется совершенным, если оно равно сумме всех своих делителей кроме Р .

Евклид доказал, что если р и 2 р -1 — простые числа, то число 4)Р р =2 р-1 (2 р -1)=2 р-1 М р является совершенным.

Действительно, делителями такого числа, включая само это число, являются 5)1,2, . ,2 р-1 ,М р ,2М р , . ,2 р-1 М р .

Их сумма S p =(1+2+ . +2 р-1 )(М р +1)=(2 р -1) . 2 р =2 . 2 р-1 М р . Вычитая из S само число Р р , убеждаемся, что сумма всех делителей числа Р р равна этому числу, следовательно Р р — совершенное число.

Числа Р 2 =6 и Р 3 =28 были известны ещё пифагорейцам. Числа Р 5 =496 и Р 7 =8128 нашел Евклид. Используя другие простые числа Мерсенна и формулу 4, находим следующие совершенные числа:

6)Р 13 =33550336, Р 17 =8589869056, Р 19 =137438691328, Р 31 =2305843008139952128.

Для всех остальных чисел Мерсенна числа Р р имеют очень много цифр.

До сих пор остаётся загадкой, как Мерсенн смог высказать правильное утверждение, что числа Р 17, Р 19, Р 31 являются совершенными. Позднее было обнаружено, что почти за сто лет до Мерсенна числа Р 17, Р 19 нашел итальянский математик Катальди — профессор университетов Флоренции и Болоньи. Считалось, что божественное провидение предсказало своим избранникам правильные значения этих совершенных чисел. Если учесть, что ещё пифагорейцы считали первое совершенное число 6 символом души, что второе совершенное число 28 соответствовало числу членов многих учёных обществ, что даже в двенадцатом веке церковь учила: для спасения души достаточно изучать совершенные числа и тому, кто найдёт новое божественное совершенное число, уготовано вечное блаженство, то становится понятным исключительный интерес к этим числам.

Однако и с математической точки зрения чётные совершенные числа по-своему уникальны. Все они — треугольные. Сумма величин, обратных всем дилителям числа, включая само число, всегда равна двум. Остаток от деления совершенного числа, кроме 6, на 9 равен 1. В двоичной системе совершенное число Р р начинается р единицами, потом следуют р-1 нулей. Например:

7)Р 2 = 110, Р 3 = 11100, Р 5 = 111110000, Р 7 =1111111000000 и т.д.

Последняя цифра чётного совершенного числа или 6, или 8, причём, если 8, то ей предшествует 2.

Леонард Эйлер доказал, что все чётные совершенные числа имеют вид 2 р-1 . М р , где М р -простое число Мерсенна. Однако до сих пор не найдено ни одного нечётного совершенного числа. Высказано предположение(Брайен Такхерман,США), что если такое число существует, то оно должно иметь не менее 36 знаков.

Ошибка в тексте? Выдели её мышкой и нажми

Остались рефераты, курсовые, презентации? Поделись с нами — загрузи их здесь!

Проект «Числа Мерсенна»

обучающаяся 5б класса

учитель математики и информатики

с. Платошино, 2017

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

Среди простых чисел особую роль играют простые числа Мерсенна — числа вида Мр = 2р -1 , где р — простое число. Они называются простыми числами Мерсенна по имени французского монаха Мерена Мерсенна, одного из основателей Парижской Академии наук, друга Декарта и Ферма.

Цель: исследовать применение простых чисел Мерсенна в жизни человека.

Дать определение числам Марсенна. Изучить применение чисел Марсенна на практике. Создать памятку по вычислению и применению чисел Марсенна.

Простые числа Мерсенна

В течение нескольких столетий шла погоня за простыми числами. Многие математики боролись за честь стать открывателем самого большого из известных простых чисел. Разумеется, можно было бы выбрать несколько очень больших чисел, не имеющих таких очевидных делителей, как 2, 3, 5, 7, и проверить, являются ли они простыми числами. Этот способ, как мы вскоре убедимся, не очень эффективен. Теперь эта погоня утихла, она идет только в одном направлении, оказавшемся удачным.

Простые числа Мерсенна являются простыми числами специального вида

где р — другое простое число. Эти числа вошли в математику давно, они появляются еще в евклидовых размышлениях о совершенных числах, которые мы рассмотрим позже. Свое название они получили в честь французского монаха Мерена Мерсенна (1588–1648), который много занимался проблемой совершенных чисел.

Читайте также  Размеры звезд. Плотность их вещества.

Если начать вычислять числа (2.2.1) для различных простых чисел р, то видно, что не все они оказываются простыми. Например,

М2 = 22 — 1 = 3 = простое,

М3 = 23 — 1 = 7 = простое,

М5 = 25 — 1 = 31 = простое,

М7 = 27 — 1 = 127 = простое,

М11 = 211 — 1 = 2047 = 23 89.

Общий способ нахождения больших простых чисел Мерсенна состоит в проверке всех чисел Мp для различных простых чисел р.

Эти числа очень быстро увеличиваются и столь же быстро увеличиваются затраты труда на их нахождение. То, что с этой работой все-таки можно справиться уже для довольно больших чисел, объясняется существованием эффективных способов выяснения простоты для чисел такого вида.

В исследовании чисел Мерсенна можно выделить раннюю стадию, достигшую своей кульминации в 1750 году, когда Леонард Эйлер[5] установил, что число М31 является простым. К этому времени было найдено восемь простых чисел Мерсенна, соответствующих значениям

р = 2, р = 3, р = 5, р = 7, р = 13, р = 17, p = 19, р = 31.

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

Генератор псевдослучайных чисел (ГПСЧ, англ. pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте — Карло и имитационного моделирования до криптографии.

Вихрь Мерсемнна (англ. Mersenne twister, MT) — генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 году японскими учёными Макото Мацумото (яп. 松本 眞) и Такудзи Нисимура (яп. 西村 拓士). Вихрь Мерсенна основывается на свойствах простых чисел Мерсенна (отсюда название) и обеспечивает быструю генерацию высококачественных по критерию случайности псевдослучайных чисел.

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

Простые числа являются не только объектом пристального рассмотрения со стороны математиков всего мира, но уже давно и успешно используются в составлении различных рядов чисел, что является основой, в том числе, для шифрографии. При этом следует признать, что огромное количество загадок, связанных с этими замечательными элементами, все еще ждут своих разгадок, многие вопросы имеют не только философское, но и практичное значение.

Вообще, поиск новых простых чисел, а особенно чисел Мерсенна, можно сравнить с коллекционированием редких вещей.

Продукт проекта – памятка по вычислению и применению чисел Марсенна.

https://math. wikireading. ru/673

https://ru. wikipedia. org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9C%D0%B5%D1%80%D1%81%D0%B5%D0%BD%D0%BD%D0%B0

https://dic. academic. ru/dic. nsf/ruwiki/7155

Памятка по вычислению и применению чисел Марсенна.

Числа Мерсенна — числа вида Мр = 2р -1 , где р — простое число. Они называются простыми числами Мерсенна по имени французского монаха Мерена Мерсенна, одного из основателей Парижской Академии наук, друга Декарта и Ферма.

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

Генератор псевдослучайных чисел (ГПСЧ, англ. pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте — Карло и имитационного моделирования до криптографии.

Вихрь Мерсемнна (англ. Mersenne twister, MT) — генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 году японскими учёными Макото Мацумото (яп. 松本 眞) и Такудзи Нисимура (яп. 西村 拓士).

Совершенные числа

Собственный делитель натурального числа — это любой делитель, кроме самого этого числа. Если число равно сумме своих собственных делителей, то оно называется совершенным. Так, 6 = 3 + 2 + 1 — это наименьшее из всех совершенных чисел (1 не в счет), 28 = 14 + 7 + 4 + 2 + 1 — это еще одно такое число.

Совершенные числа были известны еще в древности и интересовали ученых во все времена. В «Началах» Евклида доказано, что если простое число имеет вид 2 n – 1 (такие числа называют простыми числами Мерсенна), то число 2 n–1 (2 n – 1) — совершенное. А в XVIII веке Леонард Эйлер доказал, что любое четное совершенное число имеет такой вид.

Задача

Попробуйте доказать эти факты и найти еще пару-тройку совершенных чисел.

Подсказка 1

а) Чтобы доказать утверждение из «Начал» (что если простое число имеет вид 2 n – 1, то число 2 n –1 (2 n – 1) — совершенное), удобно рассмотреть сигма-функцию, которая равна сумме всех положительных делителей натурального числа n. Например, σ(3) = 1 + 3 = 4, а σ(4) = 1 + 2 + 4 = 7. Эта функция обладает полезным свойством: она мультипликативна, то есть σ(ab) = σ(a)σ(b); равенство выполняется для любых двух взаимно простых натуральных чисел a и b (взаимно простыми называются числа, у которых нет общих делителей). Это свойство можно попытаться доказать или принять на веру.

При помощи сигма-функции доказательство совершенности числа N = 2 n –1 (2 n – 1) сводится к проверке того, что σ(N) = 2N. Для этого пригодится мультипликативность этой функции.

б) Другой путь решения не использует никаких дополнительных конструкций вроде сигма-функции. Он опирается только на определение совершенного числа: нужно выписать все делители числа 2 n–1 (2 n – 1) и найти их сумму. Должно получиться это же число.

Подсказка 2

Доказывать, что любое четное совершенное число — это степень двойки, умноженная на простое число Мерсенна, также удобно с помощью сигма-функции. Пусть N — какое-нибудь четное совершенное число. Тогда σ(N) = 2N. Представим N в виде N = 2 k ·m, где m — нечетное число. Поэтому σ(N) = σ(2 k ·m) = σ(2 k )σ(m) = (1 + 2 + . + 2 k )σ(m) = (2 k +1 – 1)σ(m).

Получается, что 2·2 k ·m = (2 k +1 – 1)σ(m). Значит, 2 k +1 – 1 делит произведение 2 k +1 ·m, а поскольку 2 k +1 – 1 и 2 k +1 взаимно просты, то m должно делиться на 2 k +1 – 1. То есть m можно записать в виде m = (2 k +1 – 1)·M. Подставив это выражение в предыдущее равенство и сократив на 2 k +1 – 1, получим 2 k +1 ·M = σ(m). Теперь до окончания доказательства остается всего один, хотя и не самый очевидный, шаг.

Решение

В подсказках содержится значительная часть доказательств обоих фактов. Восполним здесь недостающие шаги.

1. Теорема Евклида.

а) Для начала нужно доказать, что сигма-функция действительно мультипликативна. На самом деле, поскольку каждое натуральное число однозначно раскладывается на простые множители (это утверждение называют основной теоремой арифметики), достаточно доказать, что σ(pq) = σ(p)σ(q), где p и q — различные простые числа. Но довольно очевидно, что в этом случае σ(p) = 1 + p, σ(q) = 1 + q, а σ(pq) = 1 + p + q + pq = (1 + p)(1 + q).

Теперь завершим доказательство первого факта: если простое число имеет вид 2 n – 1, то число N = 2 n –1 (2 n – 1) — совершенное. Для этого достаточно проверить, что σ(N) = 2N (так как сигма-функция — это сумма всех делителей числа, то есть сумма собственных делителей плюс само число). Проверяем: σ(N) = σ(2 n –1 (2 n – 1)) = σ(2 n –1 )σ(2 n – 1) = (1 + 2 + . + 2 n –1 )·((2 n – 1) + 1) = (2 n – 1)·2 n = 2N. Здесь было использовано, что раз 2 n – 1 — простое число, то σ(2 n – 1) = (2 n – 1) + 1 = 2 n .

б) Доведем до конца и второе решение. Найдем все собственные делители числа 2 n –1 (2 n – 1). Это 1; степени двойки 2, 2 2 , . 2 n –1 ; простое число p = 2 n – 1; а также делители вида 2 m ·p, где 1 ≤ mn – 2. Суммирование всех делителей тем самым разбивается на подсчет сумм двух геометрических прогрессий. Первая начинается с 1, а вторая — с числа p; у обеих знаменатель равен 2. По формуле суммы элементов геометрической прогрессии сумма всех элементов первой прогрессии равна 1 + 2 + . + 2 n –1 = (2 n – 1)/2 – 1 = 2 n – 1 (и это равно p). Вторая прогрессия дает p·(2 n –1 – 1)/(2 – 1) = p·(2 n –1 – 1). Итого, получается p + p·(2 n –1 – 1) = 2 n –1 ·p — то, что надо.

Скорее всего, Евклид не был знаком с сигма-функцией (да и вообще с понятием функции), поэтому его доказательство изложено несколько другим языком и ближе к решению из пункта б). Оно содержится в предложении 36 из IX книги «Начал» и доступно, например, здесь.

2. Теорема Эйлера.

Прежде чем доказывать теорему Эйлера, отметим еще, что если 2 n – 1 — простое число Мерсенна, то n также должно быть простым числом. Дело в том, что если n = km — составное, то 2 km – 1 = (2 k ) m – 1 делится на 2 k – 1 (поскольку выражение x m – 1 делится на x – 1, это одна из формул сокращенного умножения). А это противоречит простоте числа 2 n – 1. Обратное утверждение — «если n — простое, то 2 n – 1 также простое» — не верно: 2 11 – 1 = 23·89.

Вернемся к теореме Эйлера. Наша цель — доказать, что любое четное совершенное число имеет вид, полученный еще Евклидом. В подсказке 2 были намечены первые этапы доказательства, и осталось сделать решающий шаг. Из равенства 2 k +1 ·M = σ(m) следует, что m делится на M. Но m делится также и на само себя. При этом M + m = M + (2 k +1 – 1)·M = 2 k +1 ·M = σ(m). Это означает, что у числа m нет других делителей, кроме M и m. Значит, M = 1, а m — простое число, которое имеет вид 2 k +1 – 1. Тогда N = 2 k ·m = 2 k (2 k +1 – 1), что и требовалось.

Итак, формулы доказаны. Применим их, чтобы найти какие-нибудь совершенные числа. При n = 2 формула дает 6, а при n = 3 получается 28; это первые два совершенных числа. По свойству простых чисел Мерсенна, нам нужно подобрать такое простое n, что 2 n – 1 будет также простым числом, а составные n можно вообще не рассматривать. При n = 5 получится 2 n – 1 = 32 – 1 = 31, это нам подходит. Вот и третье совершенное число — 16·31 = 496. На всякий случай проверим его совершенность явно. Выпишем все собственные делители 496: 1, 2, 4, 8, 16, 31, 62, 124, 248. Их сумма равна 496, так что всё в порядке. Следующее совершенное число получается при n = 7, это 8128. Соответствующее простое число Мерсенна равно 2 7 – 1 = 127, и довольно легко проверить, что оно действительно простое. А вот пятое совершенное число получается при n = 13 и равно 33 550 336. Но проверять его вручную уже очень утомительно (однако это не помешало кому-то открыть его еще в XV веке!).

Послесловие

Первые два совершенных числа — 6 и 28 — были известны с незапамятных времен. Евклид (и мы вслед за ним), применив доказанную нами формулу из «Начал», нашел третье и четвертое совершенные числа — 496 и 8128. То есть сначала было известно всего два, а потом четыре числа с красивым свойством «быть равными сумме своих делителей». Больше таких чисел обнаружить не могли, да и эти, на первый взгляд, ничего не объединяло. В эпоху древности люди были склонны вкладывать мистический смысл в таинственные и непонятные явления, поэтому и совершенные числа получили особый статус. Пифагорейцы, оказавшие сильное влияние на развитие науки и культуры того времени, также поспособствовали этому. «Всё есть число», — говорили они; число 6 в их учении обладало особыми магическими свойствами. А ранние толкователи Библии объясняли, что мир был сотворен именно на шестой день, потому что число 6 — самое совершенное среди чисел, ибо оно первое среди них. Также многим казалось неслучайным, что Луна делает оборот вокруг Земли примерно за 28 дней.

Читайте также  Новаторство драматургии А.П.Чехова

Пятое совершенное число — 33 550 336 — было найдено только в XV веке. Еще почти через полтора века итальянец Катальди нашел шестое и седьмое совершенные числа: 8 589 869 056 и 137 438 691 328. Им соответствуют n = 17 и n = 19 в формуле Евклида. Обратите внимание, что счет идет уже на миллиарды, и страшно даже представить, что все вычисления были проделаны без калькуляторов и компьютеров!

Как мы знаем, Леонард Эйлер доказал, что любое четное совершенное число должно иметь вид 2 n –1 (2 n – 1), причем 2 n – 1 должно быть простым. Восьмое число — 2 305 843 008 139 952 128 — нашел тоже Эйлер в 1772 году. Здесь n = 31. После его достижений можно было осторожно сказать, что про четные совершенные числа науке стало что-то понятно. Да, они быстро растут, и их трудно вычислять, но хотя бы ясно, как это делать: надо брать числа Мерсенна 2 n – 1 и искать среди них простые. Про нечетные совершенные числа неизвестно почти ничего. На сегодняшний день не найдено ни одного такого числа, при том что проверены все числа до 10 300 (видимо, нижняя граница отодвинута даже дальше, просто соответствующие результаты еще не опубликованы). Для сравнения: число атомов в видимой части Вселенной оценивается величиной порядка 10 80 . При этом не доказано, что нечетных совершенных чисел не существует, просто это может быть очень большое число. Даже настолько большое, что наши вычислительные мощности никогда до него не доберутся. Существует ли такое число или нет — одна из открытых на сегодня проблем математики. Компьютерным поиском нечетных совершенных чисел занимаются участники проекта OddPerfect.org.

Вернемся к четным совершенным числам. Девятое число было найдено в 1883 году сельским священником из Пермcкой губернии И. М. Первушиным. В этом числе 37 цифр. Таким образом, к началу XX века было найдено всего 9 совершенных чисел. В это время появились механические арифметические машины, а в середине века — и первые компьютеры. С их помощью дело пошло быстрее. Сейчас найдено 47 совершенных чисел. Причем только у первых сорока известны порядковые номера. Еще про семь чисел пока точно не установлено, какие они по счету. В основном поиском новых мерсенновских простых (а с ними — и новых совершенных чисел) занимаются участники проекта GIMPS (mersenne.org).

В 2008 году участниками проекта было найдено первое простое число, в котором больше 10 000 000 = 10 7 цифр. За это они получили приз $100 000. Денежные призы 150 000 и 250 000 долларов также обещаны за простые числа, состоящие из больше чем 10 8 и 10 9 цифр соответственно. Предполагается, что из этих денег получат вознаграждение и те, кто нашел меньшие, но еще не открытые простые числа Мерсенна. Правда, на современных компьютерах проверка чисел такой длины на простоту займет годы, и это, наверное, дело будущего. Самое большое простое число на сегодня равно 2 43112609 – 1. Оно состоит из 12 978 189 цифр. Отметим, что благодаря тесту Люка—Лемера (см. его доказательство: A proof of the Lucas–Lehmer Test) сильно упрощается проверка на простоту чисел Мерсенна: не нужно пытаться найти хотя бы один делитель очередного кандидата (это очень трудоемкая работа, которая для таких больших чисел практически невыполнима сейчас).

У совершенных чисел есть забавные арифметические свойства:

  • Каждое четное совершенное число является также треугольным числом, то есть представимо в виде 1 + 2 + . + k = k(k + 1)/2 для некоторого k.
  • Каждое четное совершенное число, кроме 6, является суммой кубов последовательных нечетных натуральных чисел. Например, 28 = 1 3 + 3 3 , а 496 = 1 3 + 3 3 + 5 3 + 7 3 .
  • В двоичной системе счисления совершенное число 2 n –1 (2 n – 1) записывается очень просто: сначала идут n единиц, а потом — n – 1 нулей (это следует из формулы Евклида). Например, 610 = 1102, 2810 = 111002, 3355033610 = 11111111111110000000000002.
  • Сумма чисел, обратных всем делителям совершенного числа (само число здесь тоже участвует), равна 2. Например, 1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 2.

Простые числа Мерсенна. Совершенные числа

Историческая справка

Числами Мерсенна принято называть ряд 2 p -1, где p — натуральное число. При этом простые числа в этом ряду получаются только при некоторых простых значениях p. Благодаря открытию быстрого теста простоты Люка-Лемера (LL — Lucas-Lehmer Primality Testing) именно простые числа Мерсенна являются рекордсменами по размеру среди всех прочих видов простых чисел.

Electronic Frontier Foundation (EFF) учредила денежные призы за нахождение простых чисел-рекордсменов: награды за 1,000,000-значное и 10,000,000-значное уже были выплачены, а за 100,000,000-значное и 1,000,000,000-значное еще ждут своего часа!

К концу XX века стало понятно, что индивидуальный поиск зашел в тупик — слишком высока стала размерность чисел, слишком велики расстояния между соседними достижениями. Тогда-то, в 1995 году, программисту Джорджу Уолтману (George Woltman) и пришла мысль создать проект распределенных вычислений GIMPS (Great Internet Mersenne Prime Search). Теперь каждый участник (к концу первого года их насчитывалось уже более 1,000 человек) мог быть уверен, что проверяет никем еще не изученный диапазон значений, а следовательно плоды его усилий суммируются к прогрессу всего проекта без коллизий с другими искателями.

Результат не заставил себя ждать — все последующие рекорды были установлены именно в рамках GIMPS. Призовой фонд, полученный от EFF, был несколько перераспределен: теперь каждый открыватель нового простого числа Мерсенна получает приз $3,000. Но тот участник, кому посчастливится найти первое стомиллионзнаковое или миллиардзнаковое простое число (а скорее всего это будет именно число Мерсенна), получит несравненно больше!

Работа ведется одновременно по нескольким направлениям: поиск малых делителей, чтобы небольшими затратами прорежать список чисел-претендентов; поиск более крупных делителей с помощью различных алгоритмов разложения; проверка кандидатов с помощью теста простоты LL, и повторная перепроверка ради уверенности, что ни один из претендентов не оказался пропущен или протестирован с ошибкой.

TF (Trial Factoring) — разложение на множители числа-претендента путем простого перебора делителей вида 2pk +1

LL (Lucas-Lehmer) — первичная проверка на простоту числа-претендента

LL-D (Lucas-Lehmer Double-check) — перепроверка на простоту числа-претендента, уже проверенного ранее LL-тестом

PRP (PRobable Prime test) — первичная проверка на вероятную простоту числа-претендента + генерация сертификата теста (CERT)

PRP-DC (PRobable Prime test Double-Check) — перепроверка на вероятную простоту числа-претендента, уже проверенного ранее LL-тестом

CERT (Certificate test) — очень быстрая перепроверка на вероятную простоту числа-претендента, уже проверенного ранее PRP-тестом

PRP-CF (PRobable Prime test for CoFactor) — первичная проверка на вероятную простоту кофактора (числа-претендента, деленного на все его известные делители)

PRP-CF-DC (PRobable Prime test for CoFactor Double-Check) — перепроверка на вероятную простоту кофактора (числа-претендента, деленного на все его известные делители)

P-1 (P-1 Factoring) — разложение на множители P-алгоритмом Полларда

ECM (Elliptic Curve Method) — разложение на множители методом эллиптических кривых

ECMF (ECM on Fermat numbers) — разложение на множители чисел Ферма методом ECM

Ознакомиться подробнее с описаниями данных расчетов можно на сайте GIMPS:
http://mersenne.org/various/math.php

Таблица рекордов

Как водится во многих проектах, здесь также не обошлось без знаменательных достижений отдельных личностей. легендой последнего десятилетия является Кертис Купер (Curtis Cooper) — профессор Университета Центрального Миссури (UCM — The University of Central Missouri). Его парк компьютерной техники, задействованной насчитывает более 19,000 ПК! Неудивительно, что он четырежды (!) становился номинантом награды.

В 2018 году к проекту присоединился участник — британский миллиардер Ben Delo, владелец биржи криптовалют BitMEX. Мощность GIMPS фактические удвоилась, и скорость первичной проверки экспонент обогнала все прогнозы! В связи с этим ждем новых результатов!

Но поиск очередного простого числа — не единственная задача проекта. На другом его полюсе ведутся активные поиски делителей чисел Мерсенна, которые существенно сокращают список претендентов на полноценное тестирование LL. Здесь особо отличается японец Тадаси Таура (Tadashi Taura) — имя в проекте TJAOI. Он знаменит тем, что много лет собирает у себя дома различную вычислительную технику, и живет, по сути, внутри мэйнфрейма! За четверть века он нашел более полутора десятков делителей чисел Ферма и несколько миллионов (!) делителей чисел Мерсенна! Денежных выплат за делители в проектах не предусмотрено, поиск ведется исключительно на чистом энтузиазме!

Статус проекта на 2021.01.05

Проект охватывает диапазон экспонент до 999,999,999 (50,847,533 кандидата).
Тем не менее, статистика обнаруженных делителей ведется до 4,294,967,295 (203,280,220 кандидатов).

Проверены хотя бы однократно все экспоненты до 100.624.061.

Дважды перепроверены все экспоненты до 54.114.703.

До подтверждения номера 48-го простого числа Мерсенна осталось 31,375 тестов.

До подтверждения номера 49-го простого числа Мерсенна осталось 333,858 тестов.

До подтверждения номера 50-го простого числа Мерсенна осталось 389,676 тестов.

До подтверждения номера 51-го простого числа Мерсенна осталось 488,403 тестов.

Узнать текущее положение дел можно на этой странице:
http://mersenne.org/report_milestones/

С чего начать новичку?

Самая большая проблема данного проекта — редкие успехи. Практически в любой из существующих команд постоянные участники составляют скромный процент, в то время как большинство остальных забросили его. Видимо, проект многим наскучил: кому через день, кому через неделю, кому через месяцы или даже годы. Достичь фундаментального успеха довольно сложно: за 25 лет существования проекта было найдено всего 17 новых простых чисел Мерсенна. Можно надеяться на Случай, ведь может быть следующему повезет именно вам!

Но в проекте также предусмотрены и более мелкие результаты — поиск делителей, отсев заведомо неподходящих составных кандидатов. Каждый обнаруженный делитель будет подписан вашим именем. К тому же он сэкономит проекту несколько месяцев ненужного более теста простоты! К настоящему моменту найдено уже более 43 миллионов делителей. Непроверенными остаются еще чуть меньше 21 миллиона экспонент — так что на наш век хватит!

Поэтому рискну дать совет: опробуйте сперва свои силы на небольших заданиях. Вы получите первые баллы GHz-Days, увидите, как начнет расти ваш рейтинг, а если повезет — то и получите свой именной делитель! Наибольшая вероятность успеха наблюдается в режиме Trial factoring to low limits — примерно 1 успех на 75 заданий свой 1-й делитель в 2015 году я нашел лишь через 19 дней работы CPU, а потом стал находить их по 5-20 шт. в день на GPU, сейчас, конечно, значительно реже).

Настройте несколько на поиск новых делителей на быстрых TF, ECM или P-1. Помните: на многоядерных процессорах можно настроить несколько параллельно работающих Worker-ов, что может дать прирост производительности по TF до 3,5 раз!

Читайте также  Электрический ток. Источники электрического тока.

Если спустя какое-то время вы почувствуете, что готовы остаться здесь надолго, можно взять задания и посерьезнее: Загрузите долгим тестом простоты, а все остальные пустите на его поддержку/ускорение. Как именно это настраивается, читайте в Инструкции на Форуме >>>

World record sized numbers to test — LL-тест экспоненты, большей чем текущий рекорд

First time tests — от недели до пары месяцев

Double-check tests — от нескольких дней до пары месяцев

PRP — примерно аналогичен LL-тесту

PRP-DC — примерно аналогичен LL-D-тесту

CERT — около 1 часа

PRP-CF — от нескольких часов

PRP-CF-DC — от нескольких часов

Trial factoring — от нескольких минут (желательно выполнять только на GPU)

P-1 factoring — около 14 часов

Trial factoring to low limits — от нескольких минут (желательно выполнять только на GPU)

ECM on small Mersenne numbers — около 1 часа

ECM on Fermat numbers — от нескольких часов (нужно много памяти)

100,000,000 digit numbers to test — от нескольких месяцев до года и более

Посмотреть, как часто вообще везет участникам проекта, можно на этой странице:
http://mersenne.org/report_recent_results/

Вы хотите присоединиться к нам?

Так получилось, что сейчас в Команде России всего несколько десятков активных участников, компьютеры которых регулярно выполняют какие-либо расчеты для проекта GIMPS. Это довольно мало. Будем очень рады, если Вы присоединитесь и поможете увеличивать рейтинг нашей Родины!

Шаг 1: Зарегистрируйтесь в проекте ⇒ Mersenne.org

Шаг 2: Присоединитесь к нашей Команде ⇒ GIMPS.Russia

Шаг 3: Скачайте ПО и получите первые задания ⇒ ПО «Prime95»

Шаг 4: Наблюдайте за нашими последними достижениями ⇒ Team Results

Шаг 5: Пишите, если нужна помощь или появятся новые идеи ⇒ Team Contacts

§ 2. Простые числа Мерсенна

§ 2. Простые числа Мерсенна

В течение нескольких столетий шла погоня за простыми числами. Многие математики боролись за честь стать открывателем самого большого из известных простых чисел. Разумеется, можно было бы выбрать несколько очень больших чисел, не имеющих таких очевидных делителей, как 2, 3, 5, 7, и проверить, являются ли они простыми числами. Этот способ, как мы вскоре убедимся, не очень эффективен. Теперь эта погоня утихла, она идет только в одном направлении, оказавшемся удачным.

Простые числа Мерсенна являются простыми числами специального вида

где р — другое простое число. Эти числа вошли в математику давно, они появляются еще в евклидовых размышлениях о совершенных числах, которые мы рассмотрим позже. Свое название они получили в честь французского монаха Мерена Мерсенна (1588–1648), который много занимался проблемой совершенных чисел.

Если начать вычислять числа (2.2.1) для различных простых чисел р, то видно, что не все они оказываются простыми. Например,

М 2 = 2 2 — 1 = 3 = простое,

М 3 = 2 3 — 1 = 7 = простое,

М 5 = 2 5 — 1 = 31 = простое,

М 7 = 2 7 — 1 = 127 = простое,

М 11 = 2 11 — 1 = 2047 = 23 89.

Общий способ нахождения больших простых чисел Мерсенна состоит в проверке всех чисел М p для различных простых чисел р.

Эти числа очень быстро увеличиваются и столь же быстро увеличиваются затраты труда на их нахождение. То, что с этой работой все-таки можно справиться уже для довольно больших чисел, объясняется существованием эффективных способов выяснения простоты для чисел такого вида.

В исследовании чисел Мерсенна можно выделить раннюю стадию, достигшую своей кульминации в 1750 году, когда Леонард Эйлер[5] установил, что число М 31 является простым. К этому времени было найдено восемь простых чисел Мерсенна, соответствующих значениям

Эйлерово число M 31 оставалось самым большим из известных простых чисел более ста лет. В 1876 году французский математик Лукас установил, что огромное число

М 127 = 170141183460469231731687303715884105727

является простым числом. Ну и число! С 39 цифрами. Простые числа Мерсенна, меньшие этого числа, задаются значениями р, указанными выше, а также значениями

Эти 12 простых чисел Мерсенна были вычислены с помощью только карандаша и бумаги, а для вычисления следующих уже использовались механические настольные счетные машины. Появление вычислительных машин с электрическим приводом позволило продолжить поиски, доведя их до р = 257. Однако результаты были неутешительными, среди них не оказалось новых простых чисел Мерсенна.

Затем задача была переложена на плечи ЭВМ. Создание все более высокопроизводительных ЭВМ дало возможность продолжить поиск новых простых чисел Мерсенна. Д. X. Лемер установил, что значения

дают простые числа Мерсенна. Дальнейшие поиски также увенчались успехом. Ризель (1958) показал, что

дает простое число Мерсенна, а Гурвиц (1962) нашёл еще два таких значения:

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

Итак, общий урожай составил 23 простых числа Мерсенна, и, так как мощности ЭВМ продолжают увеличиваться, мы надеемся на дальнейший успех. Простое число Лукаса М 127, как мы уже упоминали, имеет 39 цифр. Даже вычисление самого большого из известных простых чисел, числа M 11213, является довольно сложной задачей и, по-видимому, нет смысла воспроизводить здесь это число. Если же мы захотим узнать, сколько цифр содержит это число, то мы можем сделать это, не вычисляя самого числа.

Вместо нахождения количества цифр числа М р = 2 p — 1 рассмотрим эту задачу для числа М р + 1 = 2 р .

Эти два числа имеют одинаковое количество цифр, так как если бы число М р + 1 имело на одну цифру больше, то оно должно было бы оканчиваться на 0. Но это невозможно ни для какой степени числа 2, что видно из ряда

2, 4, 8, 16, 32, 64, 128, 266….

в котором последняя цифра в каждом числе может быть только одним из чисел

Чтобы найти количество цифр числа 2 p , вспомним, что Ig 2 p = p lg 2. Из таблиц находим, что Ig 2 приближенно равняется 0,30103, откуда

lg 2 p = p lg 2 = р • 0,30103.

Для р = 11213 получаем

lg 2 11213 = 3375,449…,

и так как характеристика этого числа равна 3375, то мы приходим к выводу, что число 2 p имеет 3376 цифр.

Итак, мы можем сказать следующее.

Самое большое известное в настоящее время простое число имеет 3376 цифр. (Здесь слова «в настоящее время» имеют существенное значение.) Это число было найдено на ЭВМ Иллинойского университета (США). Математический факультет этого университета был так горд своим достижением, что изобразил это число на своем почтовом штемпеле, таким образом воспроизводя его на каждом отсылаемом письме, для всеобщего восхищения.

Читайте также

Глава 2 Простые числа: ускользающие правила

Глава 2 Простые числа: ускользающие правила Как мы уже говорили, простые числа представляют из себя одну из важных тем, которые возвращают нас к самым истокам математики, а затем по пути возрастающей сложности приводят на передний край современной науки. Таким образом,

Глава 4 Логарифмы и простые числа

Глава 4 Логарифмы и простые числа Когда мы исследуем объект, приборы, которые мы используем, тоже влияют на результаты наблюдений. Например, развитие астрономии было тесно связано с совершенствованием телескопов, а микробиология — с микроскопами. Оборудование для

Глава 7 Для чего нужны простые числа

Глава 7 Для чего нужны простые числа Поиск простых чисел — по крайней мере больших простых чисел — довольно сложная задача, потому что еще никому не удалось найти формулу или алгоритм, позволяющий генерировать любые простые числа. Но может возникнуть логичный вопрос:

ГЛАВА 2 ПРОСТЫЕ ЧИСЛА

ГЛАВА 2 ПРОСТЫЕ ЧИСЛА § 1. Простые и составные числа Должно быть, одним из первых свойств чисел, открытых человеком, было то, что некоторые из них могут быть разложены на два или более множителя, например,6 = 2 • 3, 9 = 3 • 3, 30 = 2 • 15 = 3 • 10,в то время как другие, например,3, 7, 13, 37,не

§ 1. Простые и составные числа

§ 1. Простые и составные числа Должно быть, одним из первых свойств чисел, открытых человеком, было то, что некоторые из них могут быть разложены на два или более множителя, например,6 = 2 • 3, 9 = 3 • 3, 30 = 2 • 15 = 3 • 10,в то время как другие, например,3, 7, 13, 37,не могут быть разложены

§ 3. Простые числа Ферма

§ 3. Простые числа Ферма Существует также еще один тип простых чисел с большой и интересной историей. Они были впервые введены французским юристом Пьером Ферма (1601–1665), который прославился своими выдающимися математическими работами. Первыми пятью простыми числами

§ 4. Совершенные числа

§ 4. Совершенные числа Нумерология (или гематрия, как ее иногда еще называют) была распространенным увлечением у древних греков. Естественным объяснением этому является то, что числа в Древней Греции изображались буквами греческого алфавита, и поэтому каждому

§ 5. Дружественные числа

§ 5. Дружественные числа Дружественные числа также входят в наследство, доставшееся нам от греческой нумерологии. Если у двух людей имена были таковы, что их числовые значения удовлетворяли следующему условию: сумма частей (делителей) одного из них равнялась второму

§ 2. Взаимно простые числа

§ 2. Взаимно простые числа Число 1 является общим делителем для любой пары чисел а и b. Может случиться, что единица будет единственным их общим делителем, т. е.d0 = D(a, b) = 1. (4.2.1)В этом случае мы говорим, что числа а и b взаимно простые.Пример. (39, 22) = 1.Если числа имеют общий

§ 1. Числа

§ 1. Числа «Все есть число» — учили древние пифагорейцы[8]. Однако количество чисел, которыми они пользовались, ничтожно по сравнению с фантастической пляской цифр, окружающих нас сегодня в повседневной жизни. Огромные числа появляются, когда считаем мы, и тогда, когда

ЧИСЛА, ЧИСЛА, ЧИСЛА…

ЧИСЛА, ЧИСЛА, ЧИСЛА… — Есть такая книга, — начал Мате, — «Диалоги о математике». Написал ее выдающийся венгерский математик нашего века Альфред Реньи. Форма диалога выбрана им не случайно, как не случайно, вероятно, обратился к ней когда-то Галилео Галилей.Жанр диалога

Глава 0 Быстрые трюки: простые (и впечатляющие) вычисления

Глава 0 Быстрые трюки: простые (и впечатляющие) вычисления Далее вы узнаете, как быстро выполнять математические действия в уме. После непродолжительной практики и освоения методов этой книги ваша способность работать с числами значительно улучшится. После более

44. Какие числа?

44. Какие числа? Какие два целых числа, если их перемножить, составят семь?Не забудьте, что оба числа должны быть целые, поэтому такие ответы, как З1/2 ? 2 или 21/3 ? 3, не

47. Три числа

47. Три числа Какие три целых числа, если их перемножить, дают столько же, сколько получается от их

44. Какие числа?

44. Какие числа? Ответ прост: 1 и 7. Других таких чисел

47. Три числа

47. Три числа 1, 2 и 3 дают при перемножении и при сложении одно и то же:1 + 2 + 3 = 6;1 ? 2 ? 3 =

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: