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

График функции Кемпнера

В теории чисел функция Кемпнера $S(n)$ определяется для данного положительного целого числа $n$ быть наименьшим числом $s$ такой, что $n$ делит факториал ​ $s!$. Например, число $8$ не делит $1!$, $2!$, или $3!$, но делит $4!$, так $S(8)=4$.

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

История

Эту функцию впервые рассмотрел Франсуа Эдуард Анатоль Люка в 1883 году. за ним последовал Жозеф Жан Батист Нойберг в 1887 году. В 1918 году А. Дж. Кемпнер предложил первый правильный алгоритм вычислений. $S(n)$.

Функцию Кемпнера также иногда называют функцией Смарандаша после повторного открытия этой функции Флорентином Смарандашем в 1980 году.

Характеристики

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

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

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

Вычислительная сложность

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

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

Ссылки и примечания

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