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

Творческая работа ученика 8 класса по теме

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

Министерство образования и науки, молодежи и спорта Автономной Республики Крым

Гпавное управление образования и науки Сакской райгосадминистрации

Сакское территориальное отделение МАН Украины

Секция математики

Сакский районный филиал

ЧИСЛА МЕРСЕННА

Работу выполнил

Айсинов Иван, учащийся 8 класса, кдч

(Сакский район, Митяевская ОШ)

Научный руководитель

Будякова Л.В. учитель математики

Митяевской ОШ

с. Митяево-2012г.

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

Правда, был один человек- французский монах Марен Мерсенн, живший в 1588-1648 годах, который получал таких писем больше других. Написать об открытии новой теоремы Мерсенну означало установить свой приоритет, поскольку Мерсенн, как правило сообщал об этом остальным своим корреспондентам, в числе которых были Р. Декарт, Б. Паскаль, П. Ферма, Х.

Гюйгенс и многие другие ученые того времен.

Я нашел в книге »История математики» упоминание о простых числах, совершенных числах. Заинтересовался этим вопросом, прочитал еще некоторые книги и журналы, где содержалось упоминание о числах Мерсенна.

Изучил геометрическую прогрессию из курса 9 класса.

Вычислил некоторые из чисел Мерсенна и обнаружил закономерность, затем доказал, что числа вида — простое число Мерсенна, -это совершенные числа. Это такие замечательные числа.

Марен Мерсенн родился в крестьянской семье 8.09.1588году, в посёлке Уазе; в наши дни это департамент Сарта. Учился в иезуитском коллеже в Ла-Флеш, вместе с Декартом, тесную дружбу с которым Мерсенн пронёс через всю жизнь.

В 1611 году Мерсенн присоединился к францисканскому ордену «минимов». Далее он продолжил обучение в Париже. В 1613 году был рукоположен в священники, но не прекратил обучения, занявшись математикой, музыкой и философией.

Совершил несколько путешествий по Европе, побывал в Италии, Германии, Голландии и других странах. Во время поездок приобретал новые знакомства, завязывал переписку, слушал лекции в местных университетах.

Затем Мерсенн вернулся в Париж, поселился в монастыре и последующие десятилетия отдал науке и преподаванию философии.

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

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

Позднее из этого кружка образовалась, при содействии Кольбера, Парижская Академия наук (1666).

На протяжении первой половины XVII века Марен Мерсенн был по существу координатором научной жизни Европы, ведя активную переписку практически со всеми видными учёными того времени. Эта переписка имеет огромную научную и историческую ценность. Имеет также серьёзные личные научные заслуги в области математики, акустики и теории музыки.

Мерсенн вёл чрезвычайно оживлённую переписку (на латинском языке), представляющую громадный исторический интерес. В числе его 78 корреспондентов, кроме Декарта, были Галилей, Кавальери, Паскаль, Роберваль, Торричелли, Ферма, Гюйгенс, Гассенди, Дж. Б.

Дони и многие другие. Научная периодика тогда не существовала, и деятельность Мерсенна значительно способствовала быстрому прогрессу физико-математических наук. 17-томное собрание переписки Мерсенна было издано в Париже в 1932-1988 годах. Умер 1.09.

1648году, не дожил до 60-летия семи дней.

Эта деятельность Марена Мерсенна способствовала созданию в Париже Академии наук.

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

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

Тот, кто знает, что такое геометрическая прогрессия, сразу заметит, что равняется сумме первых n членов геометрической прогрессии с первым членом = 1 и знаменателем 2:

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

Вопрос этот возник в задаче, поставленной еще древними грекам. Они занимались совершенными числами- числами, равными сумме всех своих натуральных делителей, отличных, конечно же, от самого числа. Например, 6=1+2+3, 28=1+2+4+7+14, 496=1+2+4+8+16+31+62+124+248 – первые три совершенных числа.

Простые числа, получающиеся по формуле =, и называются числами Мерсенна.

Попробовал и я коснуться проблемы поиска чисел Мерсенна. Вычислил несколько первых чисел по формуле и записал их по порядку в таблицу из четырех столбиков.

= 1

= 31

= 511

= 8.191

= 131.071

= 2.997.151

= 33.554.431

= 536.870.911

= 3

= 63

= 1.023

= 16.383

= 262.143

Источник: https://infourok.ru/tvorcheskaya_rabota_uchenika_8_klassa_po_temechisla_mersenna-182686.htm

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

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

