Kempner function

Graph of the Kempner function

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

This function has the property that 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 and A. J. Kempner, who in 1918 gave the first correct algorithm for computing S(n).

In 1980 Florentin Smarandache published a paper called "A Function in the Number Theory" where he rediscovered this function. Professors Constantin Dumitrescu and Vasile Seleacu from the University of Craiova and the American scientist Charles Ashbacher published books about the Smarandache function which has now become used more broadly.

Properties

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

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 S(n) coincides with the largest prime factor of n for "almost all" n (in the sense that the asymptotic density of the set of exceptions is zero).

Computational complexity

The Kempner function S(n) of an arbitrary number n is the maximum, over the prime powers p^e dividing n, of S(p^e). When n is itself a prime power p^e, its Kempner function may be found in polynomial time by sequentially scanning the multiples of p until finding the first one whose factorial contains enough multiples of p. The same algorithm can be extended to any 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 n = px, where p is prime and x is less than p, the Kempner function of n is p. 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 n is a composite number, the greatest common divisor of S(n) and n will necessarily be a nontrivial divisor of n, allowing n to be factored by repeated evaluations of the Kempner function.

Associated series

Various series constructed from S(n) have been shown to be convergent. In the case of S(n), the series have been referred to in the literature as Smarandache constants, even when they depend on auxiliary parameters. Note also that these constants differ from the Smarandache constant that arises in Smarandache's generalization of Andrica's conjecture. The following are examples of such series:

• $\sum _{n=2}^{\infty }1/[S(n)]!=1.09317\ldots$ OEIS: A048799.
• $\sum _{n=2}^{\infty }S(n)/n!\approx 1.71400629359162\ldots$ OEIS: A048834 and is irrational.
• $\sum _{n=2}^{\infty }1/\prod _{i=2}^{n}S(i)\approx 0.719960700043\ldots$ OEIS: A048835.
• $\sum _{n}S(n)^{-\alpha }{S(n)!}^{-1/2}<\infty \,(\alpha >1).$

References and notes

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