Статья: Возможности вычислительных методов в проблемах теории чисел

Обещанный миллион многим не дает покоя. Поэтому не случайно в Интернете можно найти объявления о якобы доказательстве гипотезы Римана. Так в Интернете (Компьюлента, 11 июня 2004 г.) помещена заметка В.Парамонова с интригующим заголовком "Найдено доказательство гипотезы Римана". Профессор математики из университета Пердью Луи де Бранж де Бурсил утверждает, что нашел доказательство гипотезы Римана. Его изыскания на 23 листах выложены в свободном доступе [12] и ждут опровержения.

Бинарная проблема Гольдбаха далека от решения. Есть работы [1], в которых доказывается, что если есть доля чисел, не представимых в сумме двух простых, то она мала. Есть работы, в которых увеличено число слагаемых до 6 и более. Утверждается, что на июль 2008 г. бинарная проблема проверена до [8], а на сайте "ЭлементыУ Проблема Гольдбаха" указано значительно меньшее значение .

В сентябре 2004 г. журналистка Татьяна Нечапайко разместила в Интернете заметку о том, что якобы 75-летний минский математик, кандидат наук Виктор Карпов решил "задачу" Гольдбаха-Эйлера [8]. Карпов отнес свою работу в Белорусский государственный университет, педагогический университет и АН. По его словам, от него "отмахиваются, как от назойливой мухи". В заметке описана запутанная история с обещанием в 2000 г. выплатить 1 млн долларов за решение проблемы (по непроверенным сведениям обещание действовало лишь до 2002 г.). Там же отмечено, что греческий ученый и писатель Апостолос Доксиядис проблему не решил, но, написав роман об этой проблеме [9], приобрел всемирную славу. После того как книга стала бестселлером, английское издательство "Faber and Faber" и американское "Bloomsbery" и пообещали приз за решение проблемы. Журналисты "Комсомольской правды в Беларуси" пытаются выяснить судьбу обещанного миллиона и ждут подтверждения правильности доказательства В.Карпова.

4. Вычисление таблицы простых чисел

число простой распределение гольдбах

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

В использованном алгоритме после задания первых четырех простых чисел следующие числа вычислялись по программе (Paskal):

for i:=4 to im do begin j:=2;

10: nc:=N[i]+j; {candidate for next number}

for i1:=2 to im do begin if N[i1] > 0.5*nc then goto 12;

if nc mod N[i1] =0 then begin j:=j+2; goto 10; end; end;

12: N[i+1]:=nc; end; {for i}

Использованный алгоритм на ПК Toshiba требует около 4 сек для получения 30 тысяч простых чисел при программе в Delphi. Одна и та же программа на Паскале в Delphi работает примерно в 2.5 раза быстрее. Для выявления зависимости времени счета от последнего номера простого числа im может быть использована формула:

сек.

Из нее, в частности, следует, что для получения 1 млн простых чисел требуется около 1.5 часа счета.

Отметим особенности программы. Целые переменные и массив для целых чисел предназначены для хранения longint. Первый кандидат на простое число получается добавлением к предыдущему числу j=2. Если полученное число делится на младшие предыдущие простые числа, добавка к новому кандидату на испытание увеличивается еще на 2 оператором j:=j+2. Процесс проверки повторяется до тех пор, пока не выяснятся, что нет делителей у числа nc. И если делителей нет, происходит запись нового простого числа N[i+1]:=nc. Оператор в третьей строке служит для сокращения излишних проверок. Если его убрать, время счета увеличивается примерно вдвое.

Выяснено, что простое число становится более чем в 10 раз больше своего номера при , так как

.

Среди последних цифр простых чисел (1, 3, 7, 9) нет выделенных, их доли при составляют (251)%.

5. Анализ аппроксимаций распределения простых чисел

Опишем вначале отличие функций , описанных в (3) и (4) соответственно. Определенный интеграл в функции Гаусса вычислялся по трем приближенным формулам прямоугольников:

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

Уже при =1000 относительная погрешность интегралов менее 0.08% и с ростом она убывает. Приближенные значения интегралов с избытком и недостатком удобно использовать для получения гарантированных оценок сверху и снизу.

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

Таблица 1

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

Эта величина с ростом номера числа в целом монотонно убывает (нарушения монотонности характерны для значений ). При , становится меньше 1% при , а при 0.33%.

Указанные зависимости характерны и для бо'льших номеров простых чисел. В [4] приведена теорема Е.Мейсселя, позволяющая вычислять далеко за пределам обычных таблиц простых чисел, и в качестве примера приведено значение . Аргумент в этом примере может отличаться от соответствующего значения на расстояние между простыми числами, но при достаточно больших это слабо сказывается на точности оценок. Использование этого примера позволяет оценить коэффициенты табл.1, указанные в третье и четвертой строкахУ 1.000035, 0.94901 соответственно.

Заметим, что вычисление определенного интеграла в формуле Гаусса при требует немалых затрат машинного времени (при около 10 мин). Для сокращения затрат можно использовать идеи распараллеливания алгоритма.

Перейдем к нахождению коэффициентов , которые удовлетворяют неравенствам Чебышева (4) на реальных таблицах .

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

(15)

Перед началом проверки задавались значения коэффициентов, которые заведомо изменятся, и отслеживался номер простого числа, при котором произошла последняя корректировка. При оба коэффициента оказались бо'льшими единицыУ

. В скобках указан номер последней корректировки. Заметим, что если цикл проверки начать с , то величина А уменьшится до А=1.22358 (=46). Значение подтверждает факт заниженной величины при малых и умеренных значениях . Для значительно бо'льших коэффициент , возможно, станет меньше 1. Для проверки полученных значений в цикле по вычислялись относительные отклонения функцииУ

(16)

и по ним вычислялись следующие интегральные характеристики относительного отклоненияУ

(17)

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

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

(18)

В этих формулах - приближенное значение интеграла в функции Гаусса с недостатком, а - значение с избытком. Неравенства (18) используются для поиска ШоптимальныхШ коэффициентов для функции Гаусса, которая считается наиболее приближенной к . Характеристиками отклонения были те же величины (17), что и для функции . При значении коэф-фициента все относительные откло-нения положительны (интегральный лога-рифм больше всех в интервале от до ); максимальное относительное отклонение достигается при . Уменьшение коэффициента () приводит к появлению отрицательных значений отклонений. Первое отрицательное отклонение соответствует номеру . Минимум среднеквадратичной ошибки достигается при (при ).

При значения функции интегрального логарифма лежат ниже значений от 20 до 30000.

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

Таблица 2

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

Рассмотрим аппроксимационные свойства функции с параметром У

. (19)

Очевидно, что положительные значения параметра увеличивают значения функции, а отрицательные - уменьшают. Значение рекомендовал Чебышев, значение - Лагранж. Для построения функций, ограничивающих сверху и снизу, предложены [4] значения 2 и -4. Функция (19) дает существенно завышенные значения при и малых . Так, при относительное превышение менее 1% характерно лишь для простых чисел с номерами

Результаты анализа зависимости (19) для различных значений параметра в интервале от 2 до -4 представлены в табл. 3 ( изменялось от 30 до 30001).

Таблица 3

В табл. 3 указаны характеристики относительных ошибок в %. Определение этих величин приведены в (17). При значениях параметра и, следовательно, значения функции (19) лежат выше значений в таблице (при этом, естественно, ). При и, следовательно, значения функции (19) меньше значений в таблице простых чисел.

В довольно узком интервале от 1.0 до 1.1 функция (19) дает как завышающие, так и занижающие значения. Напомним, что в этом интервале находится значение , указанное Чебышевым для больших значений , а также значение , предложенное Лагранжем. Для рассмотренного интервала простых чисел с номерами от до формула Лагранжа точнее формулы Чебышева (отношение соответствующих среднеквадратичных относительных ошибок 2.56). Это не означает, что Чебышев неправ, так как согласно его утверждениям преимущества его формулы скажутся за пределами рассмотренных значений простых чисел. Вызывает восхищение то, что Лагранж сумел найти значение параметра , близкое к оптимальному. Расчеты показали, что оптимальное значение параметра 1.0755 (при этом величина уменьшается по сравнению с величиной в варианте Лагранжа примерно на 6.8%). Для корректировки формулы типа Лагранжа согласно анализу Чебышева логично переписать ее в виде