Kempner function

In number theory, the Kempner function

[1] is defined for a given positive integer

divides the factorial

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.

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

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

greater than 4 is a prime number if and only if

is as large as possible relative to

is as small as possible are the factorials:

is the smallest possible degree of a monic polynomial with integer coefficients, whose values over the integers are all divisible by

[1] For instance, the fact that

means that there is a cubic polynomial whose values are all zero modulo 6, for instance the polynomial

but that all quadratic or linear polynomials (with leading coefficient one) are nonzero modulo 6 at some integers.

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

coincides with the largest prime factor of

(in the sense that the asymptotic density of the set of exceptions is zero).

[7] The Kempner function

is the maximum, over the prime powers

, its Kempner function may be found in polynomial time by sequentially scanning the multiples of

until finding the first one whose factorial contains enough multiples of

The same algorithm can be extended to any

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.

, the Kempner function of

[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.

is a composite number, the greatest common divisor of

will necessarily be a nontrivial divisor of

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.

This article incorporates material from Smarandache function on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.