исследовательская работа по математике "Решето Эратосфена"

Районная научно-практическая конференция школьников

«Перекрёстки открытий»

Секция МАТЕМАТИКА

 «Решето Эратосфена»

Автор: Миллер Елизавета, 12 лет

     МАОУ СОШ № 3 г. Черепаново, 6 «В» класс

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

Учитель математики, высшая категория

г. Черепаново 2019

Содержание

                                                                                                                      Стр.

Введение………………………………………………………….……….…3

Глава1 Из истории простых чисел..……………..……….………..…….....5

Глава 2 Методы нахождения простых чисел……………………….…….9

Глава 3 Исследование метода «Решето Эратосфена»и макета решета... 11

Заключение…………………………………………...………………….....14

Список литературы………………………………………………………...16

Использованное оборудование

Приложение 1 Портреты ученых

Приложение 2 Обратная сторона макета

Приложение 3 Опрос

Введение        

«Среди чисел существует такое совершенство и согласие, что нам надо размышлять дни и ночи над их удивительной закономерностью…».

Стевин

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

Алгоритм нахождения простых чисел прост, но в тоже время простые числа следует одно за другим по закону, который еще не найден.

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

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

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

Считаю её актуальной по нескольким причинам:

- загадки простых чисел всегда волнуют математиков;

-  мне не удалось найти похожих работ, т.е. макетов «Решета Эратосфена»;

-  в настоящее время этот способ компьютеризирован, а  ручная работа (собственные размышления и вычисления) приносит, гораздо больше пользы;

- знание алгоритма простых чисел будет очень полезно на экзаменах.

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

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

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

Объект исследования: Простые числа

Предмет исследования: метод нахождения простых чисел «Решето Эратосфена», макет решета.

Цель: Изучение закономерностей  расположения простых чисел полученных методом «Решето Эратосфена» и наглядная демонстрация решета.

Задачи:

- осуществить анализ литературных данных по теме исследования;

- познакомиться с различными методами нахождения простых чисел;

- научиться применять метод «Решето Эратосфена» для нахождения простых чисел;

- приготовить наглядную демонстрацию метода «Решето Эратосфена».

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

Методы: наблюдение, сравнение, анализ, опрос

В своей работе я использовала такие источники информации как учебник математики  6 класса, книги о числах и об истории математики, электронные ресурсы сети интернет.

Глава1 Из истории простых чисел

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

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

Не одну тысячу лет к ним приковано внимание математиков – их вновь и вновь ищут, исследуют, находят им применение. Евклид и Эратосфен, Эйлер и Гаусс, Рамануджан и Харди, Чебышёв и Виноградов... Этот перечень выдающихся учёных занимавшихся простыми числами и задачами с ними связанными можно продолжать и продолжать.

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

 (Часть его доказательства) Евклид строит числа

2 · 3 + 1 = 7;

2 · 3 · 5 + 1 = 31;

2 · 3 · 5 · 7 + 1 = 311;

2 · 3 · 5 · 7 · 11 + 1 = 2311;

2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 и т.д.,

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

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

Было найдено много других доказательств бесконечности простых чисел. Доказательство Эйлера (1737г.) носило особый характер. Оно оказалось тем семенем из которого позже выросли многие достижения. ».  [2, на 99 стр.]

Другой  греческий математик того же времени — Эратосфен изобрел способ, посредством которого можно найти все простые числа от 1 до некоторого определенного числа. Этот способ называется  «решетом Эратосфена».  [1, на 72 стр.] . Именно исследование данного способа и применение его на практике будет описано мной в третьей главе.

К задачам многовековой давности относится и проблема  «чисел-близнецов». Два простых числа называются близнецами, если их  разность равна 2.   П р и м е р ы: 3 и 5, 5 и 7, 41 и 43, 101 и 103.

Числа-близнецы можно находить способом, аналогичным  «решету Эратосфена». В 1952 г. В. А. Голубев, учитель математики из г. Кувшиново (Калининской области), имеющий немало заслуг в решении трудных задач теории чисел, вывел формулу для функции П2 — числа пар близнецов от 1 до х. В 1959 г. была опубликована таблица, составленная с  помощью вычислительной электронной машины, содержащая, более 8000 пар близнецов в пределах до 1 100000. Ныне известна даже такая пара больших чисел-близнецов, второе из которых равно 1 000000009651. Однако до сих пор  неизвестно, существует ли бесконечное множество пар близнецов. Эта задача теории целых чисел, еще ждет своего решения ...   [1, на 136 стр.]

Еще одна задача, вязанная с простыми числами не решена:

- Существует ли арифметическая прогрессия последовательных простых чисел для любой (конечной) длины? Например, последовательность простых чисел 251, 257, 263, 269, имеет длину 4. Самая большая такая последовательность, которая известна, имеет длину 10.  

Есть еще ряд задач, но для учащегося 6 класса они сложны для понимания.

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

Наибольшее известное простое число (найдено GIMPS [Great Internet Mersenne Prime Search широкомасштабный проект добровольных вычислений по поиску простых чисел Мерсенна.]  282 589 933 − 1. Оно было открыто Патриком Ларошем в рамках проекта GIMPS 7 декабря 2018 года и содержит 24 862 048 десятичных цифр. Более того, четырнадцать предыдущих рекордов также были установлены участниками GIMPS. Многие учёные-математики, а также любители, занимаются поиском рекордных по величине простых чисел, за нахождение которых организацией Electronic Frontier Foundation было предложено несколько наград в зависимости от величины числа. Так, в 2009 году была вручена премия в 100 000 долларов США, назначенная сообществом Electronic Frontier Foundation за нахождение простого числа, десятичная запись которого содержит не менее 10 миллионов цифр

Наибольшими известными простыми-близнецами являются числа  Они были найдены в сентябре 2016 года в рамках проекта добровольных вычислений PrimeGrid.

Об Эратофене

Эратосфен Сын Эглаоса, уроженец Кирены (один из величайших городов античности, город, посвящённый Аполлону, стоял на территории современной Ливии).

Начальное образование Эратосфен получил в Александрии под руководством своего учёного земляка Каллимаха. Другим учителем Эратосфена в Александрии был философ Лизний. Перебравшись затем в Афины, он так тесно сблизился со школой Платона, что обыкновенно называл себя платоником. Результатом изучения наук в этих двух центрах была энциклопедическая эрудиция Эратосфена; кроме сочинений по математическим наукам, он писал ещё трактаты «о добре и зле», о комедии и др. Из всех своих сочинений Эратосфен придавал особенное значение литературным и грамматическим, как это можно заключить из того, что он любил называть себя филологом. Царь Птолемей III Эвергет после смерти Каллимаха вызвал Эратосфена из Афин и поручил ему заведование Александрийской библиотекой. Удалённый в старости от этой должности, Эратосфен впал в крайнюю нищету и, страдая болезнью глаз или даже совсем ослепнув, уморил себя голодом.

Эратосфен заложил основы математической географии, вычислив с большой точностью величину земного шара, изобрел Широту и Долготу, а так же придумал високосный день.

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

В честь Эратосфена назван кратер на  Луне.

Глава 2 Методы нахождения простых чисел

После Евклида и Эратосфена  многие другие ученые разных стран и  времен стремились глубже познать   природу простых чисел. Особенно хотелось найти такую формулу, которая  позволяла бы быстро узнать, сколько простых чисел имеется между 1 и любым натурального ряда. Лишь в XIX в., около 2200 лет после Евклида, великий русский  математик Пафнутий Львович Чебышев открыл формулу 1,  позволяющую приближенно подсчитать простые числа на любом участке натурального ряда. Начиная со второй половины XX в. для поисков больших простых чисел применяются электронные счетные машины. С их помощью доказана простота таких  числовых гигантов, как:

Решето Эйлера

Решето Эйлера это вариант решета Эратосфена, в котором каждое составное число удаляется из списка только один раз.

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

Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после k-го этапа рабочий список содержит только числа взаимно простые с первыми k простыми числами (то есть числа не кратные ни одному из первых k простых чисел), и начинается с (k+1)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.

Решето только по нечётным числам

Поскольку все чётные числа, кроме 2, — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами. Во-первых, это позволит вдвое сократить объём требуемой памяти. Во-вторых, это уменьшит количество выполняемых алгоритмом операций (примерно вдвое).

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

Кроме Решета Эратофена, наглядное расположение простых чисел предложил Станислав Мартин Улам- Метод «Скатерти Станислава Улама».  Он начертил на на бумажной столовой салфетке вертикальные и горизонтальные линии и хотел заняться составлением шахматных этюдов, но потом передумал и начал нумеровать пересечения, поставив в центре 1, и, двигаясь по спирали против часовой стрелки, записывал все натуральные числа до 100. Без всякой задней мысли Улам обводил все простые числа кружками. Каково было его удивление, когда он увидел, что простые числа стали выстраиваться вдоль прямых линий!

Замечено было ещё одно интересное явление, тоже имеющее отношение к вопросу выявления простых чисел. Его суть в том, что если начинать спиральную запись из центра не с цифры «1», а любой другой, то эффект останется неизменным: простые числа будут располагаться по диагоналям. Почему? Неизвестно…

Возможно, моё следующее исследование будет связано с этим способом расположения простых чисел….

Глава 3 Исследование метода «Решето Эратосфена»

В книге История математики в школе∶ ΙV-VI кл. стр. 73 описан способ следующим образом. Пусть, например, требуется найти все простые числа между 1 и 50. Выписываем все числа от 1 до 50:

Зачеркиваем единицу, которая не является ни простым, ни  составным числом, затем подчеркиваем число 2 и зачеркиваем все числа, кратные двум, т. е. все числа таблицы, «через одно»,  начиная с 2. Далее подчеркиваем из не зачёркнутых чисел 3 и  зачеркиваем все числа, кратные трем, т. е. «через два» и т. д. Оказывается, что между 1 и 50 имеются следующие 15 простых 2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47.Этим способом в  

настоящее время составлены таблицы простых чисел между 1 и 12 000 000. Для получения таблицы простых чисел Эратосфен, писавший на  натянутом папирусе, не зачеркивал, а  прокалывал составные числа. Отсюда  название «решето Эратосфена»; оно  

отсеивает простые числа.

В других источниках информации [2, на стр 105. ] удалось найти следующее описание способа «Решето Эратосфена».  В своей «Арифметике», опубликованной около 100 г до н.э., Никомах из Герасы вводит решето Эратосфена следующим образом: «Метод для получения этих простых чисел называется по Эратосфену решетом, так как мы берем все нечетные числа, смешанные беспорядочно вместе, и выбрасывая из них, как неким инструментом, или решетом, мы отделяем в первую очередь неразложимые, а во вторую составные посредством их самих ».

Я пришла к выводу, что если вручную применять способ решето Эратосфена, то следует рассматривать только нечетные числа и 2, так можно охватить большее количество чисел и ускорить алгоритм.  Моя работа началась с выписывания нечетных чисел на макете, на котором можно просверливать отверстия. Для более наглядной картины расположения простых чисел решила просверливать не составные числа (как это делал Эратосфен), а простые.  Мой макет содержит числа нечетные и  число 2 начиная  с 2 до 449. В ряду записано по 15 чисел, рядов – 15.

Я вычеркивала по методу Эратосфена составные числа, простые отсеялись. Все клеточки с не зачёркнутыми числами папа просверлил. Получилось 87 отверстий, т.е. простых чисел.

Было замечено, что вычеркнутые числа, кратные трем, девяти и пяти располагаются строго по столбцам. По столбцам числа оканчиваются одной и той же цифрой 1, 3,5,7,9 и так 3 раза. (только первый столбец начинается числом 2). Это видимо, связано с количеством чисел по вертикале.  

  Затем я изучала расположение отверстий решета т.е. расположение простых чисел на макете и заметила:

-расположение простых чисел неравномерно; посчитала количество отверстий в рядах,  сверху вниз получилось 10, 7,7,6,5,6,5,6,5,5,4,6,5,4,6.

- в расположении отверстий усматривается вертикальный рисунок ( приложение 2 фото № 1);

- наибольшая плотность расположения в центральных столбцах. Второй и третий столбец без отверстий и 13,14 столбец (только в начале по одному отверстию) практически без отверстий.

- простых чисел, оканчивающихся тройкой оказалось наибольшее количество (23шт), оканчивающихся 1, 7,9  -20 шт., 5 и 2- по 1 шт.

- по расположению отверстий на обратной стороне замечено подчинение некоторым видам движения ( симметричное расположение  (фото № 1); параллельный перенос (фото № 1, № 2);  поворот (фото №2))

- взглянув на решето с обратной стороны, мне пришла в голову идея сравнить его со звездным небом, с помощью карт созвездий. И действительно, мне удалось найти несколько созвездий: малая медведица, цирей, рак. (Фото№ 3 в приложении 2).

В главе № 2 была представлена формула Чебышева, с помощью которой можно найти количество простых чисел, не превосходящих числа х. С помощью мамы я произвела расчёты: данная функция говорит, что в моём интервале должно быть чисел в границе от   68 до 78, но подсчеты вручную дали результат 87 шт. Выяснить причину расхождения мне не удалось возможно, в силу недостаточности знаний математики.

Заключение

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

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

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

Выводы:

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

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

Я поняла, тема простых чисел, алгоритмов и методов нахождения простых чисел настолько велика, что в рамках одного исследования, и обладая знаниями математики ученика 6 класса, её невозможно описать. Простые числа на самом деле совсем не просты! Вроде бы в Решете Эратосфена нет никаких случайностей и должна получаться точная и легко записываемая формулой последовательность. Но — как ни странно — ничего подобного: формулы нет! Сколько веков уже искали!   В это настолько не верится, что и сегодня начинают искать несуществующую формулу. Но эти поиски не заканчиваются успехом... Может быть, повезёт тем,  кто живет в наше время?

Список литературы

1. Глейзер Г.И.История математики в школе∶ ΙV-VI кл. Пособие для учителей.-М.:Просвещение,1981.-239 с
2. С.Коутинхо. Введение в теорию чисел. Алгоритм RSA. Москва: Постмаркет, 2001. - 328 с
3. Математика. 6 класс : учеб. Для общеобразоват. Учреждений / [Виленкин Н.Я.]. –М.: Мнемозина, 2009.
4.  Математика для школы [Электронный ресурс]: Бесконечность ряда простых чисел - Электрон. данные.-Режим доступа: http://math4school.ru/beskonechnost_rjada_prostih_chisel.html/  (12.0.2018)
5. Математика для школьников и студентов, обучение и образование [Электронный ресурс]: Простые числа. Статья  J.J. O’Connor, E.F. Robertson, Prime numbers. Перевод статьи http://www-history.mcs.st-and.ac.uk/HistTopics/Prime_numbers.html.- Электрон. данные.-Режим доступа: http://hijos.ru/2010/12/15/prostye-chisla/ (11.01.2018)
6. Грасиан Энрике  Простые числа [Долгая дорога к бесконечности] https://math.wikireading.ru/16

Использованное оборудование

Компьютер, карта звездного неба, фанера или пластик размером от 50см* 50см, дрель.

Приложение 1

Портреты ученых

 Евклид (около 325 г. до н. э. - до 265 г. до н. э.)— древнегреческий математик, автор первого из дошедших до нас теоретических трактатов по математике.

Эратосфен (        276 г. до н. э. Кирена-196 г. до н.э. Александрия ) — греческий математик, астроном, географ, филолог и поэт. Ученик Каллимаха, с 235 г. до н. э. — глава Александрийской библиотеки. Первый известный учёный, вычисливший размеры Земли.

Леона́рд Э́йлер (1707, Базель, Швейцария —  1783, Санкт-Петербург, Российская империя) — швейцарский, немецкий и российский математик и механик, внёсший фундаментальный вклад в развитие этих наук (а также физики, астрономии и ряда прикладных наук). Глубоко изучал медицину, химию, ботанику, воздухоплавание, теорию музыки, множество европейских и древних языков.

Иога́нн Карл Фри́дрих Га́усс ( 1777, Брауншвейг —1855, Гёттинген) — немецкий математик, механик, физик, астроном и геодезист. Считается одним из величайших математиков всех времён, «королём математиков».

Пафнутий Львович Чебышев. (1821 г.  Калужская губерния —1894, Санкт-Петербург) — русский математик и механик, основоположник петербургской математической школы, академик Петербургской академии наук (с 1859 года) и ещё 24 академий мира.

Виноградов Иван Матвеевич ( 1891 г. с. Милолюб Псковская область- 1983г. Москва). Работы «Новый метод аналитической теории чисел». «Основы теории чисел». «Метод тригонометрических сумм в теории чисел». «Метод тригонометрических сумм в простейших вариантах». С 1932 директор Математического института имени В. А. Стеклова.

Станислав Мартин Улам (13 апреля, 1909, Львов —13 мая, 1984, Санта-Фе) — выдающийся польский математик, участвовавший в создании американской водородной бомбы в рамках ядерного проекта Лос-Аламосской лаборатории, также внёс большой вклад в развитие некоторых математических методов.

Приложение 2 Решето с обратной стороны.

 Фото № 1

 Фото № 2

Фото № 3

Красным цветом- Цирей, созвездие северного полушария

Желтым цветом- Малая Медведица, созвездие северного полушария

Зелёным цветом- Рак, созвездие северного полушария

Приложение 3

Опрос среди учащихся 6 В класса с демонстрацией макета.

В опросе приняли участие 19 человек.

Вопросы.

1. Знаете ли вы, какие числа называют простыми?
2. Запишите самое маленькое простое число.
3. Известен ли вам алгоритм нахождения простых чисел.
4. Как вы считаете, если ли закономерность в расположении простых чисел?
5. Можно ли на моём макете увидеть созвездия, подобно звёздному небу?
6. Знаете ли вы что простые числа лежат в основе кодов?

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