В декабре прошлого года 51-летний Джонатан Пейс, инженер-электромеханик из американского штата Теннесси обнаружил 50-е простое число из ряда так называемых чисел Мерсенна. Новое простое число в десятичной записи содержит 23 249 425 цифр. Заметим, что в романе «Война и мир» всего около 3,1 миллиона символов. Число, открытое Пейсом, составляет примерно восемь таких романов.

Почему математический мир охвачен ажиотажем по этому поводу, зачем нужны числа Мерсенна и как их используют в повседневной жизни, корреспонденту «МИР 24» рассказал кандидат физико-математических наук, доцент кафедры высшей геометрии и топологии механико-математического факультета МГУ Дмитрий Миллионщиков.

Что такое простое число?

{} Оно действительно очень простое, потому что делится только на единицу и на самого себя. 2,3, 5,7 — это самые первые простые числа. Но дальше все начинает усложняться. Еще Эвклид в своих «Началах» доказал, что таких чисел бесконечное множество и самое большое найти просто нельзя.

Проблема в том, что большое простое число очень трудно найти. Список таких чисел веками расширялся методом проб и ошибок. Интерес к ним, то затухал, то разгорался вновь. Новый взрыв интереса произошел в 17 веке благодаря Марену Мерсенну, францисканскому монаху, теологу и математику, другу великого Рене Декарта.

Как и многие математики той эпохи, он всю жизнь занимался поиском совершенных чисел, то есть таких чисел, которые представляют собой сумму всех своих делителей (самым маленьким совершенным числом является число 6=2+3+1). Однако однажды Мерсенн заинтересовался числами другого вида.

Это были степени двойки, уменьшенные на единицу. Например, 2 в степени 1 — 1 = 1; 2 в степени 2 — 1 = 3, 2 в степени 3 — 1 = 7. Первые три числа, полученные по этой формуле, оказались простыми, но уже четвертое (2 в степени 4=15) было составным.

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

В 1648 году Мерсенн выпустил загадочный труд Cogitata Physica-Mathematica. В этой работе, не особенно утруждая себя доказательствами, он предположил, что двойка в степенях 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, уменьшенная на единицу, обязательно даст в результате простое число.

Все остальные числа, рассчитанные по этой формуле, будут составными. Почему он так решил — непонятно. Мерсенн и сам не настаивал на своей гипотезе. Однако после его смерти она стала необычайно популярна.

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

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

Эпоха компьютерных технологий вернула интерес к поиску большого простого числа. Двое американских школьников — Лаура Никел и Лэндон Нолл — в конце 70-х обнаружили 25-е простое число Мерсенна, используя мощный по тем временам компьютер.

Степень, в которую надо было возвести двойку, оказалась равна 21 701. На тот момент это было самое большое простое число. Впрочем, чуть позже Нолл уже в одиночку открыл и следующее, 26-е число.

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

Кто и зачем ищет простые числа?

{} С этого момента охотиться за большими простыми числами принялись не только профессионалы, но и энтузиасты.

В 1995 году был создан специальный проект распределенных вычислений GIMPS (Great Internet Mersenne Prime Search), к которому может подключиться любой желающий. Для этого достаточно бесплатно скачать на свой компьютер программу с сайта GIMPS.

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

«ВКонтакте» урезал музыку

Что делать, куда бежать

Джонатан Пейс, один из участников проекта GIMPS, гонялся за своим числом 14 лет. Впрочем, его коллегу профессора университета Теннесси Криса Колуэлла, удивляет не длительность поиска, а его быстрота: «Удивительно, что мы сумели найти новое число так быстро.

Мы думали, что это займет больше времени. Это то же самое, что наткнуться сразу на двух мертвых кошек — вас удивит, что они могут находиться так близко друг к другу», — сказал профессор.

Кстати, степень двойки в найденном Пейсом 50-м простом числе Мерсенна составляет 77232917.

После объявления о находке нового простого числа, требуется провести проверку. Доказательство «простоты» — дело не простое. Оно требует больших компьютерных мощностей и занимает несколько дней. Число Джонатана Пейса проверку уже прошло и признано научным сообществом. О том, что сейчас испытывает Пейс, пытается представить Дмитрий Миллионщиков.

«Все это напоминает мне фильм «Безымянная звезда». Там главный герой — школьный учитель, увлеченный астрономией. Он сидит в своем маленьком городке, смотрит каждую ночь в телескоп на небо и ищет новые звезды. Это главный смысл его жизни. И вот однажды он находит звезду, которой нет ни в одном атласе. Думаю, что сейчас Джонатан Пейс счастлив так же, как этот герой.

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

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

«С современной системой криптографии мы сталкиваемся каждый день — набираем логины, пароли, используем банковские карты, — объясняет Миллионщиков, — Все системы шифрования достаточно сложны, но в их основе как правило лежат очень очень большие простые числа».

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

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

