Сохрани и опубликуйсвоё исследование
О проекте | Cоглашение | Партнёры
Выпускная квалификационная работа 01.03.02 Прикладная математика и информатика
Источник: Белгородский государственный университет - национальный исследовательский университет (НИУ «БелГУ»)
Комментировать 0
Рецензировать 0
Скачать - 2,2 МБ
Enter the password to open this PDF file:
-
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ» ( Н И У « Б е л Г У » ) ИНСТИТУТ ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ И ЕСТЕСТВЕННЫХ НАУК Кафедра общей математики Проблема Гольдбаха при фиксированном и растущем параметрах Выпускная квалификационная работа студента очной формы обучения направления подготовки 01.03.02 «Прикладная математика и информатика» 4 курса группы 07001206 Межакова Александра Викторовича Научный руководитель: доцент кафедры общей математики, кандидат ф.-м. наук Шевцова М. В. БЕЛГОРОД 2016
2 ОГЛАВЛЕНИЕ Введение………………………………………………………………………. 3 1 Понятие простых и составных чисел …………………………................... 5 1.1 Роль простых чисел в математике………………………………………. 5 1.2 Примеры аддитивных задач……………………………………………... 10 2 Проблемы Гольдбаха………….………………..…………………………… 13 2.1 Тернарная проблема К. Гольдбаха…..…………………………………... 13 2.2 Бинарная проблема К. Гольдбаха ………………………………………... 14 2.3 Метод Харди-Литтлвуда………………………………………………..... 16 2.4 Метод Виноградова………………………………………………………. 19 3 Программная реализация и проверка ее работоспособности ................... 21 3.1 Описание основных функций программы и еѐ реализация …………... 21 3.2 Проверка работоспособности программы…...…………………………. 28 Заключение…………………………………………………………………….. 29 Список использованной литературы…………………...……………………. 30 Приложение А……………………………………………………………….. 32 Приложение Б……………………………………………………………….. 35 2
3 ВВЕДЕНИЕ Проблема Кристиана Гольдбаха (проблема Леонарда Эйлера, бинарная проблема К. Гольдбаха) – утверждение о том, что любое чѐтное число, начиная с 4, можно представить в виде суммы двух простых чисел. Одна из самых известных открытых математических проблем; в совокупности с гипотезой Георга Фридриха Бернхарда Римана включена под номером 8 в список проблем Кристиана Давида Гильберта (1900 г.) и является одной из немногих проблем К. Д. Гильберта, до сих пор остающихся нерешѐнными. Более слабый вариант гипотезы – тернарная проблема К. Гольдбаха, согласно которой любое нечѐтное число, начиная с 7, можно представить в виде суммы трѐх простых чисел, это утверждение доказано в 1937 году советским математиком Иваном Матвеевичем Виноградовым.. Из справедливости утверждения бинарной проблемы К. Гольдбаха следует справедливость тернарной проблемы К. Гольдбаха: если каждое чѐтное число, начиная с 4, есть сумма двух простых чисел, то добавляя 3 к каждому чѐтному числу, можно получить все нечѐтные числа, начиная с 7. Актуальность темы обусловлена тем, что если основные параметры проблем Гольдбаха не фиксировать, то такая задача решена лишь для тернарной проблемы. А для ограниченных параметров можно решить обе задачи при помощи компьютера. Цель работы – рассмотреть тернарную и бинарную проблемы К. Гольдбаха, изучить методы решения этих проблем и составить программу, реализующую их. Задачи: • изучить понятие простых и составных чисел, роль простых чисел в математике, примеры аддитивных задач; • познакомиться с тернарной и бинарной проблемой К. Гольдбаха, методами Харди-Литтлвуда и И. М. Виноградова; 3
4 • составить компьютерную программу для проблем К. Гольдбаха и проверить ее работоспособность. Структура и объем работы: выпускная квалификационная работа выполнена на страницах машинописного текста. Состоит из введения, трех глав, заключения и приложения. В первой главе описывается понятие простых и составных чисел; роль простых чисел в математике, примеры аддитивных задач. Во второй главе рассматриваются тернарная и бинарная проблема К. Гольдбаха, методы Харди-Литтлвуда и И. М. Виноградова. В третьей главе описываются основные функции программы, проверяется работоспособность разработанного алгоритма. В заключении, по итогам проделанной работы, сформулированы выводы. В приложении представлен листинг программы. 4
5 1 Понятие простых и составных чисел Простое число – это натуральное число, которое имеет только два делителя (единицу и само это число). Составное число – это натуральное число, которое имеет более двух делителей. Число 1 имеет только один делитель: само это число. Поэтому его не относят ни к составным, ни к простым числам. Всякое составное число можно разложить на простые множители. При любом способе получается одно и то же разложение, если не учитывать порядка записи множителей. Например: 540 = 2 • 2 • 3 • 3 • 3 • 5. 1.1 Роль простых чисел в математике Простые числа с давних времен привлекают внимание математиков. Первую известную нам таблицу простых чисел составил итальянский математик Пьетро Антонио Катальди в 1603 г. Она захватывала все простые числа от 2 до 743. В 1750 г. Л. Эйлер установил, что число 231 - 1 является простым. Оно оставалось самым большим из известных простых чисел более ста лет. В 1770 г. Немецкий математик Иоганн Генрих Ламберт опубликовал таблицу наименьших делителей всех чисел, не превосходящих 102000 и не делящихся на 2, 3, 5. Вложив в этот труд большие усилия, И. Г. Ламберт гарантировал бессмертие тому, кто доведет таблицу делителей до миллиона. На его призыв откликнулись многие вычислители. К середине 19 века уже были составлены таблицы наименьших делителей не только первого миллиона, но и следующих, вплоть до 9. В это же время в прессе появились сообщения, которые 5 представлялись абсолютно
6 фантастическими: в Венскую академию поступило 7 больших томов рукописных таблиц «Великий канон делителей всех чисел, которые не делятся на 2, 3 и 5, и простых чисел между ними до 100330201». Автором этого труда был Якуб Филипп Кулик, профессор высшей математики Пражского университета. В дальнейшем поиски простых чисел уже не носили характера массовой охоты, с которой можно сравнить составление таблиц, а превратились в целенаправленный отбор отдельных представителей. У охотников за числами популярны простые числа французского ученого Марена Мерсенна – числа вида Mn = 2n-1, где n — натуральное число. Числа такого вида замечательны, в том числе тем, что некоторые из них являются простыми числами. Некоторые представления о распределения простых чисел имели уже древние греки. Из доказательства Евклида следует, например, что они не собраны вместе, а разбросаны по всей числовой оси. В 1845 г. французский математик Жозеф Луи Франсуа Бертран, исследуя таблицу простых чисел в промежутке от 1 до 6000000, обнаружил, что между числами n и 2•n – 2, где n > 3, содержится одно простое число. Это свойство получило название постулата Ж. Л. Ф. Бертрана, хотя ему обосновать его так и не удалось. Доказал постулат в 1852 г. русский математик Пафнутий Львович Чебышев. Из результата П. Л. Чебышева следовала и более точная оценка. Таким образом, даже среди очень больших чисел простые числа не так уж редки. С другой стороны, существуют промежутки, включающие тысячи, миллионы, миллиарды и вообще какое угодно большое количество подряд стоящих натуральных чисел, среди которых нельзя найти ни одного простого. Более двух тысяч лет назад великий древнегреческий математик Евклид доказал, что ряд простых чисел бесконечен. Простые числа следуют одно за 6
7 другим по закону, который еще не найден. Числа то исчезают из натурального ряда, то появляются в нем часто, иногда по соседству: 11, 13, 5971847, 5971849. Профессор Иван Козьмич Андронов в книге «Арифметика натуральных чисел» приводит рассказ о воображаемом путешествии по бесконечной дороге простых чисел: «Мысленно возьмем прямолинейный провод, выходящий из классной комнаты в мировое пространство, пробивающий земную атмосферу, уходящий туда, где Луна совершает вращение, и далее за огненный шар Солнце, в мировую бесконечность. Мысленно подвесим на провод через каждый метр электрические лампочки, нумеруя их, начиная с ближней: 1,2,3,…,1 000,…,1 000 000,…, включим ток с таким расчетом, чтобы загорелись все лампочки с простыми номерами, и полетим вблизи провода». Дальше автор пишет «Мы начинаем движение с первой электрической лампочки, которая не осветила нам старта; она не горит, так как ее номер (единица) не является простым числом. Сразу за ней две лампочки с номерами 2 и 3 включены, эти числа простые. Оставим позади горящие лампочки 5 и 7. Они пронумерованы простыми числами. На нашем длинном пути очень редко будут попадаться числа-близнецы. Вот промелькнули следующие числаблизнецы: 11 и 13, 17 и 19. Мы быстро набираем скорость; оставляя позади лампочки 101 и 103, 827 и 829; теперь реже и реже встречаются освещенные островки из лампочек, пронумерованы простыми числами-близнецами. Вот на фоне темноты и мрака засверкали лампочки с номерами 10 016 957 и 10 016 959; это последняя пара известных простых чисел-близнецов. Возможно, где то в бесконечных просторах обрадуют наш взор еще пара светящихся лампочек, или такие близнецы исчезнут навсегда. Нам встречаются участки, довольно часто освещаемые лампочками, но чаще путь проходит в темноте. Из первого миллиона промелькнуло всего 78 498 горящих лампочек, 921 502 не горели». Как и пространство, множество простых чисел бесконечно. Ряд натуральных чисел: 1, 2, 3, 4, 5, … является бесконечным и называется 7
8 натуральным рядом. Среди натурального ряда чисел мы выделяем простые числа. Выделение простых чисел является сложной задачей математики. Ученые на протяжении многих веков пытаются найти формулу, которая позволила бы из множества натуральных чисел выписать простые. Первый, кто занимался этой задачей, был великий математик древности Эратосфен Киренский, живший почти 2 300 лет назад. Он был главным библиотекарем знаменитой Александрийской библиотеки, математиком, географом, историком, астрономом, философом и поэтом. Эратосфен К. вычислил наклон эклиптики – большой окружности сферы, по которой проходит видимое годичное движение солнца, расстояние от солнца и луны, длину земного меридиана (измерив расстояние от Асуана до Александрии), составив карту мира с учетом шарообразности Земли. Способ Эратосфена К. составления таблиц простых чисел чрезвычайно прост и не требует проверки чисел на делимость. Для того чтобы очистить зерно, мы его просеиваем. Подобно этому Эратосфен К. «просеивал» числа натурального ряда, пользуясь особым приѐмом. Решето Эратосфена К. – алгоритм нахождения всех простых чисел до некоторого целого числа n. Следуя методу, нужно выполнить следующие шаги: 1. Выписать подряд все натуральные числа от 2 до N (число 2 в списке простое). 2. Пройдем по ряду чисел, вычеркивая все числа кратные 2 (каждое второе). 3. Следующее, не вычеркнутое число 3 – простое. Пройдем по ряду чисел, вычеркивая все числа, кратные 3 (каждое третье). 4. Следующее, не вычеркнутое число 5 – простое. Пройдем по ряду чисел, вычеркивая все числа, кратные 5 (каждое пятое) и т.д. 8
9 В результате все составные числа будут просеяны, а не вычеркнутыми останутся простые числа. Пример таблицы простых чисел до 100 приведен ниже. Таблица простых чисел до 100 Простые числа: 2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97. Однако способ Эратосфена К. не смог удовлетворить ученых, и они пытались найти формулу простых чисел. На протяжении многих столетий это сделать не удавалось. В ряду простых чисел были найдены многие интересные закономерности, но поставленная задача оставалась без ответа. Первым приблизился к решению проблем простых чисел П. Л. Чебышев. Ему удалось доказать формулу, дающую приближѐнный ответ на вопрос: сколько существует простых чисел, заключѐнных между 1 и некоторым натуральным числом х. В 1876 г. французский математик Франсуа Эдуард Анатоль Лукас установил, что 2127-1=170 141 183 460 469 231 731 687 303 715 884 105 727 также простое. Оно содержит 39 цифр. Для его вычисления были использованы механические настольные счетные машины. В 1957 г. было найдено следующее простое число: 23217 – 1. А простое число 244 497 – 1 состоит из 13 000 цифр. 9
10 1.2 Примеры аддитивных задач К аддитивным задачам аналитической теории чисел относятся проблемы, связанные с уравнениями в целых числах специального вида. Основными вопросами в этой проблематике являются следующие: доказать разрешимость заданного уравнения, найти асимптотическую формулу для числа решений заданного уравнения. Второй вопрос значительно труднее, и положительный ответ на него в некотором смысле дает ответ на первый вопрос. Классическими примерами аддитивных задач являются проблема Варинга, проблема Гольдбаха, проблема Харди-Литтлвуда. Проблема Варинга (1770 г.) формулируется так: пусть Jk, n (N) – число решений в целых положительных числах x1, ..., xk уравнения (1.2.1) где N ≥ 1 – целое число. Доказать, что существует такое число k0 = k0 (n) (k0 зависит только от n), что Jk, n (N) ≥ 1 при k ≥ k0 . Другими словами, доказать, что любое число N ≥ 1 может быть представлено суммой n = х степеней целых положительных чисел, причем число слагаемых в этом представлении зависит только от n. При n = 2 задача была решена Жозефом Луи Лагранжем (1770 г.), который доказал, что каждое целое положительное число есть сумма четырех квадратов целых чисел. Первое общее решение проблемы Варинга дано К. Д. Гильбертом в 1909 г. Позднее, в 1924 г. Г. X. Харди и Д. И. Литтлвуд, применив свой круговой метод, доказали, что для Jk, n (N) при k ≥ n•(2n + 1) имеет место асимптотическая формула вида: (1.2.2) 10
11 где γ > 0 и А = А(N) ≥ с > 0, с – абсолютная константа. А поскольку существует бесконечно много таких чисел N, которые для k = n не являются суммой n-х степеней, т. е. Jk, n (N) = 0, то возникла проблема установления истинного порядка величины k в зависимости от n, при котором разрешимо уравнение (1.2.1) и справедлива формула (1.2.2). Самые сильные результаты в этой проблеме принадлежат И. М. Виноградову, который в 1934 г. доказал, что а) Jk, n (N) ≥ l при N ≥ N0 (n), если k ≥ 3n•ln n + 11•n; б) формула (1.2.2) имеет место при k ≥ 4•n2•ln n. Другая аддитивная проблема – проблема Гольдбаха-Эйлера (1742 г.), состоит в следующем: пусть J(N) – число решений в простых числах p1, р2, р3, уравнения p1 + р2 + р3 = N; доказать, что при нечетном N ≥ 7 будет J(N) ≥ 1. В 1937 г. И. М. Виноградов доказал, что асимптотическая формула для J(N): (1.2.3) где В = В(N) ≥ 0,6. Отсюда следует, что J(N) ≥ 1 при N ≥ N0, т. е. решение проблемы Гольдбаха-Эйлера для достаточно больших N. К аддитивным задачам относится проблема Харди-Литтлвуда (1923 г.); каждое N ≥ 2 может быть представлено в виде N = p + x2 + y2, где р – простое число, х, у – целые положительные числа. В 1958 г. Юрий Владимирович Линник доказал, что если W(N) – число решений этого уравнения, то имеет место асимптотическая формула (1.2.4) где σ = σ (N) ≥ c1 > 0, c1 – абсолютная константа. Отсюда следует, что W(N) ≥ 1 при N ≥ N0, т. е. решение проблемы Харди-Литлвуда для достаточно больших N. Имеется много аддитивных проблем, которые еще не решены и имеют возраст сотен и даже тысяч лет. К ним, например, относятся вопросы о 11
12 бесконечности числа простых чисел близнецов, т. е. пар простых чисел р и q таких, что |p - q| = 2, бинарная проблема Гольбаха-Эйлера, т. е., что каждое четное число ≥ 4 есть сумма двух простых чисел, проблема существования бесконечного числа простых чисел в последовательности вида n2 + 1. Таким образом, простые числа в математике играют важную роль. Они являются ключом к разрешению многих математических проблем, одной из которых является проблема К. Гольдбаха. 12
13 2 Проблемы Гольдбаха В 1742 году математик К. Гольдбах послал письмо Л. Эйлеру, в котором он высказал следующее предположение: «Каждое нечѐтное число, большее 5, можно представить в виде суммы трѐх простых чисел». Л. Эйлер заинтересовался проблемой и выдвинул более сильную гипотезу: «Каждое чѐтное число, большее двух, можно представить в виде суммы двух простых чисел». Первое утверждение называется тернарной проблемой К. Гольдбаха, второе – бинарной проблемой К. Гольдбаха (или проблемой Л. Эйлера). Рассмотрим подробно эти проблемы. 2.1 Тернарная проблема К. Гольдбаха Тернарная проблема К. Гольдбаха формулируется так: «Каждое нечѐтное число большее 7 можно представить в виде суммы трѐх нечѐтных простых». Эквивалентная формулировка: «Каждое нечѐтное число большее 5 можно представить в виде суммы трѐх простых». Это утверждение было доказано для всех достаточно больших чисел Иваном Матвеевичем Виноградовым в 1937 году, за что он получил Сталинскую премию и звание Героя Социалистического Труда. В 1923 году математики Годфри Гарольд Харди и Джон Идензор Литтлвуд показали, что в случае справедливости некоторого обобщения гипотезы Г.Ф.Б. Римана, проблема К. Гольдбаха верна для всех достаточно больших нечѐтных чисел. В 1937 году И. М. Виноградов представил доказательство, не зависящее от справедливости гипотезы Г. Ф. Б. Римана, т. е. доказал, что любое достаточно большое нечѐтное число может быть представлено в виде суммы трѐх простых. Сам И. М. Виноградов не дал явной оценки для этого 13
14 «достаточно большого числа», но его студент К. Бороздин доказал, что нижняя граница не превышает (2.1.1) То есть, это число содержит почти 7 миллионов цифр, что, в настоящее время, делает невозможной прямую проверку всех меньших чисел. В дальнейшем результат И. М. Виноградова многократно улучшали, пока в 1989 году китайские математики Ван Юэн и Чен Джингрун не опустили нижнюю грань до (2.1.2) что по-прежнему находится вне пределов досягаемости для явной проверки всех меньших чисел при современном развитии вычислительной техники. В 1997 году французский математик Жан-Марк Дешульер, голландский математик Херман те Риле, американский математик Гоув Эффингер и российский математик Зиновьев Дмитрий Викторович показали, что обобщѐнная гипотеза Г. Ф. Б. Римана влечѐт справедливость слабой проблемы К. Гольдбаха. Они доказали еѐ справедливость для чисел превышающих 1020, в то время как справедливость утверждения для меньших чисел легко устанавливается на компьютере. В 2013 году тернарная гипотеза К. Гольдбаха была окончательно доказана Х. А. Гельфготтом. 2.2 Бинарная проблема К. Гольдбаха Бинарная проблема К. Гольдбаха формулируется так: «Любое чѐтное число большее двух можно представить в виде суммы двух простых чисел». 14
15 О своем наблюдении К. Гольдбах написал великому математику XVIII века Л. Эйлеру, который был членом Петербургской Академии наук. Проверив еще много четных чисел, он убедился, что все они являются суммами двух простых чисел. Но четных чисел бесконечно много. Поэтому вычисления Л. Эйлера давали лишь надежду на то, что свойством, которое заметил К. Гольдбах, обладают все числа. Однако попытки доказать, что это всегда будет так, ни к чему не привели. С тех пор как К. Гольдбах выдвинул эту гипотезу, математики не сомневались, что она верна. Тем не менее, никто никогда не претендовал на то, что сумел ее доказать. К решению этой проблемы существует подход «в лоб» – надолго запустить компьютерную программу, которая бы последовательно проверяла это утверждение на всѐ больших и больших числах. Таким способом можно было бы опровергнуть теорему, будь она неверна. Но так нельзя доказать теорему – по той простой причине, что никогда нельзя гарантировать, что число, которое программа могла бы проверить за следующий свой шаг, не окажется первым исключением из правила. В действительности мы знаем, что проблема К. Гольдбаха верна, по крайней мере, для всех четных чисел, не превышающих 100 000. В 30-е годы XX века группа русских математиков установила, что проблема К. Гольдбаха верна для большого класса четных чисел. Однако доказательство теоремы до сих пор не найдено. Бинарная проблема К. Гольдбаха далека от решения. И. М. Виноградов в 1937 году и Теодор Эстерманн в 1938 году показали, что почти все чѐтные числа представимы в виде суммы двух простых чисел (доля непредставимых, если они есть, стремится к нулю). Этот результат немного усилен в 1975 году Хью Монтгомери и Робертом Чарльзом Воганом. Они показали, что существуют положительные константы c и C такие, что количество чѐтных чисел, не больших N, непредставимых в виде суммы двух простых чисел, не превышает C•N1 − c. 15
16 В 1930 году Лев Генрихович Шнирельман доказал, что любое чѐтное число представимо в виде суммы не более чем 800 000 простых чисел. Этот результат многократно улучшался. В 1995 году французский математик Оливье Рамаре доказал, что любое чѐтное число – сумма не более чем 6 простых чисел. В 1966 году Ч. Джингрун доказал, что любое достаточно большое чѐтное число представимо или в виде суммы двух простых чисел, или же в виде суммы простого числа и полупростого (произведения двух простых чисел). Например, 100 = 23 + 7 · 11. На апрель 2012 года бинарная гипотеза К. Гольдбаха была проверена для всех чѐтных чисел, не превышающих 4 • 1018. Бинарная гипотеза К. Гольдбаха может быть переформулирована как утверждение о неразрешимости диофантова уравнения 4-й степени некоторого специального вида. Бинарная проблема Гольдбаха всѐ ещѐ далека от решения, но с помощью компьютера, для ограниченных параметров решена. 2.3 Метод Харди-Литтлвуда Первая гипотеза Харди-Литтлвуда – гипотеза о плотности распределения кортежей простых чисел вида (p, p+a2…, p+ak), утверждающая, в частности, что число таких кортежей бесконечно, исключая тривиальные случаи. Эта гипотеза является уточнением гипотезы о простых близнецах, а также является частным случаем гипотезы американского математика Леонарда Юджина Диксона. Вторая гипотеза Харди-Литтлвуда – теоретико-числовая гипотеза, сформулированная английскими математиками Г.Х. Харди и Д. И. Литтлвудом, утверждающая, что π(x+y) ≤ π(x)+π(y), где π(x) – функция распределения простых чисел. Иначе говоря, гипотеза утверждает, что в любом отрезке длины y число простых чисел всегда не превосходит числа простых чисел в отрезке [1; y]. 16
17 В 1974 г. Яном Ричардсом было показано, что вторая гипотеза Харди-Литтлвуда противоречит первой гипотезе Харди-Литтлвуда. С точки зрения большинства математиков первая гипотеза более правдоподобна, а вторая, следовательно, ложна. Однако контрпример ко второй гипотезе, если он существует, должен быть очень большим. К примеру, рассмотрим допустимый кортеж из 447 простых на интервале длиной y=3159 (числа в данном примере подобраны на основе равенства π (3159) = 446). Если первая гипотеза истинна, а вторая – ложна, то первый такой 447-кортеж может быть обнаружен при x больше 1,5 • 10174 , но меньше 2,2 • 101198 . Одна из особенностей метода Харди-Литтлвуда заключается в том, что он может применяться для рассмотрения многих других аддитивных проблем. Начало этому методу было положено работой Г. Х. Харди и Сринивасом Рамануджаном в 1918 г., касающейся функции разбиения чисел на слагаемые, но затрагивающей также представление чисел в виде сумм квадратов. Пусть А = (am) – строго возрастающая последовательность неотрицательных целых чисел. Рассмотрим функцию (2.3.1) и ее s-ю степень (2.3.2), где Rs(n) – число представлений п в виде суммы s членов A. Задача состоит в том, чтобы оценить Rs(n) по крайней мере для больших значений п. По интегральной формуле Коши (2.3.3), 17
18 где l – окружность с центром в 0 радиуса р, 0<р< 1. Г. Х. Харди и С. Рамануджан разработали метод оценки этого интеграла в случае am = m2. Пусть р = 1 - 1/n, где п велико, и пусть е(α) = е2πiα. Тогда функция F имеет «пики» в точках z = ρe (α), «близких» к , если q «не слишком большое». На самом деле в окрестности таких точек F имеет асимптотическое представление, справедливое при ≤ и q≤ . По теореме Дирихле о диофантовом приближении, каждое z ϵ l находится в такого рода окрестности. После первой мировой войны Г. Х. Харди и Д. И. Литтлвуд обратились к проблеме Варинга. К сожалению, в случае am = mk с k ≥ 3 они смогли показать только, что разложение (2.3.4), справедливо при q≤n1/k-ε и |α-a/q|≤q-1n1/k-ε-1, а это составляет лишь малую часть точек z на l. Поскольку q-1S(q, а)→0 при q→∞ (для (a,q)= 1), возникла гипотеза, что в остальных точках z функция F во всяком случае мала по сравнению с тривиальной оценкой (1-р)-1/k = n1/k. Эта гипотеза подкреплялась фактом равномерного распределения по модулю 1 чисел a•mk для иррациональных α. Действительно, на основе метода, берущего начало в фундаментальной работе Германа Клауса Гуго Вейля в 1916 году о равномерном распределении последовательностей, Г. Х. Харди и Д. И. Литтлвуд сумели доказать, что на остатке l функция F существенно меньше, чем n1/k. Полученное утверждение о величине F часто называют неравенством Г. К. Г. Вейля. Для описания частей l, на которых используются соответственно аналог соотношения (2.3.4) и неравенство Г. К. Г. Вейля, Г. Х. Харди и Д. И. Литтлвуд ввели термины «большие» и «малые» дуги. 18
19 Метод Харди и Литтлвуда был усовершенствован советским математиком И. M. Виноградовым. Его основным достижением были оценки на малые дуги. На самом деле в круговом методе это сложная часть, и оценки Виноградова на тот момент были результатом крайне нетривиальных комбинаторных рассуждений. Для оценки же больших дуг он использовал методологию, похожую на ту, которая была у Г. Х. Харди и Д. И. Литтлвуда. 2.4 Метод Виноградова В начале 30-х гг. 20 в. И. M. Виноградовым был найден метод тригонометрических сумм, позволивший решить многие проблемы теории чисел. Так, занимаясь проблемой Варинга, И. M. Виноградов обнаружил (1929 г.), что результат Харди-Литтлвуда будет значительно проще, если вместо производящих рядов рассматривать тригонометрические суммы вида (2.4.1), где F(x) - действительная функция, и пользоваться соотношением (2.4.2) Тогда Rs(N) в проблеме Варинга запишется так: (2.4.3), где (2.4.4) 19
20 Далее интервал интегрирования [0,1] разбивается рациональными несократимыми дробями вида , 0≤a< b ≤ h, h – параметр, зависящий от N, на подынтервалы подобные «большим» и «малым» дугам кругового метода. Интервалы, отвечающие дробям с малыми знаменателями, и сумма интегралов по ним дают главный член асимптотической формулы для Rs(N) . Другие интервалы отвечают «малым» дугам; для них И. M. Виноградов оценивает |S(a)| методом Вейля и получает остаточный член. И. М. Виноградов предложил два метода оценок тригонометрических сумм. Первый метод (1934 г.) дал возможность получить новые оценки сумм Вейля. Второй метод Виноградова (1937 г.) позволил оценить такие тригонометрические суммы, в которых суммирование ведѐтся по простым числам: (2.4.5) Это привело к доказательству асимптотической формулы для числа представлений нечѐтного числа суммой трѐх простых. Тем самым была решена тернарная проблема Гольдбаха. Для бинарной проблемы круговой метод не действует – влияние малых дуг там оказывается слишком сильным и метод Виноградова не применим. 20
21 3 Программная реализация и проверка ее работоспособности 3.1 Описание основных функций программы и еѐ реализация Для бинарной проблемы Гольдбаха построена блок-схема в соответствии с рисунком 3.1.1. начало max=200 i=1..max+1 a[i]=i i=1..max+1 j=1..a[i]+1 Да a[i]%j==0 Нет t=t+1 Да t==2 z=z+1 c[z]=a[i] t=0 1 21 Нет
22 1 true Нет Да Ввод k Да k<4 || k%2!=0 || k>c[z]+c[z-1] Нет break povtorite vvod cin.clear() while (cin.get()!='\n') s=0 k1=0 i=1..k+1 j=i..k+1 s=c[i]+c[j] Да Нет s==k k1=k1+1 Вывод c[i]+c[j] Вывод k1 конец Рис.3.1.1. Блок–схема бинарной проблемы Гольдбаха 22
23 Для тернарной проблемы Гольдбаха построена блок-схема в соответствии с рисунком 3.1.2. начало max=200 i=1..max+1 a[i]=i i=1..max+1 j=1..a[i]+1 Да a[i]%j==0 Нет t=t+1 Да t==2 z=z+1 c[z]=a[i] t=0 1 23 Нет
24 1 true Нет Да Ввод k Да k<7 || k%2!=1 || k>c[z]+c[z-1]+c[z-2] Нет break povtorite vvod cin.clear() while (cin.get()!='\n') s=0 k1=0 i=1..k+1 j=i..k+1 z=j..k+1 s=c[i]+c[j]+c[z] Да s==k && c[z]!=0 Нет k1=k1+1 Вывод c[i]+c[j]+c[z] Вывод k1 конец Рис.3.1.2. Блок–схема тернарной проблемы Гольдбаха 24
25 Используя блок-схемы (Рис.3.1.1 и 3.1.2) реализуем код на языке С++ для бинарной и тернарной проблем Гольдбаха: На I этапе заполняется массив a[i] числами, где индекс числа равен самому числу. int main(int argc, char* argv[]) { int max=200; for(i = 1; i < max+1; i++) { a[i] = i; } На II этапе проверяется каждый из элементов массива a[i], является ли он простым числом. Если количество делителей числа равно 2, то число простое, записываем его в массив c[z] . В противном случае обнуляем переменную для подсчета и считаем заново для других элементов массива a[i]. for( i = 1; i < max+1; i++) { for( j = 1; j < a[i]+1; j++) { if(a[i]%j == 0) t=t+1; } if(t == 2 ) { z=z+1; c[z]=a[i]; } t = 0; } На III этапе идет проверка на корректность введенных данных пользователем. 25
26 Для бинарной проблемы Гольдбаха ограничения: число k не меньше 4, не нечетное, не превышает суммы последних двух простых чисел массива c[z]. Для тернарной проблемы Гольдбаха ограничения: число k не меньше 7, не четное, не превышает суммы последних трех простых чисел массива c[z]. Пользователь так же может ввести символ, а у нас число k – целое число. Поэтому используем функцию cin.get() для проверки, чтобы программа не выдавала ошибку. Здесь же используем функцию cin.clear() для очищения нашей переменной для корректности работы в дальнейшем. Пока пользователь не введет правильные данные, выводится сообщение «Некорректные данные, повторите ввод». Если введенные данные отвечают всем условиям, прекращается проверка корректности. while(true) { cout << "Vvedite chetnoe chislo >= 4"<<endl; // для бинарной (cout << "Vvedite nechetnoe chislo >= 7"<<endl; // для тернарной) cout << "k="; cin >> k; if(k<4 || k%2!=0 || k>c[z]+c[z-1]) // для бинарной (if(k<7 || k%2!=1 || k>c[z]+c[z-1]+c[z-2]) // для тернарной) { cout << "Nekorrektnye dannye, povtorite vvod"<<endl; cin.clear(); while (cin.get() != '\n'); } else break; } На IV этапе ищем все представления нашего числа суммой двух простых чисел для бинарной проблемы Гольдбаха и трех для тернарной, считаем их количество и выводим на экран. 26
27 Для бинарной: s=0; k1=0; for( i = 1; i < k+1; i++) { for( j = i; j < k+1; j++) { s=c[i]+c[j]; if (s==k) { k1=k1+1; cout << c[i] <<"+" <<c[j] <<endl; } } } cout << "Kolichestvo predstavleniy=" <<k1; getch(); return 0; } Для тернарной: s=0; k1=0; for( i = 1; i <= k; i++) { for( j = i; j <= k; j++) {for( z = j; z <= k; z++) { s=c[i]+c[j]+c[z]; if (s==k && c[z]!=0) { k1=k1+1; cout << c[i] <<"+" <<c[j] <<"+" <<c[z]<<endl; } } } } 27
28 cout << "Kolichestvo predstavleniy=" <<k1; getch(); return 0; } 3.2 Проверка работоспособности программы Для проверки работоспособности были выбраны следующие данные: для бинарной проблемы Гольдбаха: число 46 Рис.3.2.1 Результат работы кода бинарной проблемы Гольдбаха • для тернарной проблемы Гольдбаха: число 55 Рис.3.2.2 Результат работы кода тернарной проблемы Гольдбаха Таким образом, вычислительный эксперимент показал, что для ограниченных параметров верна, как тернарная, так и бинарная проблема Гольдбаха. 28
29 ЗАКЛЮЧЕНИЕ Проведенная выше работа позволила мне сделать следующие выводы: 1. Тернарная проблема К. Гольдбаха решена полностью. 2. Бинарная проблема К. Гольдбаха остается далекой от решения, но с помощью компьютера, для ограниченных параметров верна. Двести лет размышляли математики над проблемой К. Гольдбаха. Но пока что, к сожалению, нет надежды, даже с помощью самых лучших электронных вычислительных машин, проверить, верно ли это утверждение для всех чисел. В действительности мы знаем, что бинарная проблема К. Гольдбаха верна, по крайней мере, для всех четных чисел, не превышающих 100 000. Таким образом, в ходе проделанной работы я: • изучил понятие простых и составных чисел, роль простых чисел в математике, примеры аддитивных задач; • познакомился с тернарной и бинарной проблемой К. Гольдбаха, методами Харди-Литтлвуда и И. М. Виноградова; • составил компьютерную программу для проблем К. Гольдбаха и проверил ее работоспособность. Следовательно, поставленные задачи выпускной квалификационной работы выполнены, цель достигнута. 29
30 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Агеева И. Д. Занимательные материалы по информатике и математике. Методическое пособие. – М.: Сфера, 2006. – 240 с. 2. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. – М.: Книга по Требованию, 2012. – 419 с. 3. Альманах современной науки и образования. – Тамбов: Грамота, 2014. № 12. – с. 95-100. 4. Бухштаб А. А. Теория чисел. – М.: Книга по Требованию, 2012. – 386 с. 5. Венков Б. А. Элементарная теория чисел (книга IV). – М.: Книга по Требованию, 2012. – 222 с. 6. Виноградов И. М. Основы теории чисел: учебное пособие. – М.: Книга по Требованию, 2012. – 181 с. 7. Дирихле П. Г. Л. Лекции по теории чисел. М.: Книга по требованию, 2012. – 404 c. 8. Доксиадис А. Дядя Петрос и проблема Гольдбаха. Пер. с англ. М. Левина. – М.: АСТ, 2002. – 208 с. 9. Егоров Д. Ф. Элементы теории чисел. – М.: Книга по требованию, 2012. – 202 c. 10. Золотарев Е. И. Теория целых комплексных чисел с приложением к интегральному исчислению. – М.: Книга по требованию, 2012. – 184 c. 11. Куликов Л. Я. Алгебра и теория чисел: учебное пособие для педагогических институтов. – М.: Книга по требованию, 2012. – 560 с. 12. Михелович Ш. Х. Теория чисел : учеб. пособие / Ш. Х. Михелович. 2-е изд. – М.: Книга по Требованию, 2012. – 336 с. 13. Нестеренко Ю. В. Теория чисел: учебник для студ. высш. учеб. заведений / Ю. В. Нестеренко. – М.: Академия, 2008. – 272 с. 14. Просветов Г. И. Теория чисел: задачи и решения: учебно-практическое пособие. – М.: Альфа-Пресс, 2010. – 72 с. 30
31 15. Сизый С. В. Лекции по теории чисел. – М.: Физматлит, 2007. – 192 с. 16. Трошин В. В. Занимательные дидактические материалы по математике. Сборник заданий. Выпуск 2. – М.: Глобус, 2008. – 282 с. 17. https://ru.wikipedia.org/wiki/ Проблема_Гольдбаха. 18. https://ru.wikipedia.org/wiki/ Открытые_проблемы_в_теории_чисел. 19. http://referat.niv.ru/view/referat-mathematics/121/120451.htm. 20. http://festival.1september.ru/articles/417494/. 31
32 ПРИЛОЖЕНИЕ А Проблема Гольдбаха (бинарная) //--------------------------------------------------------------------------#include <vcl.h> #pragma hdrstop #include <iostream.h> #include <math.h> #include <conio.h> #include <stdio.h> using namespace std; //--------------------------------------------------------------------------int k, k1, s, i, j, z, t, a[200]; c[200]; #pragma argsused int main(int argc, char* argv[]) { int max=200; for(i = 1; i < max+1; i++) { a[i] = i; } for( i = 1; i < max+1; i++) { for( j = 1; j < a[i]+1; j++) { if(a[i]%j == 0) t=t+1; } if(t == 2 ) { z=z+1; 32
33 c[z]=a[i]; } t = 0; } while(true) { cout << "Vvedite chetnoe chislo >= 4"<<endl; cout << "k="; cin >> k; if(k<4 || k%2!=0 || k>c[z]+c[z-1]) { cout << "Nekorrektnye dannye, povtorite vvod"<<endl; cin.clear(); while (cin.get() != '\n'); } else break; } s=0; k1=0; for( i = 1; i < k+1; i++) { for( j = i; j < k+1; j++) { s=c[i]+c[j]; if (s==k) { k1=k1+1; cout << c[i] <<"+" <<c[j] <<endl; } } 33
34 } cout << "Kolichestvo predstavleniy=" <<k1; getch(); return 0; } //--------------------------------------------------------------------------- 34
35 ПРИЛОЖЕНИЕ Б Проблема Гольдбаха (тернарная) //--------------------------------------------------------------------------#include <vcl.h> #pragma hdrstop #include <iostream.h> #include <math.h> #include <conio.h> #include <stdio.h> using namespace std; //--------------------------------------------------------------------------int k, k1, s, i, j, z, t, a[200]; c[200]; #pragma argsused int main(int argc, char* argv[]) { int max=200; for(i = 1; i <= max; i++) { a[i] = i; } for( i = 1; i <= max; i++) { for( j = 1; j <= a[i]; j++) { if(a[i]%j == 0) t++; } if(t == 2 ) { z=z+1; 35
36 c[z]=a[i]; } t = 0; } while(true) { cout << "Vvedite nechetnoe chislo >= 7"<<endl; cout << "k="; cin >> k; if(k<7 || k%2!=1 || k>c[z]+c[z-1]+c[z-2]) { cout << "Nekorrektnye dannye, povtorite vvod"<<endl; cin.clear(); while (cin.get() != '\n'); } else break; } s=0; k1=0; for( i = 1; i <= k; i++) { for( j = i; j <= k; j++) { for( z = j; z <= k; z++) { s=c[i]+c[j]+c[z]; if (s==k && c[z]!=0) { k1=k1+1; 36
37 cout << c[i] <<"+" <<c[j] <<"+" <<c[z]<<endl; } } } } cout << "Kolichestvo predstavleniy=" <<k1; getch(); return 0; } //--------------------------------------------------------------------------- 37
Отзывы:
Авторизуйтесь, чтобы оставить отзыв