Kempner function
In number theory, the Kempner function is defined for a given positive integer to be the smallest number such that divides the For example, the number does not divide,, but does
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, followed by Joseph Jean Baptiste Neuberg in 1887. In 1918, A. J. Kempner gave the first correct algorithm forThe Kempner function is also sometimes called the Smarandache function following Florentin Smarandache's rediscovery of the function
Properties
Since is always at A number is prime if and only That is, the numbers for which is as large as possible relative to are the primes. In the other direction, the numbers for which is as small as possible are the factorials: foris the smallest possible degree of a monic polynomial with integer coefficients, whose values over the integers are all divisible
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 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 for "almost all" .
Computational complexity
The Kempner function of an arbitrary number is the maximum, over the prime powers dividing, of. When is itself a prime power, 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 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.For a number of the form, where is prime and, the Kempner function of is. It follows from this that computing the Kempner function of a semiprime is computationally equivalent to finding its prime factorization, believed to be a difficult problem. More generally, whenever is composite, the greatest common divisor of will necessarily be a nontrivial divisor allowing 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.