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

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

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

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

История

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

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

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

С п разделяет п!, S(п) всегда не больше п. Число п больше 4 - это простое число если и только если S(п) = п.[6] То есть числа п для которого S(п) как можно больше относительно п простые числа. В обратном направлении числа, для которых S(п) настолько малы, насколько это возможно, факториалы: S(k!) = k, для всехk ≥ 1.

S(п) является минимально возможным степень из монический многочлен с целыми коэффициентами, значения которых над целыми числами делятся на п.[1]Например, тот факт, что S(6) = 3 означает, что существует кубический многочлен чьи значения все равны нулю по модулю 6, например, многочлен

но что все квадратичные или линейные многочлены (со старшим коэффициентом один) отличны от нуля по модулю 6 при некоторых целых числах.

В одной из сложных задач в Американский математический ежемесячный журнал, установленной в 1991 году и решенной в 1994 году, Пол Эрдёш указал, что функция S(п) совпадает с наибольшим главный фактор из п для "почти всех" п (в том смысле, что асимптотическая плотность множества исключений равно нулю).[7]

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

Функция Кемпнера S(п) произвольного числа п это максимум, за основные силы пе разделение п, из S(пе).[4]Когда п сама по себе главная сила пе, его функцию Кемпнера можно найти в полиномиальное время путем последовательного сканирования кратных п пока не будет найден первый, факториал которого содержит достаточно кратныхп. Такой же алгоритм может быть расширен на любой п чья факторизация на простые множители уже известна, применяя ее отдельно к каждой степени простых чисел в факторизации и выбирая ту, которая приводит к наибольшему значению.

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

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

  1. ^ а б Вызвал номера Кемпнера в Интернет-энциклопедия целочисленных последовательностей: видеть Слоан, Н. Дж. А. (ред.). "Последовательность A002034 (числа Кемпнера: наименьшее число м такой, что п разделяетм!)". В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
  2. ^ Лукас, Э. (1883). «Вопрос № 288». Матезис. 3: 232.
  3. ^ Нойберг, Дж. (1887 г.). «Предлагаемые решения вопросов, вопрос № 288». Матезис. 7: 68–69.
  4. ^ а б c Кемпнер, А. Дж. (1918). "Разное". Американский математический ежемесячный журнал. 25 (5): 201–210. Дои:10.2307/2972639. JSTOR  2972639.
  5. ^ Хунгербюлер, Норберт; Спекер, Эрнст (2006), «Обобщение функции Смарандаче на несколько переменных», Целые числа, 6: A23, 11, Г-Н  2264838
  6. ^ Р. Мюллер (1990). «Редакция» (PDF). Журнал функций Smarandache. 1: 1. ISBN  84-252-1918-3.
  7. ^ Эрдеш, Пол; Кастанас, Илиас (1994), "Наименьший факториал, кратный п (решение проблемы 6674) " (PDF), Американский математический ежемесячный журнал, 101: 179, Дои:10.2307/2324376.

В этой статье использованы материалы из Функция смарандаче на PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.