ИССЛЕДОВАНИЕ ПРОБЛЕМЫ ГОЛЬДБАХА И ПУТИ ЕЁ РЕШЕНИЯ СОВРЕМЕННЫМИ ВЫЧИСЛИТЕЛЬНЫМИ СРЕДСТВАМИ

STUDYING GOLDBACH’S CONJECTURE AND ITS SOLVING WITH MODERN COMPUTING INSTRUMENTS

Pavel Popik

Radio engineer,

Russia, St. Petersburg

АННОТАЦИЯ

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

ABSTRACT

This article presents the results of the study on Goldbach’s Conjecture and reveals the ways of its successful solution. The statistical method was chosen as the method. Based on calculations in spreadsheets, it appears that the number of combinations of prime pairs that add up to even numbers, on the selected interval of even numbers, significantly exceeds their required number for each even number greater than two. In summary, a definition is stated providing a solution of Goldbach’s Conjecture for any even number. An example of a simple true primality test of a natural number is provided.

Ключевые слова: проблема Гольдбаха; простые числа; истинный тест простоты; бинарная гипотеза Гольдбаха; решето Эратосфена; основная теорема арифметики; функция распределения простых чисел.

Keywords: Goldbach’s Conjecture; prime numbers; true primality test; Binary Goldbach’s Conjecture; Sieve of Eratosthenes; Fundament al theorem of arithmetic; prime-counting function.

Введение.

Среди известных не решенных в настоящее время проблем в современной теории чисел является проблема Гольдбаха (гипотеза  Гольдбаха, проблема Эйлера, бинарная проблема Гольдбаха)[1]. В результате переписки в середине восемнадцатого века между Христианом Гольдбахом и Леонардом Эйлером вырисовалась гипотеза о том, что каждое четное число, больше двух, можно представить в виде суммы двух простых чисел (ПЧ). Известна также тернарная гипотеза Гольдбаха, но в 2013 году она была окончательно доказана Харальдом Гельфготтом.

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

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

Тем не менее, на сегодня известно множество аналитических закономерностей, с помощью которых получают ПЧ особого вида или проверяют их на простоту: ПЧ Ферма, ПЧ Мерсенна, числа Вудала; решето Эратосфена, решето Аткина и множество различных тестов проверки на простоту. Наиболее нашумевшим в силу своей относительной свежести (2002 год публикации) и опоры на доказанные гипотезы оказался тест Аграва́ла — Кая́ла — Саксе́ны (тест AKS), который практически не используется из-за своей высокой вычислительной сложности.

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

Тест простоты.

Несмотря на наличие множества тестов, которые подразделяют на два вида, истинные и вероятностные тесты, реализация истинного теста простоты в офисном приложении Excel выполняется в несколько простых шагов. Но, тем не менее, для больших ПЧ, которые используются, например, в алгоритмах защиты информации, этот тест не может быть использован. Он основан на простом переборе, и для больших чисел приложение Excel не рассчитано на подобные сложные вычислительные задачи. В качестве примера на рисунке 1 приведен фрагмент электронной таблицы и два результата, полученных с её помощью [2].

Алгоритм состоит из четырех шагов. В ячейки столбца «А» загружается натуральный ряд чисел, в данном файле от 1 до 1 млн. В ячейку «С1» записывается тестируемое число. В каждую ячейку столбца «В» вводится формула «=ЕСЛИ(C$1/A5=ОКРУГЛ(C$1/A5;0);1;0)», которая проверяет делимость без остатка числа в «С1» на число слева в столбце «А». В случае положительного исхода результат равен 1 и 0 при отрицательном исходе. Ячейки столбца «С», начиная со второй, также заполняются одной и той же формулой: «=ЕСЛИ(B5>0;A5;"")», которая проверяет ячейку «B», что слева, и выводить делитель тестируемого числа из столбца «А». И резюмирует результат формула в ячейке «F1».

«=ЕСЛИ(СУММ(B2:B1048576)=1;"простое";"составное")».

Если сумма всех ячеек столбца «В» равна 1, то число «простое», иначе «составное». А в ячейке «G1» скрыто выражение «делится на 2». Формула в ней определяет минимальный делитель числа 138.

Если при помощи приведенного алгоритма не требуется нахождение делителей, то в столбец «А» для ускорения работы алгоритма закачивается ряд уже известных простых чисел, что согласуется с основной теоремой арифметики о единственности представления составного числа произведением простых. В этом варианте алгоритма для оценки простоты необходимо учесть условие, что минимальный делитель должен быть равен тестируемому числу. Так, например, если число состоит из одного и того же делителя в какой-либо степени (8, 9, 125, 343…), то результат в ячейке «F1» покажет ошибочный результат. В сети интернет можно найти большое количество сайтов с тестами для он-лайн проверки простоты, а также таблицы ПЧ, одна из которых была использована для дальнейшего исследования [3].

Рисунок 1. Фрагмент таблицы Excel, демонстрирующей работу теста простоты

Результаты эксперимента.

Еще древнегреческий математик Евклид утверждал, что простых чисел бесконечно много. Этот вывод напрашивается с учетом утверждения основной теоремы арифметики. С физической точки зрения можно утверждать обратное, так как для представления некоего бесконечно большого числа может не хватить ни времени жизни человечества, ни технических возможностей для его представления. Да и бесконечность, на то и бесконечна, что её нельзя достичь. Но, как утверждается в Википедии, в математике известно несколько доказательств бесконечности ПЧ. Вместе с этим, понятие бесконечности простых чисел тесно связано понятием плотности простых чисел. В эксперименте на массиве в 80000 простых чисел, максимальное из которых превышает миллион, были проверены несколько выражений для функции распределения простых чисел , показывающих, как изменяется количество  ПЧ, по мере увеличения их номинала начиная с двух.

                                                                  (1)

