Вестник пермского университета




Дата02.04.2016
Размер0.49 Mb.

ВЕСТНИК ПЕРМСКОГО УНИВЕРСИТЕТА

2011 Математика. Механика. Информатика Вып. 1(5)



УДК 511.2



Уточнения формул распределения простых чисел
Е. Л. Тарунин

Пермский государственный университет, Россия, 614990, Пермь, ул. Букирева, 15



tarunin@psu.ru; (342) 2-237-10-31
Для теории чисел характерно применение тонких аналитических методов. Поэтому ее называют "жемчужиной математики". Со второй половины XX века для изучения теории чисел стали применять вычислительную технику. В данной статье показано применение персональных компьютеров к проблеме распределения простых чисел. Подбором переменных коэффициентов удалось снизить нормы отклонений четырех наиболее популярных функций распределения простых чисел от реальных значений.
Ключевые слова: теория простых чисел; распределение простых чисел.


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

Число простых чисел, меньших или равных , как это принято, будем обозначать функцией . Этой функции иногда приписывают гладкость, что не соответствует действительности. Функции распределения соответствует ступенчатая функция. Производная этой ступенчатой функции изменяется в широких пределах׃ от 1/2 на близнецах до 1/ ( – максимальное расстояние между соседними простыми числами).

Поиск формул, дающих простые числа, предпринимал еще Ферма (1601–1665). Приближенные функции распределения получали, исследовали и уточняли многие ученые [1–9]. Проанализируем функции

(1)

(2)

(3)

(4)

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

Вторую формулу предложил Лежандр (1808). Он намеревался подобрать зависимость , которая приближает функцию (2) к реальной функции . Идея подбора оптимальной функции занимала и Гаусса. Вопросы построения оптимальной функции рассматриваются и в данной работе. Для начала Лежандр предложил заменить обсуждаемую функцию постоянным значением 1.08366, которое позднее назвали постоянной Лежандра. Функция (2) со значением постоянной Лежандра неплохо описывает распределение в области невысоких значений аргумента (104 –106).

П.Л.Чебышев показал [6], что пределом при должна быть 1. Поэтому при достаточно больших значениях третья функция (3) становится более точной. Очевидно, что выполнение требования при примиряет подходы Лежандра и Чебышева.

Уверенность в том, что функция (4) лучше аппроксимирует зависимость , приобрел еще Гаусс, обрабатывая имеющиеся таблицы. Однако он высказал мнение об этом позднее (1849) в письме Enke. Функцию (4) часто называют логарифмическим интегралом, хотя в действительности логарифмическим интегралом в математике называют интеграл, имеющий особенность при [9]:



. (5)

В силу малого отличия интегралов при больших значениях часто не делают различия между ними. Для определенности мы будем говорить именно об интеграле без особенности – . Достаточно подробные сведения об истории оценок функций (1–4) содержатся в работах [7–9].

Первые три функции (1–3) являются легковычислимыми. Сложности возникают при вычислении интеграла при большом значении верхнего предела. В этом случае для вычисления часто используют разложение [9]

. (6)

Ряд в (6) не является сходящимся, при достаточно большом номере факториал становится больше степени логарифма. Близка к реальному значению интеграла сумма ряда, вычисленная до минимальной добавки. Вопросы, связанные с особенностями вычисления логарифмического интеграла, будут рассмотрены ниже.

Анализ функций (1–4), произведенный многими исследователями, позволяет утверждать, что для них выполняется цепочка неравенств

. (7)

Графически эти неравенства проиллюстрированы лишь в узком интервале аргумента. При графики функций приведены, например, в [7, 9].

Последнее неравенство в этой цепочке () проверено экспериментально для достаточно больших значений . Однако есть доказательство Литлвуда, утверждающее, что разность при очень больших значениях аргумента неоднократно меняет знак. Заметим, что пока не обнаружены случаи смены знака обсуждаемой разности. В работе [7] приведена оценка для первого корня этой разности .

Основная теорема теории чисел, изложенная в работах [7–9], утверждает, что асимптотика формул (1), (3), (4) при одинакова. Для формулы Лежандра (2) это тоже справедливо при упомянутом условии: при коэффициент . Чтобы дать представление о сближении функций при , укажем, например, что относительная разность функций и менее 1% лишь при