Источник: https://news.rambler.ru/other/38872678-prostyh-chisel-mersenna-stalo-rovno-50/

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

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

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

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

а) Для начала нужно доказать, что сигма-функция действительно мультипликативна.

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

Теперь завершим доказательство первого факта: если простое число имеет вид 2n – 1, то число N = 2n–1(2n – 1) — совершенное.

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

 + 2n–1)·((2n – 1) + 1) = (2n – 1)·2n = 2N. Здесь было использовано, что раз 2n – 1 — простое число, то σ(2n – 1) = (2n – 1) + 1 = 2n.

б) Доведем до конца и второе решение. Найдем все собственные делители числа 2n–1(2n – 1). Это 1; степени двойки 2, 22, …, 2n–1; простое число p = 2n – 1; а также делители вида 2m·p, где 1 ≤ m ≤ n – 2.

Суммирование всех делителей тем самым разбивается на подсчет сумм двух геометрических прогрессий. Первая начинается с 1, а вторая — с числа p; у обеих знаменатель равен 2.

По формуле суммы элементов геометрической прогрессии сумма всех элементов первой прогрессии равна 1 + 2 + … + 2n–1 = (2n – 1)/2 – 1 = 2n – 1 (и это равно p).

Вторая прогрессия дает p·(2n–1 – 1)/(2 – 1) = p·(2n–1 – 1). Итого, получается p + p·(2n–1 – 1) = 2n–1·p — то, что надо.

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

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

Прежде чем доказывать теорему Эйлера, отметим еще, что если 2n – 1 — простое число Мерсенна, то n также должно быть простым числом.

Дело в том, что если n = km — составное, то 2km – 1  = (2k)m – 1 делится на 2k – 1 (поскольку выражение xm – 1 делится на x – 1, это одна из формул сокращенного умножения).

А это противоречит простоте числа 2n – 1. Обратное утверждение — «если n — простое, то 2n – 1 также простое» — не верно: 211 – 1 = 23·89.

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

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

Тогда N = 2k·m = 2k(2k+1 – 1), что и требовалось.

Итак, формулы доказаны. Применим их, чтобы найти какие-нибудь совершенные числа. При n = 2 формула дает 6, а при n = 3 получается 28; это первые два совершенных числа.

По свойству простых чисел Мерсенна, нам нужно подобрать такое простое n, что 2n – 1 будет также простым числом, а составные n можно вообще не рассматривать. При n = 5 получится 2n – 1 = 32 – 1 = 31, это нам подходит. Вот и третье совершенное число — 16·31 = 496.

На всякий случай проверим его совершенность явно. Выпишем все собственные делители 496: 1, 2, 4, 8, 16, 31, 62, 124, 248. Их сумма равна 496, так что всё в порядке. Следующее совершенное число получается при n = 7, это 8128.

Соответствующее простое число Мерсенна равно 27 – 1 = 127, и довольно легко проверить, что оно действительно простое. А вот пятое совершенное число получается при n = 13 и равно 33 550 336. Но проверять его вручную уже очень утомительно (однако это не помешало кому-то открыть его еще в XV веке!).

Источник: https://elementy.ru/problems/186/Sovershennye_chisla

О проекте :: команда gimps.russia

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

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

Числами Мерсенна принято называть ряд 2p -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-значное еще ждут своего часа!

http://ru.wikipedia.org/wiki/Мерсенн,_Марен

http://ru.wikipedia.org/wiki/Числа_Мерсенна
http://ru.wikipedia.org/wiki/Тест_Люка_—_Лемера
http://ru.wikipedia.org/wiki/Electronic_Frontier_Foundation

Эра GIMPS К концу 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) — перепроверка уже проверенного ранее числа

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

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

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

Ознакомиться подробнее с описаниями данных расчетов можно на сайте GIMPS:

http://mersenne.org/various/math.php

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

