Простые числа, математическая статистика и... ЭВМ

19

ПРОСТЫЕ ЧИСЛА,
МАТЕМАТИЧЕСКАЯ
СТАТИСТИКА И… ЭВМ

Кандидат физико-математических наук
А. П. ВИННИЧЕНКО

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

ПУАССОН

2*

19

20

чисел умножением. Начало ряда простых чисел — это 2, 3, 5, 7, а конца ему нет — наиболее простого числа не существует. Будем считать единственное четное простое число 2 «ошибкой природы» и рассмотрим ряд, начиная с 3. Подвергнем этот ряд процедуре разностного анализа*) — будем быть разности двух соседних членов:

$$\begin{align*} 3, & 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 \\ 2 & 2 4 2 4 2 4 2 4 2 6 \end{align*}$$

Разности повторяют — много двоеек, есть четырки, появились и шестерки. Как будто на игровой косте выпадают очки: двойка, двойка, четверка, опять двойка… Еретическая мысль — взглянуть на этот строго deterministic ряд как на результаты измерений некой случайной величины и попробовать обработать их методом математической статистики.

Пусть для обработки взяты простые числа, не превысющие $N$; в примере (1) $N=40$. Прежде всего выпишем в порядке возрастания все наблюдаемые значения $x_1=2, x_2=4, \dots$ нашей «случайной величины» (в примере (1) число этих значений $n=3$), а под ним — частоты $\omega_1, \omega_2, \dots$, с которым они появляются (т. е. отношения числа появления $x_i$ к общему числу наблюдаемой, которое у нас равно 10):

$$\begin{align*} 1 & 4 & 9 & 16 & 25 & 36 \\ 3 & 5 & 7 & 9 & 11 & \dots \\ 2 & 2 & 2 & 2 & \dots ; \end{align*}$$

соответственно, $(x^2)^{n/2}=\text{const.}$

Далее составим таблицу «накопленных частот» $v_i=\omega_1+\omega_2+\dots+\omega_i$, т. е. запишем под каждым значением $x_i$ сумму частот всех значений, не превосходящих $x_i$:

$$\begin{align*} x_i & 2 & 4 & 6 \\ \omega_i & 0,5 & 0,3 & 0,2 \end{align*}$$

Изображим результаты этих расчетов в виде графика ступенчатой функции $F_N(x)$ (рис. 1), называемой эмпирической функцией распределения: $F_N(x)$ равно сумме $\omega_i$ по всем $i$, таким что $x_i \leqslant x$. Наша цель — сравнить графики $F_N(x)$ при разных $N$ и попытаться уловить какую-нибудь закономерность в их поведении при $N \to \infty$. Правда, если взятся за это без соответствующего подготовки, ничего хорошего не получится. Дело в том, что чем дальше, темже встречаются простые числа и тем больше в среднем будут промежутки между ними. Поэтому графики $F_N$ с ростом $N$ будут распливаться вправа. Чтобы компенсировать это распливание, применим к ним процедуру, знакомую нам по детективным романам. При слиянии fotografий с целлюльными изображен ли на них один и тот же целое, кrimиналисты уведомают или уменьшают их так, чтобы расстояния междуrachками на общих портретах стало одинаковым, а затем совмещают их поrachкам. Нечто подобное мы проделаем с эмпирическими функциями распределения.

21

Вычислим при каждом $N$ среднее арифметическое $\bar{x}$ всех наблюдаемых значений $x_i$, называемое средним значением. Легко видеть, что $\bar{x} = \sum_{i=1}^{n} x_i \omega_i$.

Эта величина характеризует сдигг функции распределения по горизонтали. Вторая нужная нам величина —

$$\sigma_x = \sqrt{\sum_{i=1}^{n} (x_i - \bar{x})^2 \omega_i}$$

— называется средневадратным отклонением. Она служит мерой рассеивания наблюдаемых значений относительной среднего значения $\bar{x}$ — чем меньше $\sigma_x$, тем теснее расположены значения $x_i$. В нашей детективной аналоги величины $\sigma_x$ отвечает размер photographer. Приведем значения $\bar{x}$ и $\sigma_x$ для различных $N$.

| $N$ | 40 | $10^2$ | $10^3$ | $10^4$ | $10^5$ | $10^6$ |
| :— | :— | :— | :— | :— | :— | :— |
| $\bar{x}$ | 3,40 | 4,10 | 5,98 | 8,12 | 10,42 | 12,73 |
| $\sigma_x$ | 1,56 | 1,84 | 3,54 | 5,86 | 8,02 | 10,28 |

Как и следовало ожидать, обе эти характеристики растут с ростом $N$, что свидетельствует о расползании графиков $F_N$. Чтобы помешать распола-zанию, сдинем каждый график на $x$ влево и созMEM в $\sigma_x$ раз к оси ordinат. Для этого заменим величины $x_i$ новых величины $y_i = (x_i - x)/\sigma_x$ и пересчитаем таблицу накопленных частот:

| $y_i$ | $-0,90$ | $0,38$ | $1,67$ |
| :— | :— | :— | :— |
| $v_i$ | 0,50 | 0,80 | 1 |

По этой таблице нарисуем график функции распределения $\bar{F}_N(y)$ величини $y_i$ (рис. 2). Легко видеть, что среднее значение и средневадратное отклонение величини $y_i$ при всех $N$ будут равны 0 и 1. Вот эти графики $\bar{F}_N$ мы и будем сравнивать. Конечно, при больших $N$ эту работу надо поручить ЭВМ. За 20 минут работы мы на сбытродействием 300 тыс. операций в секунду выделя графики, изображенные на рисунке 3 (для $N = 10^3$, $10^4$, $10^5$ и $10^6$). Правда, похоже, что эти ступенчатые графики приближаются к пологому графику, наиссованному черным цветом? Это — график так называемого показательного распределения

$$F(y) = \begin{cases} 1 - e^{-y-1} & \text{при } y \geq -1, \\ 0 & \text{при } y < -1 \end{cases}$$

с нулявым средним и единичным средневадратным отклонением. Расчет, проведенный на ЭВМ, подтверждает нашей крительное величение. Верно ли, что при $N \to \infty$ графики $\bar{F}_N(y)$ стремятся к $F(y)$ — неизвестно. Пока это только гипотеза. Однако гипотеза, подтвержданая на множество из 78 497 первых простых чисел. И эта огромная работа выполена всего за 20 минут!

Интересно отмечить, что такое же распределение дают и интервалы между соседними сигналами в пуассоновском потоке (см. конец статьи «Как возникает распределение Пуассона»). Можно появить это, вспомнить, что, как было показано в этой статье, вероятность $P_0(t)$ того, что в течение времени $t$ не поступит ни одного сигнала, равна $e^{-\lambda t}$. Следовательно, вероятность того, что очередной сигнал, на-

22

Чиная с произвольного момента $t_0$, появится до момента $t_0 + t$, равна $1 - e^{-\lambda t}$. После соответствующего сдвига и скатия получится функция распределения, задаваемая равенством (2).

Можно попытаться обнарженное свойство расстояний между соседними простыми числами какими-нибудь известными их свойствами. Например, имеется оценка количества $N$, впервые доказанная французским математиком Ж. Адамаром и белгийским математиком Ш.-Ж. Валле Пуссеном в 1896 году: $\pi(N) \approx N/\ln N$. Расмотрим так называемые квазипростые числа: корни уравнений $n_i/\ln n_i = i + 3, i = 1, 2, 3...$, число которых на отрезке от 1 до $N$, очень удобно, также применно равно $N/\ln N$. Выпишем $n_1, n_2, ..., n_6$ и применим разностный анализ:

$$8,61 \quad 12,71 \quad 17,00 \quad 21,47 \quad 26,10 \quad 30,87 \quad 4,10 \quad 4,29 \quad 4,47 \quad 4,63 \quad 4,77 \quad 0,19 \quad 0,18 \quad 0,16 \quad 0,14$$

Видно, что расстояния между соседними квазипростыми числами $n_i$ и $n_{i+1}$ возратают, однако все медленнее с ростом $i$. Попробуйте, опираясь на это наблюдение, доказать, что для квазипростых чисел эмпирическая функция распределения выпукла вниз и поэтому не может совпадать с показательной функцией распределения. Следовательно, наша гипотеза не может быть обоснована просто оценкой числа $\pi(N)$. Если она верна, то ее доказательство должно использовать какие-то более глубокие факты.

Заказы принятия…

(Начало см. на с. 18)

Информация, программирование

52. Самарский А. А., Гулин А. В. Численные методы. 1 р. 90 к.

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

90. Знакомьте с персональной ЭВМ «Корвет». 95 к.

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

128. Абрамов С. А., Зima Е. В. Основы информаики. 1 р.

Содержит системизированное изложение основных понятий и методов информаики (вычислительной техники, программирования, численных методов, сортировки и поиск). Изложение основ программирования проводится на языке Паскаль.

129. Арсак Ж. Программирование и голосовойлокок. Пер. с фр. 90 к.

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

154. Новосельцев В. Н. Организм в мире техники: кибернетическая аспект. 70 к.

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

155. Дьяковов В. П. Справочник по расчетам на микрокалькуляторх. 1 р. 20 к.

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

156. Пильшиков В. Н. Сборник управления по языку Паскаль. 40 к.

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

159. Николов Р., Сендова Е. Начала информаики: Пер. с болг. 60 к.

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