Перейдем к описанию результатов, полученных ранее с помощью различных вычислительных экспериментов (ВЭ). В работе [10] было предложено искать для функций (1, 2, 3) поправочные коэффициенты , которые приблизят их к реальной зависимости . Эти поправочные коэффициенты уменьшают норму отклонения . Ясно, что результат (значение ) зависит от выбранной нормы и от рассматриваемого интервала .

Поиску "оптимальных" коэффициентов предшествовал этап определения коэффициентов, удовлетворяющих неравенствам



, j=1,3,4 (8)

. (9)

Для первой функции значения коэффициентов определил П.Л.Чебышев [5]. Значения коэффициентов позднее неоднократно уточнялись. Уточнялись они в работе [10] и уточняются в данной статье. Чебышев высказал также утверждение о существовании асимптотических формул при :



.

Последнее утверждение было доказано в 1896 г. независимо друг от друга Адамаром и Валле–Пуссеном. Представление о поведении при увеличении дают значения: 1.08449, 1.04780, 1.02272 для , равных соответственно 10k (k=6,10, 20). Доказательства Адамара и Вале–Пуссена были основаны на анализе дзета-функции Римана. Работы этих авторов показали, что функция (4), предложенная Гауссом, дает более точное приближение к , чем функция .

Для функции в [4] предлагались грубые значения . Уточнение коэффициентов в неравенствах (8), (9) дано в [10] при использовании таблицы простых чисел. Алгоритм заключался в циклическом переборе табличных значений и нахождении коэффициентов, которые удовлетворяют неравенствам (8), (9). Перед началом проверки задавались значения коэффициентов, которые заведомо изменятся, и отслеживался номер простого числа, при котором произошла последняя корректировка. При использовании полной (без пропусков) таблицы простых чисел значения коэффициентов определяются в основном интервалом по от минимального значения до максимального X (). При определении "оптимальных" коэффициентов результат еще зависит от выбранной нормы (именно поэтому мы заключаем слово оптимальность в кавычки).