НомерЧислоРазмерностьДатаОткрывательАлгоритм и компьютерКомпьютерная Эра:Эра GIMPS:
122 -11 цифра~500 до н.э.Древнегреческие математики
223 -11~500 до н.э.Древнегреческие математики
325 -12~275 до н.э.Древнегреческие математики
427 -13~275 до н.э.Древнегреческие математики
5213 -141456НеизвестноПростое деление
6217 -161588Pietro CataldiПростое деление
7219 -161588Pietro CataldiПростое деление
8231 -1101772Leonhard EulerУлучшенное простое деление
9261 -1191883Иван Михеевич ПервушинПоследовательность Люка
10289 -1271911.06R.E.PowersПоследовательность Люка
112107 -1331914.06.11R.E.PowersПоследовательность Люка
122127 -1391876.01.10Edouard LucasПоследовательность Люка
132521 -11571952.01.30Raphael M.RobinsonLL / SWAC
142607 -11831952.01.30Raphael M.RobinsonLL / SWAC
1521,279 -13861952.06.25Raphael M.RobinsonLL / SWAC
1622,203 -16641952.10.07Raphael M.RobinsonLL / SWAC
1722,281 -16871952.10.09Raphael M.RobinsonLL / SWAC
1823,217 -19691957.09.08Hans RieselLL / BESK
1924,253 -11,2811961.11.03Alexander HurwitzLL / IBM 7090
2024,423 -11,3321961.11.03Alexander HurwitzLL / IBM 7090
2129,689 -12,9171963.05.11Donald B.GilliesLL / ILLIAC II
2229,941 -12,9931963.05.16Donald B.GilliesLL / ILLIAC II
23211,213 -13,3761963.06.02Donald B.GilliesLL / ILLIAC II
24219,937 -16,0021971.03.04Bryant TuckermanLL / IBM 360/91
25221,701 -16,5331978.10.30Landon Curt Noll & Laura NickelLL / CDC Cyber 174
26223,209 -16,9871979.02.09Landon Curt NollLL / CDC Cyber 174
27244,497 -113,3951979.04.08Harry Lewis Nelson & David SlowinskiLL / Cray 1
28286,243 -125,9621982.09.25David SlowinskiLL / Cray 1
292110,503 -133,2651988.01.28Walter Colquitt & Luke WelshLL / NEC SX-2
302132,049 -139,7511983.09.19David SlowinskiLL / Cray X-MP
312216,091 -165,0501985.09.01David SlowinskiLL / Cray X-MP/24
322756,839 -1227,8321992.02.19David Slowinski & Paul GageLL / Maple — Harwell Lab Cray-2
332859,433 -1258,7161994.01.04David Slowinski & Paul GageLL / Cray C90
3421,257,787 -1378,6321996.09.03David Slowinski & Paul GageLL / Cray T94
3521,398,269 -1420,9211996.11.13GIMPS / Joel ArmengaudLL / Prime95 — 90 MHz Pentium PC
3622,976,221 -1895,9321997.08.24GIMPS / Gordon SpenceLL / Prime95 — 100 MHz Pentium PC
3723,021,377 -1909,5261998.01.27GIMPS / Roland ClarksonLL / Prime95 — 200 MHz Pentium PC
3826,972,593 -12,098,9601999.06.01GIMPS / Nayan HajratwalaLL / Prime95 — 350 MHz Pentium II IBM Aptiva
39213,466,917 -14,053,9462001.11.14GIMPS / Michael CameronLL / Prime95 — 800 MHz Athlon Thunderbird
40220,996,011 -16,320,4302003.11.17GIMPS / Michael ShaferLL / Prime95 — 2 GHz Dell Dimension
41224,036,583 -17,235,7332004.05.15GIMPS / Josh FindleyLL / Prime95 — 2.4 GHz Pentium 4 PC
42225,964,951 -17,816,2302005.02.18GIMPS / Martin NowakLL / Prime95 — 2.4 GHz Pentium 4 PC
43230,402,457 -19,152,0522005.12.15GIMPS / Curtis Cooper & Steven BooneLL / Prime95 — 2 GHz Pentium 4 PC
44232,582,657 -19,808,3582006.09.04GIMPS / Curtis Cooper & Steven BooneLL / Prime95 — 3 GHz Pentium 4 PC
45237,156,667 -111,185,2722008.09.06GIMPS / Hans-Michael ElvenichLL / Prime95 — 2.83 GHz Core 2 Duo PC
46 ??242,643,801 -112,837,0642009.04.12GIMPS / Odd M. StrindmoLL / Prime95 — 3 GHz Core 2 PC
47 ??243,112,609 -112,978,1892008.08.23GIMPS / Edson SmithLL / Prime95 — Dell Optiplex 745
48 ??257,885,161 -117,425,1702013.01.25GIMPS / Curtis CooperLL / Prime95 — Intel Core2 Duo E8400 @ 3.00GHz
49 ??274,207,281 -122,338,6182016.01.07GIMPS / Curtis CooperLL / Prime95 — Intel i7-4790 @ 3.60GHz
50 ??277,232,917 -123,249,4252017.12.26GIMPS / Jonathan PaceLL / Prime95 — Intel i5-6600 @ 3.30GHz

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

Его парк компьютерной техники, задействованной в проекте, насчитывает более 19,000 ПК! Неудивительно, что он четырежды (!) становился номинантом награды. Но поиск очередного простого числа — не единственная задача проекта. Но другом его полюсе ведутся активные поиски делителей чисел Мерсенна, которые существенно сокращают список претендентов на полноценное тестирование LL.

Здесь особо отличается японец Тадаси Таура (Tadashi Taura) — имя в проекте TJAOI.

Он знаменит тем, что много лет собирает у себя дома различную вычислительную технику, и живет, по сути, внутри мэйнфрейма! За четверть века он нашел более полутора десятков делителей чисел Ферма и несколько миллионов (!) делителей чисел Мерсенна! Денежных выплат за делители в проектах не предусмотрено, поиск ведется исключительно на чистом энтузиазме!

Первоисточник: http://mersenne.org/primes/

Статус проекта на 2018.01.08 Проект охватывает диапазон экспонент до 999,999,999 (50,847,533 кандидата).

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

Проверены хотя бы однократно все экспоненты до 76,333,099. Дважды перепроверены все экспоненты до 42,042,053. До подтверждения номера 46-го простого числа Мерсенна осталось 1,044 тестов. До подтверждения номера 47-го простого числа Мерсенна осталось 2,583 тестов. До подтверждения номера 48-го простого числа Мерсенна осталось 234,790 тестов. До подтверждения номера 49-го простого числа Мерсенна осталось 545,890 тестов. До подтверждения номера 50-го простого числа Мерсенна осталось 602,767 тестов. Узнать текущее положение дел можно на этой странице:

http://mersenne.org/report_milestones/

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

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

Каждый обнаруженный делитель будет подписан вашим именем. К тому же он сэкономит проекту несколько месяцев ненужного более теста простоты! К настоящему моменту найдено уже более 33 миллионов делителей.

Непроверенными остаются еще чуть меньше 23 миллионов экспонент — так что на наш век хватит!

Поэтому рискну дать совет: опробуйте сперва свои силы на небольших заданиях.

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

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

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

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

First time tests — 2-3 месяца интенсивно

Double-check tests — пару месяцев

Trial factoring — около суток

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

Trial factoring to low limits — чуть больше часа

ECM on small Mersenne numbers — примерно 25 минут

ECM on Fermat numbers — около 15 часов (но бывает и месяц)

100,000,000 digit numbers to test — 2 года и более

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

http://mersenne.org/report_recent_results/

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

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

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

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

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

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

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

Источник: http://mersenne.ru/info.htm

Простые числа Мерсенна и тест Люка-Лемера

Простые числа Мерсенна. Совершенные числа
Перевод поста Джона Макги (John McGee) «Mersenne Primes and the Lucas–Lehmer Test».
Код, приведенный в статье, можно скачать здесь.

Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации

.

— Введение.
— Теорема множителей Эйлера и Мерсенна
— Люка и Лемер
— От до
— Совершенные числа
— 21-е, 22-е и 23-е числа Мерсенна
— 24-е, 25-е и 26-е числа Мерсенна.
— 27-е и 28-е числа Мерсенна
— 29-е число Мерсенна
— 30-е и 31-е числа Мерсенна
— Великий интернет-поиск чисел Мерсенна
— Факторизация чисел Мерсенна
Простое число Мерсенна — простое число вида (значение степени р также должно быть простым). Эти простые числа получили свое название от имени французского математика и религиозного ученого Мерсенна, который и составил данный список простых чисел этой формы в первой половине семнадцатого века. Первые четыре из них были известны уже давно: , , и .

Мерсенн утверждал, что значение будет простым для простых чисел , принадлежащих множеству . Во всем ли он был прав, можно проверить с помощью функции Wolfram Language — PrimeQ, в которой используются современные методы тестирования чисел на простоту, для которых не требуется поиска конкретного множителя, чтобы доказать, что число составное.

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

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

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

Первые важные достижения в области проверки на простоту принадлежат великому математику Леонарду Эйлеру, который незадолго до 1772 года уточнил, что является простым. Он сделал это, продемонстрировав, что любой простой делитель должен быть равен 1 или 62 (mod 248).

Такой относительно короткий список даже во времена Эйлера мог быть проверен с помощью пробного деления (вручную).

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

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

Мы используем эти функции, чтобы быстро найти делитель . Обратите внимание, что является делителем тогда и только тогда, когда . Это дает возможность использовать функцию PowerMod, что обеспечивает эффективное возведение в степень по модулю.

Ниже приводится число Мерсенна с 161649 знаками:.

Следующим важным шагом стало открытие Эдуардом Люка метода для проверки простоты чисел данной формы. Он использовал свой метод в 1876 году для проверки, является ли (самое большое число Мерсенна «докомпьютерной» эпохи) простым. В начале двадцатого века, когда основы двоичной арифметики и алгебры стали широко известны, Дерек Генри Лемер усовершенствовал метод Люка. Полученный в результате тест простоты чисел Люка-Лемера обеспечивал эффективную проверку, если число данной формы являлось простым. Проверка проводилась с помощью сравнения по модулю:

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

Рассмотрим следующий пример. Здесь мы покажем, что для . Обратите внимание, что (23 бита низшего порядка) и — означает, что остальные биты сдвинуты в крайнее нижнее положение.

Функция ниже задает этот метод для вычисления с использованием только битовых операций (без деления). Обратите внимание на то, что имеет двоичную форму , при этом нет ни одного 0, и поэтому она также служит в качестве маски для битов низшего порядка числа .

Следующая функция реализует тест простоты Люка-Лемера (LLT). Определим последовательность , . Тогда является простым тогда и только тогда, когда .

Опыт показывает, что основное время выполнения этих функций тратится на целочисленную арифметику.

Чтобы проверить, является ли простым, лучше сначала проверять простоту на небольших простых делителях и выполнять другие проверки простоты. Сначала мы используем теорему делителей простых чисел Мерсенна, закодированную в checkMPDivisors, а затем функцию PrimeQ. Если это не сработает, применим тест Люка-Лемера.

Здесь мы представляем расширенную версию функции PrimeQ, которая применяет тест Люка-Лемера для больших чисел вида .

Первым простым числом Мерсенна, обнаруженным на компьютере с помощью теста Люка-Лемера, стало , найденное Рафаэлем Робинсоном 30 января 1952 года на базе лампового компьютера SWAC (Standards Western Automatic Computer). Ниже вы видите блок памяти этого компьютера, содержащий 256 слов по 37 бит каждое.

20-е простое число Мерсенна было обнаружено Александром Гурвицем в ноябре 1961 года в результате проведения 50-минутного теста Люка-Лемера на IBM 7090. Ниже мы воспроизводим эти результаты (на это потребовалось около 151 секунд машинного времени на современном одноядерном ноутбуке).

Одной из особенностей Wolfram Language, делающей его пригодным для такого рода работы, является его быстрая целочисленная арифметика. Поиск простых чисел Мерсенна стал настоящим вызовом на рассвете эпохи компьютеризированного поиска.

Исследователи адаптировали методы быстрого преобразования Фурье для преобразования задачи умножения двух больших целых чисел в простое поэлементное произведение трансформированных цифр. Быстрое умножение целых чисел необходимо для шага возведения в квадрат в тесте Люка-Лемера.

В Wolfram Language используются новейшие алгоритмы, оптимизированые для работы с точными целыми числами с миллиардами символов. Например, убедимся, что последнее из них, — , — на самом деле простое число Мерсенна, и продемонстрируем все его цифры.

Существует интересная связь между простыми числами Мерсенна и совершенными числами. Совершенное число — это число, равное сумме всех своих делителей (отличных от самого числа). Евклид предполагал, а Эйлер доказал, что все четные совершенные числа, имеют вид . Функция Wolfram Language PerfectNumberQ проверяет, является ли число совершенным. Продемонстрируем это свойство на .
Перейдем к переоткрытию 21-го, 22-го и 23-го чисел Мерсенна (будем обозначать их далее в форме вида ): , , . Все они были обнаружены Дональдом Гиллисом, который запускал LLT на ILLIAC II всю весну 1963 года (см. здесь). Для проверки всех чисел вида для простых чисел в промежутке нам понадобилось около 6 минут.
Далее мы расширяем поиск, чтобы найти , , . Последнее из них было обнаружено в феврале 1979 г. Лэндоном Куртом Ноллом и Лорой Никель. Они искали в диапазоне от до на суперкомпьютере CDC Cyber 174 (почитать об этом можно здесь). Наши расчеты становятся более долгими, так что мы начинаем использовать параллельную обработку. Поскольку тесты независимы, для ускорения работы мы можем использовать ParallelMap. Проверка диапазона занимает приблизительно три с половиной минуты (используются 4 ядра).

Обратите внимание на то, что специализированный тест Люка-Лемера значительно быстрее, чем более общая функция PrimeQ (для данных чисел Мерсенна).

Далее мы проверили диапазон , чтобы найти число . Оно было обнаружено в апреле 1979 года Гарри Нельсоном и его командой (они использовали суперкомпьютер Cray-1). Наш поиск завершился за 15 минут.