Где ln(n) – натуральный логарифм от натурального числа, верхней границы выбранного диапазона.

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

                                                              (2)

Где В  1,08366 - поправочный коэффициент.

Статистика и расчеты по выражению (2) показывает, что количество ПЧ с ростом n асимптотически уменьшается, но теоретически к нулю не может быть сведено. Так среди первых 10000 НЧ количество ПЧ равно 1229, а к миллиону падает до 721 на интервале в 10 тысяч НЧ, колеблясь уже с полумиллиона в пределах нескольких десятков.

Статистический подход к проблеме Гольдбаха.

Статистический подход основан на очевидном факте, что количество четных чисел на некоем конечном интервале НЧ, при его увеличении, существенно отстает от того возникающего количества комбинаций в два простых числа, из того набора ПЧ, которые входят в этот же или несколько больший интервал НЧ. Любое четное число достаточно большое может быть получено множеством комбинаций простых чисел. Например, 4 =2+2, 6=3+3, 8=3+5 10=5+5=3+7 и т.д. А начиная с 14 и далее 16,18, 20  имеем уже 2 комбинации.

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

Для расчетов были построены три варианта разного размера квадратные вычислительные матрицы. Вариант 1 – матрица ПЧ от 3 до 1999. Вариант 2 –до 3989, вариант3 - до 7993.

В первом крайнем левом столбце и в первой строке таблицы размещаем последовательность ПЧ в соответствии с вариантом. Первая ячейка «А1» остается пустой. Все ячейки матрицы, в которых производим вычисления, заполняем одной и той же формулой: «=ЕСЛИ($A5>=B$1;B$1+$A5;"")».

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

Диагональ заполняется четными числами, образованными парами одинаковых слагаемых, 2+2, 3+3, 5+5, 7+7 … 17+17 и т.д. Таким образом, получает полный перечень всех возможных комбинаций ПЧ (их суммы) в заданном интервале. Каждое ПЧ из первой строки суммируется с каждым ПЧ из левого столбца всего один раз.

В отдельном столбце справа от матрицы формируем перечень всех четных чисел, начиная с 6 и до удвоенной суммы крайнего ПЧ соответствующего варианта, т.е. 1999+1999, 3989+3989 и 7993+7993.Для подсчета количества полученных комбинаций для каждого четного числа, правее него вводим формулу: «=СЧЁТЕСЛИ($B$2:$KQ$303;KS2)». В ней анализируется весь массив из 303х303 сумм ПЧ для варианта 1, и по критерию выбранного четного числа (KS2=6) выдает сумму комбинаций, образующих это число в полученной вычислительной матрице. Поскольку количество комбинаций растет не линейно, а колеблется от числа к числу, то для анализа полученной закономерности далее было вычислено минимальное число комбинаций для каждой сотни НЧ (50 четных чисел) в каждом из исследуемых вариантов, для того чтобы обнаружить провалы. Потенциально во всех вариантах таблиц максимальные значения образуемых четных чисел равны удвоенному значению максимального значения ПЧ, как показано выше, но не на все четные числа выпадает комбинация из 2-х ПЧ. Результат функции «СЧЕТЕСЛИ» в этом случае равен нулю.

Так, для варианта 1 количество четных чисел с нулевыми комбинациями равно 16, от числа 3836 до 3988 . Для варианта 2 количество четных чисел с нулевыми комбинациями равно 36, от числа 7718 до 7976. Для варианта 3 количество четных чисел с нулевыми комбинациями равно 44, от числа 15688 до 15984. На рисунках 2 – 4 приведены полученные зависимости.

Рисунок 2. Минимальных значения комбинаций ПЧ в промежутке 1-100 натуральных чисел, в сумме дающих четные числа, для варианта 1

Рисунок 3. Минимальных значения комбинаций ПЧ в промежутке 1-100 натуральных чисел, в сумме дающих четные числа, для варианта 2

Рисунок 4. Минимальных значения комбинаций ПЧ в промежутке 1-100 натуральных чисел, в сумме дающих четные числа, для варианта 3

Как видно из графиков число комбинаций для каждого четного числа во всех вариантах устойчиво растет до максимума, соответствующего граничному значению ПЧ, что позволяет сделать вывод о разрешимости проблемы Гольдбаха. Энтузиастам, желающим проверить гипотезу Гольдбаха для больших граничных условий, чем в приведенном варианте 3, и имеющим необходимые вычислительные мощности, хочется пожелать не тратить свое драгоценное время. Поскольку согласно источнику в Википедии в разделе «Проблема Гольдбаха» [5] сообщается о том, что её справедливость на апрель 2012 года проверена до величины не превышающей .

Заключение

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

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

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

1. Википедия. Проблема Гольдбаха. https://ru.wikipedia.org/wiki/Проблема_Гольдбаха
2. Ссылка на ВМ истинного теста простоты в облаке. https://disk.yandex.ru/i/kvkuWzXPIe3xHQ
3. Справочник простых чисел. http://www.unconnected.info/sn100.aspx
4. Теорема о распределении простых чисел. https://ru.wikipedia.org/wiki/Теорема_о_распределении_простых_чисел
5. Weisstein, Eric W. Goldbach Conjecture. На сайте Wolfram Math World. http://mathworld.wolfram.com/GoldbachConjecture.html