Kempner function
In number theory, the Kempner function [math]\displaystyle{ S(n) }[/math][1] is defined for a given positive integer [math]\displaystyle{ n }[/math] to be the smallest number [math]\displaystyle{ s }[/math] such that [math]\displaystyle{ n }[/math] divides the factorial [math]\displaystyle{ s! }[/math]. For example, the number [math]\displaystyle{ 8 }[/math] does not divide [math]\displaystyle{ 1! }[/math], [math]\displaystyle{ 2! }[/math], or [math]\displaystyle{ 3! }[/math], but does divide [math]\displaystyle{ 4! }[/math], so [math]\displaystyle{ S(8)=4 }[/math].
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 [math]\displaystyle{ S(n) }[/math].[4]
The Kempner function is also sometimes called the Smarandache function following Florentin Smarandache's rediscovery of the function in 1980.[5]
Properties
Since [math]\displaystyle{ n }[/math] divides [math]\displaystyle{ n! }[/math], [math]\displaystyle{ S(n) }[/math] is always at most [math]\displaystyle{ n }[/math]. A number [math]\displaystyle{ n }[/math] greater than 4 is a prime number if and only if [math]\displaystyle{ S(n)=n }[/math].[6] That is, the numbers [math]\displaystyle{ n }[/math] for which [math]\displaystyle{ S(n) }[/math] is as large as possible relative to [math]\displaystyle{ n }[/math] are the primes. In the other direction, the numbers for which [math]\displaystyle{ S(n) }[/math] is as small as possible are the factorials: [math]\displaystyle{ S(k!)=k }[/math], for all [math]\displaystyle{ k\ge 1 }[/math].
[math]\displaystyle{ S(n) }[/math] is the smallest possible degree of a monic polynomial with integer coefficients, whose values over the integers are all divisible by [math]\displaystyle{ n }[/math].[1] For instance, the fact that [math]\displaystyle{ S(6)=3 }[/math] means that there is a cubic polynomial whose values are all zero modulo 6, for instance the polynomial [math]\displaystyle{ x(x-1)(x-2)=x^3-3x^2+2x, }[/math] 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 [math]\displaystyle{ S(n) }[/math] coincides with the largest prime factor of [math]\displaystyle{ n }[/math] for "almost all" [math]\displaystyle{ n }[/math] (in the sense that the asymptotic density of the set of exceptions is zero).[7]
Computational complexity
The Kempner function [math]\displaystyle{ S(n) }[/math] of an arbitrary number [math]\displaystyle{ n }[/math] is the maximum, over the prime powers [math]\displaystyle{ p^e }[/math] dividing [math]\displaystyle{ n }[/math], of [math]\displaystyle{ S(p^e) }[/math].[4] When [math]\displaystyle{ n }[/math] is itself a prime power [math]\displaystyle{ p^e }[/math], its Kempner function may be found in polynomial time by sequentially scanning the multiples of [math]\displaystyle{ p }[/math] until finding the first one whose factorial contains enough multiples of [math]\displaystyle{ p }[/math]. The same algorithm can be extended to any [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ n=px }[/math], where [math]\displaystyle{ p }[/math] is prime and [math]\displaystyle{ x }[/math] is less than [math]\displaystyle{ p }[/math], the Kempner function of [math]\displaystyle{ n }[/math] is [math]\displaystyle{ p }[/math].[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 [math]\displaystyle{ n }[/math] is a composite number, the greatest common divisor of [math]\displaystyle{ S(n) }[/math] and [math]\displaystyle{ n }[/math] will necessarily be a nontrivial divisor of [math]\displaystyle{ n }[/math], allowing [math]\displaystyle{ n }[/math] 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.
References and notes
- ↑ 1.0 1.1 Called the Kempner numbers in the Online Encyclopedia of Integer Sequences: see Sloane, N. J. A., ed. "Sequence A002034 (Kempner numbers: smallest number m such that n divides m!)". OEIS Foundation. https://oeis.org/A002034.
- ↑ "Question Nr. 288". Mathesis 3: 232. 1883.
- ↑ "Solutions de questions proposées, Question Nr. 288". Mathesis 7: 68–69. 1887.
- ↑ 4.0 4.1 4.2 Kempner, A. J. (1918). "Miscellanea". The American Mathematical Monthly 25 (5): 201–210. doi:10.2307/2972639.
- ↑ Hungerbühler, Norbert (2006). "A generalization of the Smarandache function to several variables". Integers 6: A23, 11. http://www.emis.de/journals/INTEGERS/papers/g23/g23.Abstract.html.
- ↑ R. Muller (1990). "Editorial". Smarandache Function Journal 1: 1. ISBN 84-252-1918-3. http://www.gallup.unm.edu/~smarandache/SFJ1.pdf.
- ↑ Erdős, Paul; Kastanas, Ilias (1994). "The smallest factorial that is a multiple of n (solution to problem 6674)". The American Mathematical Monthly 101: 179. doi:10.2307/2324376. http://www-fourier.ujf-grenoble.fr/~marin/une_autre_crypto/articles_et_extraits_livres/irationalite/Erdos_P._Kastanas_I.The_smallest_factorial...-.pdf..
This article incorporates material from Smarandache function on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
 |  |
