Функция Кемпнера

В теории чисел функция Кемпнера ^[1] определяется для данного положительного целого числа как наименьшее число , которое делит факториал . Например, число не делит , , или , но делит , поэтому .${\displaystyle S(n)}$ ${\displaystyle n}$${\displaystyle с}$${\displaystyle n}$ ${\displaystyle s!}$${\displaystyle 8}$${\displaystyle 1!}$${\displaystyle 2!}$${\displaystyle 3!}$${\displaystyle 4!}$ ${\displaystyle S(8)=4}$

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

Эту функцию впервые рассмотрел Франсуа Эдуард Анатоль Люка в 1883 году ^[2] , а затем Жозеф Жан Батист Нойберг в 1887 году ^[3]. В 1918 году А. Дж. Кемпнер предложил первый правильный алгоритм вычисления . ^[4]${\displaystyle S(n)}$

Функцию Кемпнера иногда называют функцией Смарандаке после того, как Флорентин Смарандаке заново открыл ее в 1980 году. ^[5]

Так как делит , всегда не более . Число больше 4 является простым числом тогда и только тогда, когда . ^[6] То есть, числа, для которых является максимально большим относительно являются простыми числами. В обратном направлении, числа, для которых является максимально малым являются факториалами: , для всех .${\displaystyle n}$ ${\displaystyle н!}$ ${\displaystyle S(n)}$${\displaystyle n}$${\displaystyle n}$${\displaystyle S(n)=n}$${\displaystyle n}$${\displaystyle S(n)}$${\displaystyle n}$${\displaystyle S(n)}$${\displaystyle S(к!)=к}$${\displaystyle k\geq 1}$

${\displaystyle S(n)}$является наименьшей возможной степенью монического многочлена с целыми коэффициентами, значения которого над целыми числами все делятся на . ^[1]${\displaystyle n}$ Например, тот факт , что существует кубический многочлен , все значения которого равны нулю по модулю 6, например многочлен , но что все квадратичные или линейные многочлены (со старшим коэффициентом один) являются ненулевыми по модулю 6 для некоторых целых чисел.${\displaystyle S(6)=3}$$${\displaystyle x(x-1)(x-2)=x^{3}-3x^{2}+2x,}$$

В одной из сложных задач в The American Mathematical Monthly , поставленной в 1991 году и решенной в 1994 году, Пол Эрдёш указал, что функция совпадает с наибольшим простым множителем для «почти всех» (в том смысле, что асимптотическая плотность множества исключений равна нулю). ^[7]${\displaystyle S(n)}$${\displaystyle n}$${\displaystyle n}$

Функция Кемпнера произвольного числа является максимумом по простым степеням, делящим , из . ^[4] Когда само является простой степенью , его функция Кемпнера может быть найдена за полиномиальное время путем последовательного сканирования кратных , пока не будет найдено первое число, факториал которого содержит достаточно кратных . Тот же алгоритм можно распространить на любое число, разложение которого на простые множители уже известно, применяя его отдельно к каждой простой степени в разложении и выбирая ту, которая приводит к наибольшему значению.${\displaystyle S(n)}$${\displaystyle n}$ ${\displaystyle p^{e}}$${\displaystyle n}$${\displaystyle S(p^{e})}$${\displaystyle n}$${\displaystyle p^{e}}$${\displaystyle p}$${\displaystyle p}$${\displaystyle n}$

Для числа вида , где является простым и меньше , функция Кемпнера числа равна . ^[4] Из этого следует, что вычисление функции Кемпнера полупростого числа (произведения двух простых чисел) вычислительно эквивалентно нахождению его разложения на простые множители , что считается сложной задачей. В более общем смысле, всякий раз, когда является составным числом , наибольший общий делитель и обязательно будет нетривиальным делителем , что позволяет разложить его на множители путем повторных вычислений функции Кемпнера. Следовательно, вычисление функции Кемпнера в общем случае не может быть проще, чем разложение на множители составных чисел.${\displaystyle n=px}$${\displaystyle p}$${\displaystyle x}$${\displaystyle p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n}$${\displaystyle S(n)}$ ${\displaystyle n}$ ${\displaystyle n}$${\displaystyle n}$

В данной статье использованы материалы функции Smarandache на PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .