4.4 ФАКТОРИАЛЬНЫЕ ФАКТЫ

Давайте теперь посмотрим, как выглядит разложение на простые множители самых составных чисел — факториалов:

В соответствии с нашим соглашением относительно пустого произведения эта формула определяет 0! как 1. Таким образом, для каждого целого положительного числа Это число перестановок различных объектов, т. е. число способов размещения предметов в некотором ряду: для размещения первого предмета имеется вариантов; для каждого из этих вариантов имеется вариантов размещения второго предмета; для каждого из этих вариантов имеется вариантов размещения третьего предмета и т. д., что дает вариантов размещения в целом. Вот несколько первых значений

факториальной функции:

Полезно знать несколько факториальных фактов: например, точные значения первых шести факториалов, приблизительное значение 10! равное 3 миллиона с мелочью. Еще один полезный факт заключается в том, что количество цифр в записи превышает , когда

Можно доказать, что величина очень велика, используя нечто вроде уловки Гаусса из гл. 1:

Имеем поскольку квадратный многочлен принимает наименьшее значение при и наибольшее значение —при Поэтому

т. е.

Это соотношение указывает на то, что факториальная функция возрастает экспоненциально!!

Для более точного приближения при большом можно воспользоваться формулой Стирлинга, которую нам еще предстоит вывести в гл. 9:

А еще более точное приближение доставляет его асимптотическую относительную погрешность: формула Стирлинга „не дотягивает" до величины на множитель, примерно равный Даже при весьма малом подобное более точное приближение вполне достаточно. К примеру, приближение Стирлинга (4.23) при дает значение, близкое к 3598696, при этом погрешность — около — крайне мала. Хорошая вещь — асимптотика.

Но вернемся к простым числам. Хотелось бы для любого заданного простого числа установить наивысшую степень , которая делит т. е. показатель числа , с которым оно входит в однозначное разложение на простые множители. Обозначим эту величину через и начнем наше исследование с частного случая Поскольку 10! — произведение десяти

чисел, то величину можно найти, сложив вхождения степеней числа 2 в эти десять чисел; подобное вычисление соответствует суммированию столбцов в следующей таблице:

(Суммарные значения столбцов образуют то, что иногда называют линеечной функцией в силу ее сходства с линейкой деления которой отмечают доли дюйма.) Сумма этих чисел равна 8; следовательно, 28 делит нет.

Есть и другой способ: можно подсчитать вклады по строкам. В первой строке отмечены числа, которые вносят степень 2 (и, следовательно, делятся на 2): их Во второй строке отмечены те числа, которые вносят дополнительную степень 2: их . И, наконец, в третьей строке отмечены числа, которые вносят еще кое-что: их Тем самым подсчитываются все вклады, так что

Для произвольного данный метод дает

В действительности эта сумма конечна, так как при общий член суммы обращается в нуль. Следовательно, она содержит только ненулевых членов и довольно просто вычисляется. Так, если то

Каждый член в этой сумме — всего лишь пол от половины предыдущего члена. Это справедливо для любого поскольку, как частный случай выражения (3.11), получаем Если записать эти числа в двоичной форме, то суть дела становится предельно ясной:

Для получения последующего члена мы просто отбрасываем наименее значимый бит предыдущего.

Помимо этого, двоичное представление показывает, как вывести другую формулу:

где — число единиц в двоичном представлении Подобное упрощение возможно потому, что каждая 1, которая обеспечивает вклад в величину обеспечивает вклад в величину

Обобщая наши находки на произвольное простое число и используя прежнее рассуждение, получаем, что

А какова примерно величина Можно получить простую (но хорошую) верхнюю оценку, просто удаляя пол в общем члене суммы, а затем суммируя бесконечную геометрическую прогрессию:

это неравенство свидетельствует, что . Таким образом, 100 — как оценка сверху — не только правильна, но и близка к действительному значению 97. И в самом деле, в общем случае действительная величина потому что асимптотически много меньше

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

Оценка для величины в свою очередь, приводит к оценке для величины которая равна вкладам

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

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

самое большее, Но неравенство можно легко опровергнуть, выбрав достаточно большое скажем, Тогда

что противоречит неравенству которое было установлено в (4.22). Так что простых чисел все же бесконечно много.

Можно еще помусолить это рассуждение, с тем чтобы получить грубую оценку для — количества простых чисел, не превосходящих Каждое такое простое число вносит в разложение множитель, меньший чем 271; поэтому, как и прежде,

Если здесь заменить величину приближением Стирлинга (4.23), которое служит ее нижней оценкой, и взять логарифмы, то получим

откуда

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