In number theory, the Kempner function ${\displaystyle S(n)}$^[1] is defined for a given positive integer ${\displaystyle n}$ to be the smallest number ${\displaystyle s}$ such that ${\displaystyle n}$ divides the factorial ${\displaystyle s!}$. For example, the number ${\displaystyle 8}$ does not divide ${\displaystyle 1!}$, ${\displaystyle 2!}$, or ${\displaystyle 3!}$, but does divide ${\displaystyle 4!}$, so ${\displaystyle S(8)=4}$.

This function has the property that it has a highly inconsistent growth rate: it grows linearly on the prime numbers but only grows sublogarithmically at the factorial numbers.

History

This function was first considered by François Édouard Anatole Lucas in 1883,^[2] followed by Joseph Jean Baptiste Neuberg in 1887.^[3] In 1918, A. J. Kempner gave the first correct algorithm for computing ${\displaystyle S(n)}$.^[4]

The Kempner function is also sometimes called the Smarandache function following Florentin Smarandache's rediscovery of the function in 1980.^[5]

Properties

Since ${\displaystyle n}$ divides ${\displaystyle n!}$, ${\displaystyle S(n)}$ is always at most ${\displaystyle n}$. A number ${\displaystyle n}$ greater than 4 is a prime number if and only if ${\displaystyle S(n)=n}$.^[6] That is, the numbers ${\displaystyle n}$ for which ${\displaystyle S(n)}$ is as large as possible relative to ${\displaystyle n}$ are the primes. In the other direction, the numbers for which ${\displaystyle S(n)}$ is as small as possible are the factorials: ${\displaystyle S(k!)=k}$, for all ${\displaystyle k\geq 1}$.

${\displaystyle S(n)}$ is the smallest possible degree of a monic polynomial with integer coefficients, whose values over the integers are all divisible by ${\displaystyle n}$.^[1] For instance, the fact that ${\displaystyle S(6)=3}$ means that there is a cubic polynomial whose values are all zero modulo 6, for instance the polynomial

$${\displaystyle x(x-1)(x-2)=x^{3}-3x^{2}+2x,}$$

In one of the advanced problems in The American Mathematical Monthly, set in 1991 and solved in 1994, Paul Erdős pointed out that the function ${\displaystyle S(n)}$ coincides with the largest prime factor of ${\displaystyle n}$ for "almost all" ${\displaystyle n}$ (in the sense that the asymptotic density of the set of exceptions is zero).^[7]

Computational complexity

The Kempner function ${\displaystyle S(n)}$ of an arbitrary number ${\displaystyle n}$ is the maximum, over the prime powers ${\displaystyle p^{e))$ dividing ${\displaystyle n}$, of ${\displaystyle S(p^{e})}$.^[4] When ${\displaystyle n}$ is itself a prime power ${\displaystyle p^{e))$, its Kempner function may be found in polynomial time by sequentially scanning the multiples of ${\displaystyle p}$ until finding the first one whose factorial contains enough multiples of ${\displaystyle p}$. The same algorithm can be extended to any ${\displaystyle n}$ whose prime factorization is already known, by applying it separately to each prime power in the factorization and choosing the one that leads to the largest value.

For a number of the form ${\displaystyle n=px}$, where ${\displaystyle p}$ is prime and ${\displaystyle x}$ is less than ${\displaystyle p}$, the Kempner function of ${\displaystyle n}$ is ${\displaystyle p}$.^[4] It follows from this that computing the Kempner function of a semiprime (a product of two primes) is computationally equivalent to finding its prime factorization, believed to be a difficult problem. More generally, whenever ${\displaystyle n}$ is a composite number, the greatest common divisor of ${\displaystyle S(n)}$ and ${\displaystyle n}$ will necessarily be a nontrivial divisor of ${\displaystyle n}$, allowing ${\displaystyle n}$ to be factored by repeated evaluations of the Kempner function. Therefore, computing the Kempner function can in general be no easier than factoring composite numbers.