Следующее число Мерсенна, . Оно был открыто в сентябре 1982 года Дэвидом Словински — также на Cray-1. Этот суперкомпьютер весил около 5 тонн и потреблял около 115 киловатт электроэнергии, а его вычислительная производительность достигала 160 мегафлопс.

Он поставлялся с 1 миллионом 64-разрядных слов памяти (8 мегабайт), а стоил около 16000000$ в сегодняшних ценах. Ниже показана деталь его системы охлаждения.

Для сравнения: Raspberry Pi весит несколько унций, работает на 4 Вт, обеспечивает около 410 мегафлопс и снабжен 1Гб оперативной памяти, и это все — за 40$. А еще он поставляется сразу с системой Mathematica.

Число содержит 25962 цифры. Это значение мы нашли за 1 час и 14 минут (на моем ноутбуке, а не на Raspberry Pi), проводя испытания в диапазоне .

Поскольку теперь нам требуется более серьезное компьютерное время, мы также производим отметку времени для каждого прогона. Теперь мы проверяем диапазон . Через 1 час и 44 минут компьютер показал: . Это число впервые было обнаружено 29 января 1988 года Уокер Колкуиттом и Люком Уэлшем (суперкомпьютер NEC DX-2; статью можно найти здесь).

Следующие два простых числа Мерсенна: и , — были на самом деле обнаружены еще до 29-го (той же командой, которая обнаружила и 28-е). Они использовали Cray X-MP, чтобы найти 30-е число Мерсенна в сентябре 1983 года и 31-е — в сентябре 1985 года. Проверим с помощью функции поиска в диапазоне . Для проверки каждого в этом диапазоне понадобилось 4 часа и 8 минут.
С открытием 34-го простого числа Мерсенна — — в сентябре 1996 года закончилась эпоха суперкомпьютеров для поиска простых чисел Мерсенна. Следующие 15 были найдены добровольцами Великого интернет-поиска простых чисел Мерсенна (GIMPS), в рамках которого проводится вариант теста Люка-Лемера (в качестве фонового процесса) на персональных компьютерах. Этот масштабный проект распределенных вычислений в настоящее время достигает уровня производительности, эквивалентного приблизительно 300 терафлопс в секунду, причем задействуется время простоя более чем 1,3 миллиона компьютеров.

Проверим 34-е число Мерсенна с помощью теста Люка-Лемера. На этом этапе мы достигли предела возможностей личного компьютера. На тестирование тысячи чисел Мерсенна в этом диапазоне потребуется много дней.

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

Тот факт, что мы проверили каждое для простых чисел в промежутке между 2 и 139901, убедительно доказывает надежность арифметики больших чисел и бинарных операций в системе Mathematica и языке Wolfram Language.

Как мы уже видели, количество возможных множителей в разложении чисел вида согласно теореме множителей Мерсенна ограниченно. Это позволило провести эффективный компьютеризированный поиск делителей больших чисел этой формы. На момент написания этой статьи все числа Мерсенна (до ) были полностью разложены на множители (иллюстрации можно найти здесь). Проект GIMPS также привел к открытию крупных множителей многих чисел Мерсенна в качестве побочного продукта проверки простоты чисел. Новую статью, которая представляет собой современный подход к решению этой проблемы (наряду с 17 новыми факторизациями), можно найти здесь. Наибольшее факторизованное число составило ; его наименьший из найденных делителей имеет 76 десятичных цифр. Его наименьший делитель равен 23. Общее время, необходимое для того, чтобы получить этот результат составляет 7500 лет (речь о компьютерном времени).

Мы можем быстро найти несколько первых множителей с помощью функции FactorInteger.

Все простые числа Мерсенна, обнаруженные на сегодняшний день, каталогизированы в Wolfram Language (до 44-го). Доступ к этой информации обеспечивается функциями MersennePrimeExponent и MersennePrimeExponentQ.

Если вас заинтересовала эта тема, вы можете найти более подробную информацию на следующих веб-сайтах:

  • GIMPS
  • Страницы простых чисел
  • Простые числа

Источник: https://habr.com/post/327342/

Совершенные числа и простые числа Мерсенна-Python

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

Я написал программу, которая вычисляет четные идеальные числа для всех простых чисел Мерсенна из 1-1000, используя ((2n)-1)(2(n-1)) где n-простое число Мерсенна.

Это и есть программа:

def PrimeFinder(PotPrime): PlaceNum=1 for x in range (int(PotPrime**0.5)): PlaceNum=PlaceNum+1 if int(PotPrime/PlaceNum) == (PotPrime/PlaceNum): return False return True TrialNum = 1 for x in range (1000): if PrimeFinder(TrialNum) == True: if PrimeFinder((2**TrialNum)-1) == True: print(TrialNum,»is the Mersenne Prime for the perfect number:»,(2**(TrialNum-1))*((2**TrialNum)-1)) TrialNum = TrialNum+1