Из результатов [10] следует, что самая простая функция ( дает заниженные значения. Для "подтягивания" ее к требуется умножать ее на коэффициент больший 1. Границы функции Лежандра ( оказались значительно уже, чем предсказано в [4]: интервал ( сократился почти на порядок. Эксперименты с логарифмическим интегралом (показывают, что в рассмотренном диапазоне действительно больше . Функция Лежандра с коэффициентом оказалась точнее даже и тем более . Указанный коэффициент дает меньшую норму невязки по сравнению с постоянной Лежандра.

Сделаем критические замечания к результатам работы [10]. Самое существенное из них касается малой величины верхнего предела . Избавиться от этого недостатка предполагаем в этой статье за счет увеличения до 1023. Напомним также, что представленные результаты зависят и от нижнего предела . В [10] результаты были получены для номеров простого числа (. В данной работе величина нижней границы увеличена до 103 и приведены аргументы, показывающие, что для поиска асимптотических зависимостей ее разумно еще увеличить.
Результаты
Для проверок была использована таблица значений для набора (k=3,4,…,23) из работы [8]. Для достижения соответствия реальным значениям таблица расширялась втрое за счет изменения значений аргумента для всех использованных значений . Вычисление производилось с использованием оценки сверху [10] для максимального расстояния между простыми числами :

. (10)

Эффект такого дополнения данных про-иллюстрирован на рисунке, где представлены значения аргумента для номеров простых чисел от i=169 до i=175. Представлен центральный интервал по , относящийся к номеру i=172. Выбранный интервал содержит близнецов слева и справа. Выбранному интервалу соответствует значение расстояние между простыми числами 10. По формуле (10) этот интервал расширяется до 32. Видно, что аналитические функции, обходящие значения сверху и снизу, при расширении интервала должны быть сдвинуты за счет соответствующего уменьшения коэффициента kL и увеличения коэффициента правой границы kR.



Для поиска оптимальных коэффициентов определим характеристики отклонения, которые вычисляются с помощью величин





Шесть характеристик отклонения от вычислялись по формулам



,

,

, , (11)

.

Первые три характеристики дают сведения об относительных отклонениях в процентах.

Для всех формул =3( ,

– минимальная степень , а

максимальная (чаще всего , =23).

Вторая характеристика относительных отклонений учитывает неравномерный шаг по , отклонения с большим значением степени берутся с бо'льшим весом ( .

При выводе формулы предполагалось, что плотность распределения простых чисел пропорциональна . В случае . Неравенство свидетельствует о том, что относительные отклонения при больших значениях меньше. Третья характеристика дает максимум модуля относительного отклонения (программа выдавала и соответствующее значение показателя степени). Чаще всего максимум достигался на левом конце интервала ( =3).

Следующие три характеристики дают сведения о реальных (не относительных) отклонениях. При отклонениях одного знака , а в общем случае . При =0 сумма положительных отклонений равна сумме модулей отрицательных отклонений. Для максимального по модулю отклонения программа выдавала и соответствующее значение степени, обычно достигаемое на правом конце интервала ( =23).

Отличия новых значений границ для функций (1–4) обусловлены изменением интервала по . Неожиданным оказалось уменьшение значений верхних границ для первых двух функций. Это, по-видимому, говорит о том, что использованные значения таблиц с пропусками имеют определенный дефект.

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


Таблица 1

Функция % 4.8037

(4.8036)3.4710

(3.4710)1.983

(1.983 )16.12

(13.83) 0.25484

(0.2283)0.1659

(0.1587)1.260

(1.260 )4.825

(2.203) 0.3234

(0.2649)0.16683

(0.1587)3.997

(3.997 )3.348

(0.897) 0.36487

(0.3670)0.09533

(0.09583)4.827

(4.827 )7.929

(5.629)



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

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



.

Для первой функции, например, отсюда легко получить оценки для абсолютной и относительной погрешностей





. (12)

При получаем, что . Из (12) легко определяем оценку для интегральной погрешности



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

1.019639 1.03590,

1.0200498 1.05036,

1.0003860 1.00110,

3.15 (1- ) 3.76566 . (13)

Значения коэффициентов лежат внутри соответствующего интервала ( ). Для первых трех функций набольшим коэффициентом является , а наименьшим – ; в случае логарифмического интеграла наибольшим коэффициентом является , а наименьшим . Укажем номера функций в порядке увеличения трех характеристик погрешности: для суммы относительных отклонений : 2,3,4,1; для суммы относительных погрешностей с весовыми коэффициентами : 2,4,3,1; для суммы абсолютных отклонений : 4,2,3,1. Первая функция во всех случаях находится на последнем месте. "Призовые" места чаще всего занимает вторая функция, за ней следует четвертая функция – логарифмический интеграл (как и ожидалось, эта функция дает наименьшую погрешность – менее 1% для ).

Напомним, что значения (13) относятся к набору трех типов контрольных точек ( и ) для – от 3 до 23. Исключение из таблицы боковых точек ( ) незначительно (в пределах 1%) меняет значения коэффициентов в (13). Сильно влияет на характеристики отклонения значение нижней границы. При вычислении логарифмического интеграла для степеней от = 6 до 23 отклонение уменьшилось в 28.6 раза, а отклонение – в 16.8 раза (полученные значения для коэффициента таковы: , , , , ( ). В случае степеней от =7 до 23 относительные отклонения еще уменьшаются в 2–3 раза.

Постоянные оптимальные значения коэффициентов из (13) не решают проблему поиска оптимальной функции. Они могут приблизить значения функции к , обеспечивая минимум какой-либо нормы невязки, но только на конечном интервале. Нужно иметь функции, которые бы гарантировали требуемые асимптотические свойства при стремлении аргумента к бесконечности. Решить такую задачу можно используя переменные коэффициенты. Такую задачу, как уже упоминалось, пытались решить Лежандр, Гаусс и др.

Пусть требуется найти переменные коэффициенты A(x), B(x), C(x) для трех функций:



, , . (14)

Эти три задачи сводятся к одной. Сведение к одной задаче достигается требованием равенства этих функций и получением соответствующих связей для коэффициентов. Из равенства функций (14) следуют связи



. (15)

Так как все коэффициенты мало отличаются от 1, логично ввести функции отклонения этих коэффициентов от 1:



,

. (16)

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

Имея таблицу простых чисел, можно построить таблицу коэффициентов, которые обеспечивают равенство

. (17)

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

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

При , вычисленной по формуле (10), минимальные значения погрешностей для первых трех функций с учетом боковых значений равны







(18)

Уменьшение интервала между простыми числами вдвое вдвое же уменьшает величины в первой строке (18) и практически не меняет остальные. Сокращение интервала по степеням от 3 до 6 (верхняя граница = 23) снижает значения относительных погрешностей на несколько порядков до значений .

Анализ таблиц , полученных по формулам (17) и (16), позволил выяснить, что коэффициенты монотонно убывают с ростом , начиная с 1.1605 до 1.019639, а коэффициенты монотонно убывают лишь при . Монотонный характер функции обусловил выбор именно этой функции для поиска "оптимальной" аппроксимации. Наиболее удачные аппроксимации были подсказаны формулой разложения логарифмического интеграла (6). Для демонстрации этой идеи формулу (6) запишем в виде

.(19)

Эта идея использовалась в работе [7], в которой учитывали три слагаемых из [19] без всяких поправок и с поправкой последнего коэффициента:



(20)

Ниже мы обсудим погрешность подобных аппроксимаций, а сейчас обсудим вопрос сравнения и, следовательно, выбора аппроксимаций. Очевидно, что выбор аппроксимации должен опираться на все характеристики отклонений (11). Однако часто аппроксимации имеют лишь часть лучших показателей. Как поступать в этом случае? Логично, на наш взгляд, для быстрой предварительной оценки использовать весовые коэффициенты.

Кроме того, сложно сравнивать относи-

тельные и абсолютные погрешности (они могут отличаться порядками). В итоге было ре-

шено использовать два показателя эффективности аппроксимации:



. (21)

Величины с нулевым верхним индексом относятся к погрешностям без всякой коррекции (см. табл. 1). Следовательно, отношения в (21) показывают, во сколько раз уменьшилась соответствующая погрешность. Весовые коэффициенты в характеристике относительных показателей , конечно, являются субъективными – они отражают наше понимание значимости показателя.

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

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




Таблица 2

вариантаАппроксимация 1 42.6230.72 41.932622'Вариант 2, но 47.132623 41.611964 39.1269.55 34.44466 30.51426'Вариант 6, но 37.01427 , 16.315.281 15.249.79 9.025.8



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

. (22)

Особый счет при малом значении (эти варианты отмечены штрихами в номере), как уже не раз отмечалось, существенно уменьшает относительные погрешности. Для варианта 2' характеристики погрешности таковы:









.

Приведенные относительные отклонения весьма близки к минимальным отклонениям (18), но абсолютные все еще велики. Уточнение коэффициентов в вариантах (1, 3) может, конечно, немного улучшить их эффективность, но не существенно.

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

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

Прежде чем обсуждать вопросы погрешности разности , обсудим вопросы точности вычисления логарифмического интеграла. При больших значениях аргумента вычисление определенного интеграла выполняется с помощью разложения (6). Члены разложения вначале убывают, достигают минимума при , а затем начинают возрастать. Минимальные значения убывают с ростом . Приведем их соответствующие значения для 3,10,23: 0.959, 0.523, 0.345. Номера при этих же значениях таковы: 6,23,52.

Рассмотрим в качестве примера случай , для которого , значение определенного интеграла 176.9, значение интеграла по формуле разложения (6) до слагаемого с номером 178.01. Видно, что .

Это типичная ситуация! С ростом разности указанных величин увеличиваются, а относительные – уменьшаются. Например, при 128 (в работе [8] указано 130), а относительная разница около 0.163%. Отсюда следует, что вычисление с недостатком, когда , может приближать вычисленные значения к реальному распределению простых чисел.

Вычислительные эксперименты (ВЭ) подтверждают этот факт. В первой серии ВЭ вычисления выполнялись с уменьшением числа слагаемых в разложении на задаваемое число =1,2,3,4. При каждом увеличении отклонения от уменьшались. Очевидно, что такая корректировка касалась в основном малых значений аргумента, для которых требуемое по точности число разложений было сопоставимо с .

Во второй серии ВЭ определялся первый номер разложения , при котором . Для использованного интервала значений для "оптимального" числа разложений найдена простая формула (функция Round определяет ближайшее целое)

. (23)

По этой формуле для минимальной степени , а для максимальной степени ( . Дополнительное уменьшение погрешностей было получено при .

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

Приведем характеристики отклонения ( при использовании формулы (6) до минимальной добавки ( ):





. (24)

Показатель эффективности уменьшения относительных характеристик для первой серии ВЭ с равен 2.01, а для второй серии 2.95.

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

. (25)

Величины немного меньше 1, и поэтому отслеживались величины , которые быстро убывают с ростом . Для представления об их убывании укажем их значения для 3,10, 23 соответственно: 5.38978 , 6.82063 , 3.76566 .

Точно описать поведение в виде экспоненциальной функции не удалось, так как по полученным данным величина меняется не монотонно: при среднем значении 1.21508 эта величина меняется в пределах от 1.17136 до 1.35665. Наилучшие показатели эффективности соответствуют минимальному значению : . При увеличении быстро уменьшается показатель , Например, при (чуть больше), но . Характеристики отклонения при минимальном значении таковы:





Относительные погрешности близки к минимальным (17), но абсолютные погрешности на три порядка больше. Кроме экспоненциальной аппроксимации можно использовать различные оценки [7,8] для разности .

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

. (26)

Так как функция значительно точнее , весовой коэффициент должен быть малым. Вариант с постоянным значением весового коэффициента явно не годится: при =0.001, например, показатели относительной погрешности незначительно (менее 1%) уменьшились, но при этом показатели абсолютной возросли более чем в тысячу раз.

Значения , полученные из равенства , монотонно убывают с ростом . Использование формулы с экспоненциальным убыванием

(27)

уменьшило относительные погрешности примерно в три раза (в 3.8 раза и в 2.8 раза ), не изменив практически значений абсолютных отклонений.


Выводы


  1. Скорректированы оценки снизу и

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

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

  2. Указаны возможные способы уточнения полученных приближений.


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


  1. Виноградов И.М. Основы теории чисел. 10-е изд. М.׃ Лань, 2004. 176 с.

  2. Сушкевич А.К. Теория чисел (Элементарный курс). М.׃ Вузовская книга, 2007. 240 с.

  3. Бухштаб А.А. Теория чисел: учеб. пособие. Санкт-Петербург, Москва, Краснодар׃ Лань, 2008. 384 с.

  4. Трост Э. Простые числа. М.׃ ИЛ, 1959. 136 с.

  5. Прахар К. Распределение простых чисел. М.׃ Мир, 1967. 512 с.

  6. Чебышев П.Л. Об определении числа простых чисел, не превосходящих данной величины // Избранные труды. М.׃ Изд-во АН. 1955. С. 9–32.

  7. Weisstein Eric W. Prime Number Theorem. From MathWorld–A Wolfram Web Resource ( http:mathworld.wolfram.cjm

/PrimeNumberTheorem.html).

  1. Prime number theorem – Wikipedia, the free encyclopedia.

  2. Bent E. Petersen Prime Number Theorem, Mth 619. Spring 2002.

  3. Тарунин Е.Л. Возможности вычислительных методов в проблемах теории чисел // Вестник Перм. ун-та. Математика. Механика. Информатика. 2010. Вып. 2(2). С.5–28.



Accurate definition of functions for prime numbers
E. L. Tarunin

Perm State University, Russia, 614990, Perm, Bukireva st., 15



tarunin@psu.ru; (342) 237-10-31
A theory of numbers is famed for using of analytical methods. Great mathematicians call the theory as "a pearl of mathematics". Numerical methods and computers were used in the theory only in the second half of the 20 century. Classical analytical methods deal with smooth functions but the real distribution of simple numbers is a stepped function. So it is more suitable for computers. It was shown that computers permit to find "optimal" parameters of different functions (Chebishev, Lagrange, integral logarithm) that can describe the real distribution of simple numbers more exactly.
Key words: theory of simple numbers; distribution of simple numbers.

?

© Е. Л. Тарунин, 2011



10


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница