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

Абстракт     Цель работы: классифицировать совершенные числа по их свойствам и  закономерностям, составить программу для вычисления совершенных чисел на данном диапазоне чисел и исследовать их свойства.              Гипотеза: множество совершенных чисел является бесконечным.  Среди совершенных чисел встречаются как чётные, так и нечетные числа.     Этапы и процедура исследования:  этап дата процедура исследования I II III изучение теоретических источников,  определением научного аппарата исследования исследование практической части работы проведение анализа, обобщение всего  материала      Методика эксперимента: 1) Изучение теоретических источников; 2) Поиск решений задач по теме исследования; 3) Изучение трудов ученых­исследователей; 4) Обобщение и систематизирование собранного материала.     Научная новизна работы заключается в рассмотрении свойств  совершенных числе и доказательстве их теорем, в поиске олимпиадных задач  о совершенных числах  и решение некоторых сложного рода задач на языке  программирования Паскаль.     Результаты работы и выводы: основной смысл работы заключается в  доказательстве теорем о совершенных числах и решении некоторых сложного  рода задач на языке программирования Паскаль. Результаты этой работы  могут быть полезны в прикладной математике. 3 Abstract        Purpose of the work:  to  classify perfect numbers by their functions and legitimacies, to compose program for calculating perfect numbers on the given spectrum of numbers and explore their functions.     Hypothesis: the number of perfect numbers is infinite. There are both even and odd numbers among perfect numbers.     The procedure and the stages of the study:  ­ First stage September – November 2013) related with the study of theoretical  sources, the definition of scientific research. ­ Second stage (December – February 2013) study the practical part of the work. ­ Third stage (March ­ May 2013) carrying out analysis, generalization of all  material.      The experimental procedure: 1) The study of the theoretical sources; 2) Looking for solutions for problems;      3) Studying of works of scientists­researchers;      4) Generalization and systematization of a collected material.     The scientific novelty is based on the consideration of perfect number functions and on proof of their theorems, on the search of Olympiad exercises about perfect  numbers and solutions of complicated problems on the Pascal program language.     The results and conclusions :the main meaning of this work is based the  consideration of perfect number functions and on proof of their theorems, on the  search of Olympiad exercises about perfect numbers and solutions of complicated  problems on the Pascal program language. The results of this work can be useful in applied mathematics science. 4 Никомах Геразский, славный грек,                                                                                             знаменитый философ и математик,                                                                                                   писал: «Совершенные числа красивы.                                                                                                          Красивые вещи редки и немногочисленны,                                                                                                       безобразные же встречаются в изобилии.                                                                                                         Избыточными и недостаточными бывают                                                                                                         все числа, в то время как совершенных                                                           чисел немного». Введение Число ­ одно из основных понятий математики, позволяющее выразить результаты счета или измерения. Понятие числа служит исходным для многих математических   теорий.   Числа   находят   широкое   применение   в     физике, механике, астрономии, химии и многих других науках. Числами постоянно пользуются в повседневной жизни. Возникновение   чисел   в   нашей   жизни   не   случайность.   Невозможно представить   себе   общение   без   использования   чисел.   История   чисел увлекательна   и   загадочна.   Человечеству   удалось   установить   целый   ряд законов   и   закономерностей   мира   чисел,   разгадать   кое­какие   тайны   и использовать   свои   открытия   в   повседневной   жизни.   В   школьном   курсе математики   постепенно   знакомят   со   всеми   числами,   в   том   числе   с натуральными,   действительными,   рациональными   и   иррациональными. Изучаются действия с ними, их свойства. Актуальность исследования данной темы   заключается   в   том,   что   изучение     свойств   чисел   в   школьном   курсе математики   ограниченно.   Наше   исследование   нацелено   на   выявление совершенных   свойств   чисел,   то   есть   тех,   о   которых   нельзя   прочесть   на страницах   школьных   учебниках.   Интерес   к   данной   теме   вызван   тем,   что многие столетия ума ученых были заняты отысканием различных видов чисел 5 и   их   свойств,   некоторые   из   них   были   найдены   только   после   развития компьютерной техники. На сегодняшний день эти поиски продолжаются.  Предметом   исследования являются совершенные числа: рассмотрение их   свойств,   доказательства   теорем   о   совершенных   числах,   олимпиадные задачи о совершенных числах  и решение некоторых сложного рода задач на языке программирования Паскаль.    Актуальность  данного исследования заключается в  том, что совершенные числа   образуют   одно   из   наиболее   интересных   подмножеств   множества натуральных   чисел.   Они   обладают   необычной   историей,   удивительными свойствами.     Цель   исследования  заключается   в   том,   чтобы   классифицировать   совершенные   числа   по   их   свойствам   и     закономерностям,   составить программу на вычисления совершенных чисел на данном диапазоне чисел и исследовать их свойства.    Задачи по достижению цели: ­ рассмотреть основные этапы развития совершенных чисел; ­ дать определение совершенным числам; ­ классифицировать совершенные числа;     ­ выделить совершенные числа на данном диапазоне чисел; ­ установить ряд удивительных свойств, законов и закономерностей этих чисел.      Объектом исследования  являются труды Г.И.Гейзера, Я.И. Перельмана, Е.И.Деза, а  также   «Британская энциклопедия» и  главная редакция физико­ математической литературы Москва «Наука».    Предметом  исследования являются совершенные числа: рассмотрение их свойств, доказательства теорем о совершенных числах, олимпиадные задачи о совершенных числах   и решение  некоторых сложного рода  задач на языке программирования Паскаль. 6 Структура работы: работа состоит из введения, теоретической и  практической частей, заключения, списка использованных источников и  приложения.        Данная   работа   имеет  теоретическую   и   практическую   значимость, которая может быть полезна в прикладной математике. I. Этапы развития натуральных чисел Число является одним из основных понятий математики. Понятие числа развивалось   в   тесной   связи   с   изучением   величин;   эта   связь   сохраняется   и теперь.  Считается, что термин "натуральное число" впервые применил римский государственный  деятель, философ, автор трудов  по математике  и теории музыки   Боэций   (480   –   524   гг.),   но   еще   греческий   математик   Никомах   из Геразы говорил о натуральном, то есть природном ряде чисел. Понятием   "натуральное   число"   в   современном   его   понимании последовательно пользовался выдающийся французский математик, философ­ просветитель Даламбер (1717­1783 гг.) Первоначальные представления о числе появились в эпоху каменного века, при переходе от простого собирания пищи к ее активному производству, примерно   100   веков   до   н.   э.   Числовые   термины   тяжело   зарождались   и медленно   входили   в   употребление.   Древнему   человеку   было   далеко   до абстрактного мышления, хватило того, что он придумал числа: "один" и "два". Остальные количества для него оставались неопределенными и объединялись в понятии "много". Росло производство пищи, добавлялись объекты, которые требовалось учитывать в повседневной жизни, в связи, с чем придумывались новые числа: "три", "четыре"… Долгое время пределом познания было число "семь". 7 О непонятном говорили, что эта книжка "за семью печатями", знахарки в сказках давали больному "семь узелков с лекарственными травами, которые надо   было   настоять   на   семи   водах   в   течение   семи   дней   и   принимать каждодневно по семь ложек". Познаваемый мир усложнялся, требовались новые числа. Так дошли до нового предела. Им стало число 40. Запредельные количества моделировались громадным по тем временам числом "сорок сороков", равным 1600. Большой интерес вызывает история числа "шестьдесят", которое часто фигурирует  в  вавилонских,  персидских   и  греческих   легендах   как   синоним большого числа. Вавилоняне считали его Божьим числом: шестьдесят локтей в высоту имел золотой идол из храма вавилонского  царя Навуходоносора. Позже с тем же самым значением (неисчислимое множество) возникли числа, кратные   60:   300,   360.   Со   временем   число   60   в   Вавилоне   легло   в   основу шестидесятеричной   системы   исчисления,   следы   которой   сохранились   до наших дней при измерении времени и углов. Следующим   пределом   у   славянского   народа   было   число   "тьма",   (у древних греков – мириада), равное 10 000, а запределом – "тьма тьмущая", равное   100   миллионам.   У   славян   применяли   также   и   иную   систему исчисления (так называемое "большое число" или "большой счет"). В Античном мире дальше всех продвинулись Архимед (III в. до н.э.) в "исчислении песчинок" ­ до числа 10, возведенного в степень 8×1016 , и Зенон Элейский (IV в. до н. э.) в своих парадоксах – до бесконечности ∞. Долго   и   трудно   человечество   добиралось   до   1­го   уровня   обобщения чисел.   Сто   веков   понадобилось,   чтобы   выстроить   ряд   самых   коротких натуральных чисел от единицы до бесконечности:1, 2, … ∞ . Натуральных потому, что ими обозначались реальные неделимые объекты: люди, животные, вещи… Самое трудное было придумать нуль. Его придумали на много веков 8 позже,   чем   другие   цифры.   Первая   точно   датированная   запись,   в   которой встречается знак нуля, относится к 876 г. 2. Свойства простых чисел Простые числа можно обнаружить только путем долгих кропотливых расчетов. Недавно было найдено простое число, содержащее 25692 цифры! Чтобы   доказать,   что   оно   простое,   быстродействующему   компьютеру потребовалось   несколько   недель.   Удивительными   являются     свойства некоторых простых чисел. Рассмотрим некоторые свойства 7. Рассмотрим арифметическую прогрессию, первым членом и разностью которой является число 15 873. Будем умножать каждый из членов данной прогрессии   на   7,   то   получим   очень   странные   произведения.   Числа   15873, 31746, 47619, 63492, 79365, 95238, ..., 142857, умножаемые на 7, всегда дают число, состоящее из шестикратно повторенной одной и той же цифры: 15873 • 7 = 111111  31746 • 7 = 222222 79365 • 7 = 555555 142857 •7 = 999999 Это любопытное сочетание цифр можно легко объяснить, если заметить, что 79365 • 7 = (5 • 15873) • 7 = 5 • (15873 • 7) = 5 • 111111. Значительно   труднее   объяснить   следующее   необычное   явление:   если между двумя цифрами второй степени числа  7, между цифрами числа 49, будем вставлять число 48, то составленные таким образом числа, а именно: 49, 4 48 9, 44 48 89, 444 48 889,... всегда будут полными квадратами: 49 = 72 4489 = 672 444889 = 6672 44448889 = 66672 9 3. Совершенные числа Пифагорейцы   развивали   свою   философию   из   науки   о   числах. Совершенные числа, считали они есть прекрасные образы добродетелей. Они представляют собой середину между излишеством и недостатком. Они очень редки и порождаются совершенным порядком. В противоположность этому сверхизобильные   и   несовершенные   числа,   которых   сколь   угодно   много,  не расположены в порядке и не порождаются с некоторой определенной целью. И поэтому они имеют большое сходство с пороками, которые многочисленны, неупорядочены и неопределены.  Из­за   трудности   нахождения   и   таинственной   непостижимости совершенные числа в старину считались божественными. Так, средневековая церковь полагала, что изучение совершенных чисел ведет к спасению души, что нашедшему новое совершенное число гарантировано вечное блаженство. Существовало   также   убеждение,   что   мир   потому   прекрасен,   что   сотворен создателем за 6 дней. А вот род человеческий, дескать, несовершенен, ибо произошел   от   несовершенного   числа   8.   Ведь   именно   8   людей   спаслось   от всемирного потопа в Ноевом ковчеге. Надо бы возразить, что в том же ковчеге спаслись еще семь пар чистых и семь пар нечистых животных, что в сумме составляет совершенное число 28. Да и вообще легко обнаружить множество подобных   совпадений.   Например,   руки   человеческие   можно   объявить совершенным орудием по той причине, что в десяти пальцах насчитывается 28 фаланг… Сколько же их?  Первым   совершенным   числом,   о   котором   знали   математики   Древней Греции, было число 6. Следующим совершенным числом, известным древним, было число 28. В Риме в 1917 году при подземных работах было открыто странное сооружение: вокруг большого центрального зала были расположены 28 келий. До  10 последнего времени именно столько членов, часто просто по обычаю, причины которого давным­давно забыты, полагалось иметь во многих ученых  обществах. Древних математиков удивляло особое свойство этих двух чисел: каждое из  них равно сумме всех их собственных делителей:  6 = 1 + 2 + 3,  28 = 1 + 2 + 4 + 7 + 14. До Евклида (знаменитый  древнегреческий математик III в. до н. э. ) были известны только эти два числа, и никто не знал, существуют ли еще совершенные числа  и сколько их вообще может быть. Великий основатель геометрии много занимался изучением свойств чисел; конечно, его не могли не   интересовать   совершенные   числа.   Евклид   доказал,   что   всякое   число, которое может быть представлено в виде произведения множителей 2^(p ­1) и (2^p) ­ 1, где второе ­ простое число, является совершенным числом. Если в формулу Евклида подставить p=2, то получим 2 х 3 = 6 ­ первое совершенное число, а если p=3, то 2^(3­1) х (2^3)­1 = 28. Благодаря своей формуле Евклид сумел найти еще два совершенных числа: третье при p=5 и четвертое при p=7. 8128. Вот числа: 496 и       эти       Алгоритм построения чётных совершенных чисел описан в IX книге Начал Евклида.   Эйлер   впоследствии   доказал,   что   все   чётные   совершенные   числа имеют указанный вид.  Дальнейшие поиски оказались более сложными. Следующее,   пятое   совершенное   число   было   найдено   лишь   полторы тысячи лет спустя в пятнадцатом веке немецким математиком Региомонтаном , оказалось, что и оно подчиняется условию Евклида и равно 33 550 336. В   XVI   веке   немецкий   ученый   Шейбель   нашел   еще   два   совершенных числа: 8589869056 и 137438691328. Они соответствуют  р = 17 и р = 19.  11 Однако на этот счет есть еще информация. Катальди   Пьетро   Антонио   (1548­1626),   бывший   профессором математики во Флоренции и Болонье, который первый дал способ извлечения квадратных корней, тоже занимался поисками совершенных чисел. В его  записках были указаны значения шестого и седьмого совершенных чисел.    8 589 869 056 (шестое число), 137 438 691 328 (седьмое число). И навсегда осталась в истории загадочная тайна, как он сумел найти их. До сих пор предложено только одно объяснение этой загадке ­ оно было дано еще его современниками: помощь божественного провидения, подсказавшего своему избраннику верные значения двух совершенных чисел. Однако … Французский   математик   XVII   века   Марен   Мерсенн   предсказал,   что многие числа, описываемые формулой «два в степени p минус один», где p ­ простое число, также являются простыми.  Ему удалось доказать, что p=17, p=19, p=31: Р17=8589869056,           Р19=137438691328,      Р31=2305843008139952128.    являются  совершенными.  Уже позднее  было обнаружено,  что  почти  за  сто  лет  до  Мерсенна числа  p=17,  p=19  нашел итальянский  математик  Катальди. Девятое совершенное число было вычислено только в 1883 году. В нем оказалось   тридцать   семь   знаков.   Этот   вычислительный   подвиг   совершил сельский   священник  из­под   Перми  Иван Михеевич Первушин.  Первушин считал без всяких вычислительных приборов.  В начале XX в. были найдены еще 3 совершенных числа (для р = 89, 107 и 127). До середины XX века обнаружено еще семь таких чисел. С 1952 года в поиски   включились   электронно­вычислительные   машины.   И   если   первое 12 совершенное   число   (6)   однозначно,   то   двадцать   четвертое   содержит   уже свыше 12 000 знаков. На апрель 2014 года известно 47 чётных совершенных чисел. Эти числа скрывают и сегодня много загадок. Неизвестно, ограничено или   бесконечно   их   множество.   Все   открытые   совершенные   числа   парные. Ученые  доказали, что  может  быть не  меньше  1036  непарных  совершенных чисел, но ни одного из них ещё не нашли. Считают, что даже наименьшее из непарных совершенных чисел может быть чрезвычайно большим. Возникают и другие вопросы, ответа на которые ищет много математиков. На октябрь 2008 г. известно 46 чётных совершенных числа, поиском новых таких чисел занимается проект распределённых вычислений GIMPS. Почти   все   последующие   совершенные   числа   выдерживают   только евклидову форму записи. Все   чётные   совершенные   числа   (кроме   6)   являются   суммой   кубов последовательных нечётных натуральных чисел: (13+33+53+…). Сумма всех чисел, обратных делителям совершенного числа (включая его само), равна 2. Например, взяв делители совершенного числа 28, получим: Все   чётные   совершенные   числа,   кроме   6   и   496,   заканчиваются   в десятичной записи на 16, 28, 36, 56 или 76. Знаменитый   греческий   философ   и   математик   Никомах   Герасский, живший в 1 в., отмечал, что совершенные числа красивы, а красивые вещи редки и немногочисленны. Он не знал, сколько имеется совершенных чисел. Не знаем этого и мы.  Определение: натуральное число называется  совершенным  числом если оно равно сумме всех его положительных делителей, не включая само число. 13 6 28 496 = 1+2+3 = 1+2+4+7+14 = 1+2+4+8+16+31+62+124+284 Таблица 1: первые три совершенных числа. 4. Как найти совершенное число? Евклид (примерно 300 лет до н.э.) изобрел простой метод исчисления совершенных  чисел. Начиная  с цифры 1,  продолжайте  прибавлять   степени двух (т. е. удваивая цифры), пока вы не получите сумму, которая является простым   числом.   Затем   получаем   соврешенное   число   путем   умножения данной суммы на последнюю степень двух. Мы   используем   данный   метод,   чтобы   определить   следующие   два совершенных числа. Первые   две   строки   в   таблице   демонстрируют   вычисления, производственные   для   извлечения   первых   трех   совершенных   чисел.   Мы используем   эту  технику,  чтобы   посмотреть,  как   быстро  мы  сможем   найти четвертое идеальное число. Перед   тем,   как   перейти   к   исчислению   пятого   совершенного   числа, сделаем паузу и познакомимся поближе с первыми четырьмя совершенными числами, полученными данным путем. Исчисление   четвертого   и   пятого   совершенного   числа   следуя предписаниям  Евклида. Первые  две  строки  в  таблице демонстрируют использованные вычисления. 1+2 1+2+4 1+2+4+8 1+2+4+8+16 1+2+4+...+16+32 Calculation 2*3 4*7 16*31 Perfekt number 6 28 496 Sum =3 =7 =15 =31 =63 Prime √ √ Χ √ Χ 14 1+2+4+...+32+64 1+2+4+...+64+128 1+2+4+...+128+256 1+2+4+...+256+512 1+2+4+...512+1024 1+2+4+...+1024+2048 1+2+4+...+2048+4096 =127 =255 =511 =1023 =2047 =4095 =8191 √ Χ Χ Χ Χ Χ √ 64*127 8128 4096*8191 Таблица 2: вычисление первых пяти совершенных числа. 33550336 5. Что такое числа Мерсенна? После   вычисления   первых   пяти   совершенных   чисел,   мы   перейдем   к вычислению шестого совершенного числа. Перед этим вернемся к таблице 2. в то время как мы прибавляли степени двух в предыдущей таблице, наблюдали закономерность   в   последовательности   полученных   сумм.   Более   очевидно было бы выразить каждое число в виде степени двух. Теперь   выражаем   первые   две   колоны,   с   предыдущей   таблицы,   в   виде степени двух. Последовательность 1+21 1+21+22 1+21+22+23 1+21+22+23+24 1+21+22+23+24+25 1+21+22+23+24+25+26 Сумма 22 ­1 23 ­1 24 ­1 25 ­1 26 ­1 27 ­1 Таблица 3: последовательность сумм в степени двух. Используя, сокращенное вычисление пришли к решению, позволяющему вычислить следующую сумму: 1+21+22+23+24+25+...+224+225 (226 ­1) Обобщение: Первые n члены ряда: 15 1+21+22+23+24+25+...+2n­2+2n­1 Просто 2n ­1 Вспомним формулу для суммы Геометрической Прогрессии: Sn = Для ряда 1+21+22+23+24+25+...+2n­2+2n­1 а=1, n=2, таким образом: 2n ­1=22k ­1= (2k)2­1= (2k)2­12= (2k ­1)(2k +1) Последовательность чисел, которые мы только что определили 1, 3, 7, 15, 31, 63, 127, …называются числами Мерсенна.  Определение: числа формы 2n ­1 называются числами Мерсенна. Среди простых чисел особую роль играют простые числа Мерсенна ­  числа вида Мn = 2n ­1 , где n ­ простое число. Они называются простыми  числами Мерсенна по имени французского монаха Мерена Мерсенна (1588­ 1648), одного из основателей Парижской Академии наук, друга Декарта и  Ферма. Так как М2=3, М3=7, М5=31, М7=127, то это ­ простые числа   89 простым не является. До 1750 года Мерсенна. Однако, число М11=2047=23 . было найдено всего 8 простых чисел Мерсенна: М2, М3, М5, М7, М13, М17, М19,  М31. То, что М31 ­ простое число, доказал в 1750 году Л. Эйлер. В 1876 году  французский математик Эдуард Люка  установил, что число М127=170141183460469231731687303715884105727  ­ простое. В 1883 г. Сельский священник Пермской губернии И.М.Первушин  без всяких вычислительных приборов доказал, что число  М61=2305843009213693951 является простым. Позднее было установлено, что числа М89 и М107 ­ простые. Использование ЭВМ позволило в 1952­1964 годах  16 доказать, что числа М521, М607, М1279, М2203, М2281, М3217, М4253, М4423, М2689,  М9941, М11213 ­ простые. К настоящему времени известно уже более 30 простых  чисел Мерсенна, одно из которых М216091 имеет 65050 цифр. Если мы обозначим Мn = 2n ­1, тогда последовательность чисел Мерсенна может быть выражена как: М1 = 21 ­1=1 М2 = 22 ­1=3 М3 = 23 ­1=7 М4 = 24 ­1=15 М5 = 25 ­1=31 М6 = 26 ­1=63 М7 = 27 ­1=127 6. Как простые числа Мерсенна связаны с совершенными числами? Если число Мерсенна оказывается простым числом, то оно называется простым числом Мерсенна.    Простые числа Мерсенна являются простыми числами в форме 2n ­1. Мы вычислили первые 5 простых чисел Мерсенна: 3, 7, 31, 127, 8191. Каждое  из  этих чисел в свою  очередь  дает  совершенное число, когда оно умножено его предыдущей степенью двух. Чтобы   сделать   вывод   по   тому,     что   мы   сделали   до   этого   момента, вернемся снова к Таблице 2. Н этот раз мы выразим числа в степени двух и удалим те строки, которые не включают совершенные числа. Последовательность 1+21 1+21+22 1+21+22+23 1+21+22+23+24 17 Сумма 22 ­1 23 ­1 24 ­1 25 ­1 1+21+22+23+24+25 1+21+22+23+24+25+26 26 ­1 27 ­1 Итак, мы можем сократить наши вычисления: Последовательность Сумма 1+2 1+2+4 1+2+4+8 1+2+4+8+16 1+2+4+8+16+34 1+2+4+...+32+64 =3 =7 =15 =31 =63 =127 Следующая таблица выражает первые пять простых чисел Мерсенна и совершенные числа в степени двух. Числа Мерсенна 1+21 1+21+22 1+21+22+23+24 1+21+22+...+25+26 1+21+22+...+211+212 3 7 31 127 8191 22 ­1 23 ­1 25 ­1 27 ­1 213 ­1 Совершенные числа 6 28 496 8128 21(22 ­1) 22(23 ­1) 24(25 ­1) 26(27 ­1) 212(213 ­1) 33550336 Таблица 4: первые пять чисел Мерсенна и соответствующие совершенные числа. Два   совершенных   числа   были   открыты   Катальди   в   1588   году.   Эти совершенные числа можно получить с простых чисел Мерсенна  М17 = 217 ­1 и М19 = 219 ­1. Мы уже поняли почему числа в форме 2n ­1 настолько привлекательны. Каждый раз, когда находится простое число этой формы, можно немедленно получить совершенное число, как было доказано Евклидом.   совершенным числом.  Определение:   если     2n  ­1   простое   число,   то   2(n­1)(2n  ­1)   является   Древние греки знали первые четыре совершенных числа. Многими веками позже   было   найдено   пятое   совершенное.   Оно   было   записано   в   рукописях 18 неизвестного писателя в 1456 году ­   два совершенных числа, которые мы ранее   выработали   с   М17  и   М19,  являются   раскрытыми   шестым   и   седьмым совершенными числами. Таким образом, поиск совершенных чисел превратился в поиск простых чисел Мерсенна, т.е. простые числа в форме 2n  ­1. Но это оказалось очень сложной задачей, так как по мере того, как число увеличивается, становится чрезвычайно томительно тестировать его на простоту без помощи приборов вычисления   таких   как   электронных   калькуляторов,   которые   мы   имеем сегодня. Отец Марин Мерсенн (1588­1648), французский монах, в чью честь числа Мерсенна были названы, заявил, что числа  2n ­1 были простыми для n=2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257 и были составными для всех других целых чисел  n<257. Но это заявление не было полностью плавильным. Ни он, ни его современники не смогли доказать это. 7. Как найти простые числа Мерсенна? Мы внимательно изучим список простых чисел Мерсенна, который был открыт до настоящего времени: М2, М3, М5, М7, М13, М17, М19,... Значение n в этих числах выдают ключ к закономерности возникновения простых чисел Мерсенна. Ряд целых чисел, которые производят простые Мерсенна, сами являются простыми числами. Разумеется, мы бы немедленно захотели доказать может ли число в форме   2n  ­ 1 быть простым, если  n  не является простым. Мы исследуем это далее. Сейчас   без   использования   калькулятора   мы   покажем,   что   М26=   214  ­1 может   быть   разложено   на  множители,  как   разность   квадратов   двух   чисел. Также  М26= 226 ­1. Любое выражение, которое может быть показано как разность квадратов 19 двух   чисел,   может   быть   разложено   на   множители   с   использованием алгебраического тождества: Поэтому a2­b2=(a­b)(a+b) 214­1=(27­1)(27+1) и мы нашли два множителя для  М14. Аналогично, 226­1=(213­1)(213+1) показывающее что М26 не является простым Мерсенна. Мы  можем заключить  что если  n  четное, тогда Мn  не  будет  простым числом Мерсенна. Теперь мы докажем что если n четное число больше 2, то  2n – 1 является составным. Если n четное число больше 2, мы можем написать n=2k  для некоторых целых чисел больше 1. 2n ­1=22k ­1= (2k)2­1= (2k)2­12= (2k ­1)(2k +1) Учитываем: правило индексов (dm)n=dmn  и определение разности квадратов двух чисел. Поэтому 2n – 1 является составным. Теперь покажем что М15= 215 ­1 может быть разложено на множители без использования калькулятора. Формула   для   суммы   геометрической   прогрессии   с   числителем   1   и знаменателем r,   1+r1+r2+...+rn­1= , которое может показано, как: rn­1=(r­1)(1+r1+r2+...+rn­1) М15= 215­1 может быть выражено как (23)5­1 Теперь, если мы заменим  r=(23) и  n=5 в вышеуказанном уравнении, мы 20 получим (23)5­1=((23)­1)(1+(23)1+(23)2+...+(23)5­1). Таким образом, нашли множитель  215­1: 23­1 или 7. Используя этот же способ, мы не можем сделать вывод, что множитель 221­1 является еще и 7. Теперь давайте докажем что если n составное число, то  2n – 1 является составным. rn­1=(r­1)(1+r1+r2+...+rn­1) Если n составное число, то мы можем написать n=pq, где p и  q являются двумя целыми числами. Тогда 2n – 1 может быть выражено как (2p)q­1. Теперь, если мы заменим  r=(2p) и  n=q  в вышеуказанном уравнении, мы получим  (2p)q­1=((2p)­1)(1+(2p)1+(2p)2+...+(2p)q­1). Таким образом, 2n – 1 является составным. С предыдущего обсуждения мы поняли, что единственные значения  n, которые   произведут   простые   числа   Мерсенна,   сами   являются   простыми числами. Поэтому, чтобы найти простые Мерсенна, мы можем полностью не обращать внимания на значения n, которые не являются простыми. Определение:   если   2n  –   1   является   простым,   то  n  должно   быть простым. Тогда как, необходимо чтобы n было простым для того, чтобы показать что   2n­1   является   простым,   не   каждое   значение   простого   числа   для  n произведет   простое   число   Мерсенна.   Например,   число   М11  заметно отсутствует в списке: М2, М3, М5, М7, М13, М17, М19, … На самом деле, в одном из ранних вычислений мы нашли  М11 = 211– 1=2047=23*89. Получается, что простые числа Мерсенна отбирают только простые числа и делают это выборочно. Было решено пропустить следующие два М23 и М29, перед тем как выбрать М31. Как было упомянуто ранее, если даже Мерсенн предложил что 231­1 является простым, он не смог доказать это. 21 Великий   шведский   математик   Леонард   Эйлер   (1707­1783)   используя разумную   аргументацию   и   экспериментальное   деление,   показал,   что   231­ 1=2147483647 является простым. Последовательно, открытие 8­го простого числа было отнесено Эйлеру. В 1811 году Питер Барлоу прокомментировал простое число 230(231­1) что оно  «величайшее из всех что будет изобретено, если даже они попросту заинтересованы, не будучи полезными, не похоже что кто­либо   попытается   найти   число   помимо   него».   Очевидно,   что   никто   в поздние 1800­е не имел понятия о мощи современных компьютеров. М13 = 223– 1 не является простым. Мы можем подтвердить это с помощью калькулятора. Если даже n является простым числом,  2n­1 может все еще не быть простым. Первый пример, который мы привели это   211­1.  Теперь другой пример, 223­1.  Первое,   рассмотрим   простой   множитель   данного   числа.   Мы   можем выработать его с помощью калькулятора и по таблица простых чисел (<100):  1 11 21 31 41 51 61 71 81 91 2 12 22 32 42 52 62 72 82 92 3 13 23 33 43 53 63 73 83 93 4 14 24 34 44 54 64 74 84 94 5 15 25 35 45 55 65 75 85 95 6 16 26 36 46 56 66 76 86 96 7 17 27 37 47 57 67 77 87 97 8 18 28 38 48 58 68 78 88 98 9 19 29 39 49 59 69 79 89 10 20 30 40 50 60 70 80 90 99 100 Вероятно,   ушло   много   времени,   чтобы   найти   его   простой   множитель. Другой простой множитель достаточно большой:  223– 1=8388607=47*178481 22 8. Как были найдены большие совершенные числа? Большинство из больших совершенных чисел, найденные после Эйлера, были найдены в эпоху компьютеров с помощью электронных компьютерных приборов.   К   1985   году,   в   общей   сложности   были   известны   31   идеальных чисел. К концу 1997 года было открыто 36­е совершенное число: 22976221– 1! Все   известные   совершенные   числа   являются   в   форме   2n­1(2n­1), утвердившиеся   со  времен  Евклида.  Эйлер   показал,  что  нет  других  четных совершенных чисел, исключая тех, которые встречаются в формуле Евклида. Есть ли какие­либо нечетные совершенные числа? Никто не нашел ни одного и никто не сумел доказать что хотя бы одно существует. Все, что мы знаем о нечетных совершенных числах это то, что они должны иметь хотя бы 300 десятичных знаков и множество множителей. Возможно нет ни одного! 9. Некоторые свойства совершенных чисел. Совершенные числа производят ряд интересных качеств, некоторые из которых можно с легкостью наблюдать, но некоторые должны быть изучены поглубже. Одно из довольно интересных качеств это то, что сумма обратных чисел всех   делителей   (включая   само   число)   идеального   числа   это   2.   Например, число 28: Маленькое   наблюдение   может   показаться   немного   удивительным   с первого   взгляда,   но   более   близкое   изучение   показывает,   что   оно   следует напрямую с определения совершенного числа. Другое   наблюдение   это   то,   что   совершенные   числа,   похоже заканчиваются цифрой 6 или 8, но не обязательно, чередуясь цифрами между двумя. Данная таблица может оказать огромную помощь в исследованиях. 23 n 2n­1 2n­1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 2n­1(2n­1) 6 28 120 496 2016 8128 32640 130816 523776 2096128 8386560 33550336 134209536 536854528 2147450880 8589869056 34359607296 137438691328 549755289600 2199022206976 8796090925056 35184367894528 Таблица 5. Теперь   рассмотрим,   почему   последняя   цифра   совершенных   чисел 24 2n­1(2n­1) 6 28 120 496 2016 8128 32640 130816 523776 2096128 8386560 33550336 134209536 536854528 2147450880 8589869056 34359607296 137438691328 549755289600 2199022206976 8796090925056 35184367894528 заканчивается либо цифрой 6, либо 8. n 2n­1 2n­1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 25 Рассмотрим последовательность цифр разряда единиц в 3­х колонах. Последняя цифра совершенного числа заканчивается цифрой 6 или 28. n 2n­1 2n­1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287 1048575 2097151 4194303 8388607 2n­1(2n­1) 6 28 120 496 2016 8128 32640 130816 523776 2096128 8386560 33550336 134209536 536854528 2147450880 8589869056 34359607296 137438691328 549755289600 2199022206976 8796090925056 35184367894528 Дополнительные сведения совершенных чисел:  26 10. Как связаны совершенные числа и треугольные числа? 1 3 6 10 15 21 28 36 … Рассмотрим   другое   свойство   совершенных   чисел.   Взгляните   на последовательность треугольных чисел показанных в таблице 5. Совершенные числа 6 и 28 оказываются в последовательности, таким образом, они тоже треугольные   числа.   Являются   ли   другие   совершенные   числа   также треугольными? Для ответа на этот вопрос рассмотрим нижеследующее: Обобщение: n­е треугольное число через ∆n .  ∆n =1+2+3+4+...+n=n(n+1)/2 Эйлер нашел 8­е совершенное число: 230(231­1). Мы можем переписать это значение как:  Теперь, мы можем увидеть почему оно (231­1)­е треугольное число! Совершенные   числа   6,   28,   496   и   8128   являются   3­м,   7­м,   31­м   и  k треугольным числом соответственно. Давайте найдем значение k (k=127). Следующая   таблица   показывает   один   метод   вычисления   значений   для первых 4­х совершенных чисел.  Идеальное число М(М+1)/2 6 28 496 = = = 27 М 3 7 31 8128 33550336 = = 127 8191 11. Каждое четное совершенное число является треугольным числом Все   ли   совершенные   числа   шестиугольные?   Также   как   и   треугольные числа, шестиугольные числа могут быть отображены визуально, как показано на рисунке внизу. 6 1 Изучим связь между шестиугольными числами и совершенными числами, 15 28 45 с проекции этих шестиугольных чисел мы пришли к выводу, что совершенные числа являются шестиугольными. Какое самое большое известное простое число? 22976221– 1! Это   36­е   простое   Мерсенна   и   оно   является   самым   большим   простым числом известным до нашего времени. 21398269– 1! Новое простое число, 21398269–1 является 35­м известным простым числом 28 Мерсенна,   оно   состоит   из   420,921  цифр.   С   теоремы   Евклида­Эйлера,   мы знаем, что 35­е совершенное число это 21398268(21398269– 1). Это число состоит из 841,842 цифр! Существует около 30 уже раскрытых Совершенных чисел! 12. Олимпиадные задачи с совершенными числами. Задача№1 Найдите все совершенные числа от 1 до 1000 и выведите их на экран. Подсказка: вам  необходимо найти все делители от 1 до исследуемого числа. Делителем числа называется  число, которое делит данное без остатка (a mod b=0). Алгоритм решения задачи:  1. Каждое число от 1 до 1000 поочередно делить на все целые числа от 1 до этого  числа. Все найденные делители помещать в массив. 2. Найти сумму всех делителей и сравнить с самим числом. Если сумма и число равны, то последнее является совершенным. Программа на языке Паскаль:  const N = 1000; var     i,d,j,k,sum: integer;     dv: array[1..N] of integer; begin     for i:=2 to N do begin         //write(i,': ');         d := 1;         j := 1;         while d < i do begin             if i mod d = 0 then begin                 dv[j] := d;                 j := j+1;                 //write(d,',');             end;             d := d + 1;         end;         sum := 0;         for k:=1 to j­1 do             sum := sum + dv[k];         if sum = i then             writeln(i,' ­ perfect!');        //writeln;     end;   readln; end. Задача №2.  29 Найдите все совершенные числа из диапазона [a, b]. Если таких чисел нет, программа должна выдать соответствующее сообщение. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 program nname; uses Crt; var k,i,a,b,sum:longint; f:Boolean; begin f:=False; ClrScr; Write('a='); Readln(a); Write('b='); Readln(b); for i:=a to b do  begin sum:=0; for k:=1 to i div 2 do  if i mod k=0 then sum:=sum+k; if sum=i then begin if f=False then Writeln('Найдены совершенные числа на отрезке [a;b]:'); f:=True; Write(i,' '); end; end; if f=False then Writeln('Совершенных чисел на отрезке [a;b] не найдено!')  else Writeln; Readln; end. Задача№ 3. Дано натуральное число n. Получить все совершенные числа, меньшие n. Число называется  совершенным, если оно равно сумме всех своих делителей, кроме себя самого. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 uses crt; var i,s:integer;     n,x: longint; begin  clrscr;  write('n: ');  readln(n);  for i:=1 to n do   begin    s:=0;    x:=1;    while x<>i do     begin      if i mod x = 0 then       s:=s+x;      inc(x);     end;    if s=x then    write(x,' ');   end;  readln; end. 30 Задача № 4. Проверить, является ли заданное натуральное число простым Формулировка. Дано натуральное число. Проверить, является ли оно простым.  Примечание: простым называется натуральное число, которое имеет ровно два различных  натуральных делителя: единицу и само это число. Решение. Задача отличается от предыдущей только тем, что вместо вывода на экран числа  делителей, содержащегося в переменной count, необходимо выполнить проверку равенства счетчика числу 2. Если у числа найдено всего два делителя, то оно простое и нужно  вывести положительный ответ, в противном случае – отрицательный ответ. А проверку  через условный оператор, как мы уже знаем, можно заменить на вывод результата самого  булевского выражения с помощью оператора write (writeln). Код: 1. program PrimeTest; 2. 3. var 4.   i, n, count: word; 5. 6. begin 7.   readln(n); 8.   count := 0; 9.   for i := 1 to n do begin 10.     if n mod i = 0 then inc(count) 11.   end; 12.   writeln(count = 2) 13. end. Задача № 5. Проверить, является ли заданное натуральное число  совершенным Формулировка. Дано натуральное число. Проверить, является ли оно совершенным. Примечание: совершенным числом называется натуральное число, равное сумме всех своих собственных делителей (то есть натуральных делителей, отличных от самого числа).  Например, 6 – совершенное число, оно имеет три собственных делителя: 1, 2, 3, и их сумма  равна 1 + 2 + 3 = 6. Решение. Эта задача напоминает задачу 17, в которой нужно было найти количество всех  натуральных делителей заданного числа. Напомним код ее основной части (назовем его  кодом 1): count := 0; for i := 1 to n do begin   if n mod i = 0 then inc(count) end; Как видно, в этом цикле проверяется делимость числа n на все числа от 1 до n, причем при  каждом выполнении условия делимости увеличивается на 1 значение счетчика count с  помощью функции inc. Чтобы переделать этот код под текущую задачу, нужно вместо  инкрементации (увеличения значения) переменной­счетчика прибавлять числовые значения самих делителей к некоторой переменной для хранения суммы (обычно ее мнемонически  называют sum, что в пер. с англ. означает «сумма»). В связи с этим оператор   if n mod i = 0 then inc(count); в коде 1 теперь уже будет выглядеть так: 31 if n mod i = 0 then sum := sum + i; Кроме того, чтобы не учитывалось само число n при суммировании его делителей  (насколько мы помним, этот делитель не учитывается в рамках определения совершенного  числа), цикл должен продолжаться не до n, а до n – 1. Правда, если говорить точнее, то  цикл следовало бы проводить до n div 2 (также это обсуждалось в задаче 15), так как  любое число n не может иметь больших делителей, иначе частное от деления должно быть  несуществующим натуральным число между 1 и 2. Единственное, что останется теперь сделать – это вывести ответ, сравнив число n с суммой его делителей sum как результат булевского выражения через writeln:   writeln(n = sum); Код: program PerfectNumbers; var   i, n, sum: word; begin   readln(n);   sum := 0;   for i := 1 to n div 2 do begin if n mod i = 0 then sum := sum + i   end;   writeln(n = sum) end. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 13. Некоторые нерешенные задачи по теории чисел. №   1.   Существует   ли   хотя   бы   одно   четное   число,   большее   2,   не являющееся суммою двух простых чисел (Гольдбах, Эйлер)? №   2.   Существует   ли   среди   чисел   бесконечное множество простых чисел? 2 n 1 ,   где   n   ­   натуральное, №   3.   Существует   ли   бесконечное   множество   простых   чисел  p,   для которых  2 p 1  ­ составное число (числа Мерсенна)? № 4. Если число  2 n 1  ­ простое, то будет ли и число  22 n 1  ­ простым (числа Ферма)? № 5. Существует ли бесконечное множество простых чисел, которые (в десятичной системе счисления) имеют все цифры, равные 1? №   6.   Имеется   ли   среди   чисел   ,   где   n   ­   натуральное   число, бесконечное множество простых чисел (легко доказать, что среди этих чисел – бесконечное множество составных чисел)? 1!n №   7.   Существует   ли   хотя   бы   одно   четное   число,   не   являющееся разностью двух простых чисел? №   8.   Существует   ли   бесконечное   множество   пар   простых   чисел­ близнецов? 32 № 9. Существует ли как угодно длинные арифметические прогрессии, образованные только из различных, простых чисел? № 10. Существует ли хотя бы одно нечетное число  n  такое, что сумма всех его делителей равна  n2  (совершенные числа)? 33 Программа Совершенных чисел (Исходная Программа) include #include #include using namespace std; int main() { char cont = 'y' double counter = 2, i=0, pnumber = 1; while (cont =='y' || cont == 'Y') { if (counter == 11 || counter ==23){ counter = counter + 1; pnumber = 1; continue; } for (I = 2; I <= (counter / 2); i++) { if ((counter /i)n== floor(counter / I)) { pnumber = pnumber + I; } } if (pnumber == 1) { count<< “\n\tPERFECT NUMBER......” <<((pow(2,   (counter   –   1)))   *   (pow(2,   counter)   – 1));//(pow(2,counter) – 1); cout << “\n\n\n\tCONTINUE.....[Y/N]”;//Beep cin >> cont; cout << “\n\tsearching.....\n”; } counter = counter + 1; pnumber = 1; }//End of While Loop 34 } // End of Main 35 Программа Совершенных Чисел (Алгоритм / псевдокод) Include ''input output stream'' Library in the software Include ''console input output'' Library in the software Include ''mathematics'' Library in the software Declare main body of the software { Declare and initialize character type variables Declare and initialize numeric type variables Loop to keep user in the software environment until he chooses ''n/N'' to exit { Loop to keep natural number increasing by the increment of ''1'' { Authenticating/verifying Perfect number { Flagging to remember, a perfect number is located/searched/found } } Checking status of ''Flag' { After verification from ''Flag' that number was perfect number, user will informed by displaying that perfect number Ask user, whether he want to continue with the searching of next Perfect Number Continue searching with for the next Perfect Number } Increasing the  natural number by the increment of 1 Re­Initializing a numeric variable back to 1 } }//End of Main body of software Некоторые образцы вывода данных с программы 36 3. •   // Меньшиков. Тренировка 4. Условие задачи? •   // 4A. Совершенные числа [perfect] •   // ibelyaev: 05Mar2010 •   #include  •   #include  •     •   using namespace std; •     •   bool isPerfect(int n) •   { •       if (n==1) return false; •       int sum = 1; •       int len = sqrt((double)n); •       for (int i=2;i<=len;i++) •       { •           if (n%i==0) •           { •               sum+=i;  •               if (n/i != i) •                   sum+=n/i;    •           } •       } •       return n == sum; •   } •   int main() •   { •       int a,b; •       cin>>a>>b; •       bool isExist = false; •       for (int i=a;i<=b;i++) •           if (isPerfect(i)) •           { •               printf("%i\n",i); •               isExist = true; •           } •       if (!isExist) •           cout<<"Absent"; •       return 0; 37 Заключение Из   огромного   многообразия   натуральных   чисел   ученые   выделили совершенные числа, обладающие рядом очень интересных свойств. Анализируя   научно­популярную   литературу   о   простых,   совершенных числах,   можно   убедиться,   что   формулы   общего   вида   для   нахождения простых,     совершенных   чисел   не   существует?   Вопрос   о   существовании: бесконечности   множества   четных   совершенных   чисел,   нечетного совершенного числа открыт до сих пор.   Нами   проведены   исследования   классификации   свойств   простых   и совершенных   чисел.   Рассмотрены   некоторые   закономерности   совершенных чисел. В   работе   изучена   связь   между   совершенными   числами   и   формулой Мерсенна. Проект также включает в себя рассмотрение способов и случаев использования формулы Мерсенна. Мы определили свойства построения алгоритма, который поможет нам определить является ли число совершенным или нет, а также выдвинуть его некоторые свойства. До настоящего времени нет ответов на два важных вопроса:  1) Существует ли наибольшее чётное совершенное число?  2) Существует ли нечетное совершенное число? До сегодняшнего дня не обнаружено ни одного нечетного совершенного числа, хотя и не доказано, что такого числа не существует.  38 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. История математики в школе. Пособие для учителей /Г.И.Гейзер. – М.:         Просвещение, 1981. 2. Живая математика. Математические рассказы и головоломки /Я.И.      Перельман. ­ М: Триада – литера, 1994. 3. «Специальные числа натурального ряда».­Е.И.Деза, 2011 год. 4. «Math world» (http://mathworld.wolfram.com/MersenneNumber.html) 5. «Британская энциклопедия»  (http://mathworld.wolfram.com/MersenneNumber.html) 6. Главная редакция физико­математической литературы (Москва «НАУКА», 1980 год) 39 40