Эта программа отлично работает, вплоть до того, где 32 < TrialNum < 60, поскольку она правильно определяет, что 31 является простым числом Мерсенна, однако это не так для 61 (и все числа больше, чем он).

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

python math primes perfect-numbers ИсточникJonathan Beaumont     24 марта 2015 в 00:45

Ошибки округления я полагаю: если вы отлаживаете, вы замечаете, что он думает, что 2 является делителем 261 -1 (что не имеет смысла).Если заменить if int(PotPrime/PlaceNum) == (PotPrime/PlaceNum): на if PotPrime % PlaceNum == 0: это исправлено. Но ваш алгоритм довольно неэффективен, и 261-1-это очень большое число, поэтому ожидайте, что это займет несколько часов. (возможно, даже дольше)

Soronbe     24 марта 2015 в 01:19

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

Вместо

for x in range (int(PotPrime**0.5)):

используйте что-то вроде

while x*x < PotPrime:

Вместо

if int(PotPrime/PlaceNum) == (PotPrime/PlaceNum):

используйте более простой

if PotPrime % PlaceNum == 0:

James K Polk     26 марта 2015 в 10:36

Используйте тест на примитивность Лукаса-Лемера , чтобы проверить, какие простые числа производят простые числа Мерсенна (Mp), таким образом, вы избегаете проверки примитивности самого числа Мерсенна, потому что они довольно большие, и потому что только простой показатель производит Mp, с этим тестом вам нужно только, чтобы этот p был простым и прошел этот тест, тогда вы можете построить свое идеальное число как ((2p)-1)(2(p-1)).

С помощью этого теста я могу найти первые 16 p [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203] это производит Mp en 12seg в моей машине, которая является старой, Pentium Dual-Core 3GHz

Вот код (в python 3.3) вы также можете использовать более мощный тест на примитивность, такой как тест Миллера-Рабина или Baillie-PSW, которые в отличие от пробного разделения не требуют вечности для проверки больших чисел.

def primality_Test_Trial_Division(n:int) -> bool: if n >= 0 : if n= n: break

Copperfield     06 декабря 2015 в 01:13

Как найти все совершенные числа в определенном интервале в c++?

Я хочу найти все совершенные числа от интервала x до y. любая помощь, как я могу это сделать ?

Почему вывод не показывает простые числа на дисплее?

Я работал над этой программой для моего вводного класса Java, и в основном он должен предлагать пользователю меню с выбором, отображать ли простые числа (1-1000), простые числа Мерсенна (1-10000)…

Python простые числа и простые множители

Я очень новичок в Python, и программирование в целом. Я пытаюсь написать программу, которая выплевывает простые множители большого числа. Я написал код, который дает мне простые числа, но он…

Простые Числа python

Я начинающий программист в python и у меня есть вопрос о моем коде, который я пишу: number = int(input(Enter a random number: )) for num in range(1, number + 1) : for i in range(2, num) : if (num %…

Python простые числа

Привет, я новичок в программировании и в python, и у меня есть задание, которое я не могу выполнить. Мне нужно написать программу Python для вычисления и печати первых 200 простых чисел. Выходные…

Простые Числа PYTHON:

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

Как вычислить числа Мерсенна во время компиляции

Примечание: это Q&A не о мерсеннском твистере, а о числах Мерсенна . Я хочу вычислить во время компиляции массив размера N, содержащий простые числа Мерсенна (2 n -1) для n в [0, N — 1]….

поиск идеальных чисел из простых чисел Мерсенна-очень странный результат

не могли бы вы помочь мне с тем, где моя функция идет не так? Я хочу создать функцию, которая перечисляет совершенные числа до 2N -1, используя тот факт, что если q − простое число Мерсенна…

найти простые числа в python

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

Палиндромические простые числа в python

Поэтому я пытаюсь выяснить, как найти все простые числа палиндрома между 2 числами. Пока мой код может найти палиндром, но когда я проверяю простое число, он также выводит не простые числа. И есть…

Источник: https://coderoad.ru/29223052/%D0%A1%D0%BE%D0%B2%D0%B5%D1%80%D1%88%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5-%D1%87%D0%B8%D1%81%D0%BB%D0%B0-%D0%B8-%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5-%D1%87%D0%B8%D1%81%D0%BB%D0%B0-%D0%9C%D0%B5%D1%80%D1%81%D0%B5%D0%BD%D0%BD%D0%B0-Python

Refy-free
Добавить комментарий